关注
#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-29 11:37
东南大学 测试开发 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 春招什么时候投? #
9318次浏览 159人参与
# 今年秋招你收到了多少封邮件? #
37249次浏览 273人参与
# 春节前,你还在投简历吗? #
12713次浏览 146人参与
# 牛友的春节生活 #
6193次浏览 138人参与
# 牛客AI体验站 #
14511次浏览 266人参与
# 春节提前走,你用什么理由请假? #
8926次浏览 215人参与
# 从夯到拉,锐评职场mentor #
4236次浏览 64人参与
# 备战春招/暑实,现在应该做什么? #
4101次浏览 137人参与
# 实习到现在,你最困惑的一个问题 #
3929次浏览 116人参与
# 距离春招还有一个月,你现在是什么开局? #
5944次浏览 107人参与
# AI“智障”时刻 #
25809次浏览 128人参与
# 聊聊Agent开发 #
23060次浏览 568人参与
# 机械人的offer怎么选 #
250257次浏览 1186人参与
# 暑期实习什么时候投? #
6342次浏览 153人参与
# 推荐一个值得做的AI项目 #
6230次浏览 168人参与
# 投格力的你,拿到offer了吗? #
171452次浏览 875人参与
# 非技术2024笔面经 #
465897次浏览 4940人参与
# 实习生应该准时下班吗 #
335647次浏览 1737人参与
# 通信硬件薪资爆料 #
1226279次浏览 7207人参与
# 大家实习每天都在干啥 #
121646次浏览 633人参与
