关注
#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++ 没过,还没改回来就时间到了 这是改完后的,不知道能不能过,希望哪位大佬能帮我看看
查看原帖
点赞 评论
相关推荐

点赞 评论 收藏
分享
牛客热帖
更多
- 1... 脱下孔乙己长衫,浅聊一下就业下沉!3.9W
- 2... 美团java后端日常实习一二面1.5W
- 3... 腾讯PCG QQ后台开发一面1.3W
- 4... 腾讯/字节/快手 前端面经汇总1.0W
- 5... 【未来准备7】就业下沉时代,如何摆脱困境9014
- 6... 实习入职第一天,应该做点啥❓7760
- 7... 腾讯2025暑期实习提前批前端开发面经(已OC)5989
- 8... [26届四段大厂]“HR面致命题!腾讯字节亲测”5188
- 9... 字节前端日常实习 oc 总结4876
- 10... 【有奖互动】你问过DeepSeek什么意想不到的问题?4850
正在热议
更多
# 听劝,这个简历怎么改 #
18286次浏览 239人参与
# 你见过最离谱的招聘要求是什么? #
146229次浏览 871人参与
# 水滴春招 #
34054次浏览 570人参与
# 你想留在一线还是回老家? #
16586次浏览 236人参与
# 分享一个让你热爱工作的瞬间 #
16490次浏览 174人参与
# 25届如何提前做秋招准备? #
145526次浏览 2288人参与
# 入职第四天,心情怎么样 #
12699次浏览 88人参与
# 面试被问“你的缺点是什么?”怎么答 #
11020次浏览 218人参与
# 参加完秋招的机械人,还参加春招吗? #
27650次浏览 281人参与
# 如果你有一天可以担任公司的CEO,你会做哪三件事? #
20716次浏览 415人参与
# 机械校招之路总结 #
80284次浏览 1759人参与
# 第一份工作应该选高薪还是热爱? #
5179次浏览 83人参与
# 如果重来一次你还会读研吗 #
156916次浏览 1716人参与
# 租房找室友 #
8515次浏览 53人参与
# 职场新人生存指南 #
200991次浏览 5563人参与
# 地方国企笔面经互助 #
18109次浏览 26人参与
# 简历无回复,你会继续海投还是优化再投? #
49008次浏览 564人参与
# 读研or工作,哪个性价比更高? #
26503次浏览 357人参与
# 你们的毕业论文什么进度了 #
905102次浏览 8995人参与
# 文科生还参加今年的春招吗 #
4456次浏览 32人参与
# 百度工作体验 #
178223次浏览 1780人参与