关注
#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 5;
int a[N];
vector <int> vec[N];
vector <int> fac[N];
vector <pair<double, double> > Node[N];
vector <pair<double, double> > tmp;
bool vis[N];
double fini[N];
int n, m, B, E;
void dfs(int v)
{
tmp.clear();
if(v == B) {
vis[v] = 1; fini[v] = 1.0 * a[v] / (1.0 * E);
double flo = 0.0;
if(vec[v].size()) flo = 1.0 * E / (1.0 * vec[v].size());
tmp.push_back(make_pair(fini[v], flo));
Node[v] = tmp;
return ;
}
for(auto u: fac[v]) {
//cout << v << " " << u << endl;
if(!vis[u]) dfs(u);
for(auto x: Node[u]) {
tmp.push_back(x);
//cout << v << " " << u << " " << x.first << " " << x.second << endl;
}
}
vis[v] = 1;
if(tmp.size() == 0) {
fini[v] = -1.0; return ;
}
sort(tmp.begin(), tmp.end());
int tmpl = tmp.size();
double pre = 0.0;
double sum = 0.0;
int flg = -1;
for(int i = 0; i < tmpl-1; ++ i) {
pre += tmp[i].second;
double inv = tmp[i+1].first - tmp[i].first;
if(sum + inv*pre > 1.0 * a[v]) {
fini[v] = tmp[i].first + 1.0 * (1.0 * a[v] - sum) / pre;
flg = i; break;
}
sum += inv*pre;
}
if(flg == -1) {
double ptim = tmp[tmpl - 1].first;
//if(tmpl >= 2) ptim = tmp[tmpl - 2].first;
fini[v] = ptim + 1.0 * (1.0 * a[v] - sum) / (pre + tmp[tmpl - 1].second);
double fi = fini[v];
double se = pre + tmp[tmpl - 1].second;
tmp.resize(1);
tmp[0] = make_pair(fi, se / (1.0 * vec[v].size()));
Node[v] = tmp;
return ;
}
int nl = 0;
for(int i = flg; i < tmpl; ++ i) {
tmp[nl] = tmp[i];
tmp[nl].second = tmp[i].second / (1.0 * vec[v].size());
nl ++;
}
tmp[0].first = fini[v];
tmp[0].second = pre / (1.0 * vec[v].size());
tmp.resize(nl);
Node[v] = tmp;
return ;
}
int main()
{
int T;
scanf("%d", &T);
while(T --) {
scanf("%d%d%d%d", &n, &m, &B, &E);
for(int i = 1; i <= n; ++ i) {
scanf("%d", a + i);
vec[i].clear();
fac[i].clear();
Node[i].clear();
}
for(int i = 1; i <= m; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
vec[u].push_back(v);
fac[v].push_back(u);
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++ i) {
if(!vis[i]) dfs(i);
}
for(int i = 1; i <= n; ++ i) {
printf("%.8f", fini[i]);
if(i != n) printf(" ");
}
printf("\n");
}
return 0;
}
第三题,场上少写了个 nl++ 没过,还没改回来就时间到了 这是改完后的,不知道能不能过,希望哪位大佬能帮我看看
查看原帖
点赞 评论
相关推荐
牛客热帖
更多
正在热议
更多
# 为了入行xx岗,我学了__ #
7254次浏览 115人参与
# 26届校招投递进展 #
586327次浏览 3775人参与
# 简历第一个项目做什么 #
8280次浏览 123人参与
# 被说“做题家”,你的反应是_____? #
3066次浏览 105人参与
# 实习的你做了哪些离谱的工作 #
11301次浏览 126人参与
# 你都见过什么样的草台班子? #
10307次浏览 83人参与
# Prompt分享 #
3384次浏览 93人参与
# 找实习记录 #
40030次浏览 586人参与
# 工作压力大,你会干什么? #
15239次浏览 334人参与
# 从哪些方向判断这个offer值不值得去? #
48708次浏览 342人参与
# 找工作前vs找工作后的心路变化 #
37303次浏览 301人参与
# AI让你的思考变深了还是变浅了? #
5847次浏览 147人参与
# 多益网络求职进展汇总 #
62238次浏览 281人参与
# 如果不上班,你会去做什么 #
8390次浏览 295人参与
# 入职以后才知道的校招谎言 #
117241次浏览 747人参与
# 去年你投递实习了吗? #
28206次浏览 335人参与
# 大家每天通勤多久? #
75464次浏览 537人参与
# 今年秋招还有金九银十吗 #
71433次浏览 502人参与
# 邪修省钱套路 #
8501次浏览 268人参与
# 校招入职后的感受 #
466573次浏览 3629人参与

