关注
#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++ 没过,还没改回来就时间到了 这是改完后的,不知道能不能过,希望哪位大佬能帮我看看
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你现在会用到哪些AI技能? #
3298次浏览 64人参与
# 为什么国企只招应届生 #
207147次浏览 1233人参与
# 智慧芽求职进展汇总 #
1335次浏览 5人参与
# 实习在多还是在精 #
31321次浏览 222人参与
# 你的房租占工资的比例是多少? #
63711次浏览 792人参与
# 秋招踩过的“雷”,希望你别再踩 #
75586次浏览 1018人参与
# 平安产险科技校招 #
358次浏览 0人参与
# 小马智行求职进展汇总 #
13134次浏览 49人参与
# 24届的你们现状如何了? #
98465次浏览 509人参与
# 我的求职进度条 #
71510次浏览 1016人参与
# 实习下班不想学习,正常吗? #
17777次浏览 168人参与
# HR问:你期望的薪资是多少?如何回答 #
63364次浏览 636人参与
# 你见过哪些工贼行为 #
15143次浏览 86人参与
# 反问环节如何提问 #
114566次浏览 2442人参与
# 如果不考虑收入,你最想做什么工作? #
32203次浏览 185人参与
# 校招谈薪一定要知道的事 #
11992次浏览 110人参与
# 顺丰求职进展汇总 #
62840次浏览 312人参与
# 大厂VS公务员你怎么选 #
21581次浏览 333人参与
# 找工作中的小确幸 #
24416次浏览 254人参与
# 牛客租房专区 #
118561次浏览 1334人参与
# 求职遇到的搞笑事件 #
140548次浏览 852人参与
# 你觉得什么岗位会被AI替代 #
15006次浏览 161人参与