关注
#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++ 没过,还没改回来就时间到了 这是改完后的,不知道能不能过,希望哪位大佬能帮我看看
查看原帖
点赞 评论
相关推荐
01-21 04:38
中国矿业大学 大数据开发工程师 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 交出你的校招焚诀 #
11277次浏览 187人参与
# 公司情报交流地 #
144696次浏览 1275人参与
# 神州信息求职进展汇总 #
3734次浏览 69人参与
# 实习生至暗时刻 #
19322次浏览 373人参与
# 27届求职交流 #
3547次浏览 95人参与
# 面试___岗的必刷题单 #
13008次浏览 233人参与
# 26届求职交流 #
3060次浏览 69人参与
# 你的秋招第一面感觉怎么样 #
140642次浏览 806人参与
# 三月的小目标 #
12364次浏览 222人参与
# 经纬恒润求职进展汇总 #
153314次浏览 1080人参与
# 哪些公司开暑期实习了? #
18729次浏览 150人参与
# 米哈游求职进展汇总 #
585756次浏览 3015人参与
# AI面试问题分享 #
14138次浏览 284人参与
# 春招开局,你有保底offer吗? #
26735次浏览 212人参与
# 找AI工作应该卷什么? #
4347次浏览 77人参与
# 你经历过哪些AI幻觉? #
5167次浏览 120人参与
# 实习想申请秋招offer,能不能argue薪资 #
225084次浏览 1196人参与
# 字节开奖 #
130992次浏览 604人参与
# 实习生的生存小技巧 #
7160次浏览 115人参与
# 24届的你们现状如何了? #
112602次浏览 523人参与
# 硬件人的简历怎么写 #
329777次浏览 3090人参与
