社区讨论
为什么会死循环?
学术版参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo9qisqp
- 此快照首次捕获于
- 2023/10/28 15:42 2 年前
- 此快照最后确认于
- 2023/11/02 11:04 2 年前
代码:
(经过debug大概可以确定出错在了build函数中,但是不知道具体是哪里)
CPP#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 8*1e4+10,M=2*1e5+10;
struct Edge
{
int u, v, w;
} edges1[M], edges2[M];
int n, m, s, buc[M];
int idx1 = 0, head1[N], nxt1[M];
int idx2 = 0, head2[N], nxt2[M];
int dfn[N], low[N], time_cnt = 0;
int stk[N], in_stk[N], top = 0;
int scc_cnt = 0, id[N], scc_sum[N];
inline void add1(int u, int v, int w)
{
Edge &e = edges1[idx1];
e.u = u, e.v = v, e.w = w;
nxt1[idx1] = head1[u], head1[u] = idx1 ++;
}
inline void add2(int u, int v, int w)
{
Edge &e = edges2[idx2];
e.u = u, e.v = v, e.w = w;
nxt2[idx2] = head2[u], head2[u] = idx2 ++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ time_cnt;
in_stk[u] = 1, stk[++ top] = u;
for(int i = head1[u]; ~i; i = nxt1[i])
{
int v = edges1[i].v;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
} else if(in_stk[v])
low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
scc_cnt ++;
int a;
do
{
a = stk[top --];
id[a] = scc_cnt;
in_stk[a] = 0;
} while(u != a);
}
}
void build()
{
for(int i = 0; i < idx1; i ++)
{
// 把这里改为 Edge e = edges1[idx1] 就不会死循环
Edge e = edges1[i];
int u = e.u, v = e.v, w = e.w;
if(id[u] == id[v])
{
int tot = w, w_ = w;
while(w_) w_ = w_ * buc[idx1] / 10, tot += w_;
scc_sum[id[u]] += tot;
} else add2(u, v, w);
}
for(int u = 1; u <= scc_cnt; u ++)
{
for(int j = head2[u]; ~j; j = nxt2[u])
{
int v = edges2[j].v, w = edges2[j].w;
scc_sum[v] += w, edges2[j].w = 0;
}
}
}
int dp(int u)
{
int mx = 0;
for(int i = head2[u]; ~i; i = nxt2[i])
mx = max(mx, dp(edges2[i].v));
return mx + scc_sum[u];
}
int main()
{
memset(head1, -1, sizeof head1);
memset(head2, -1, sizeof head2);
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i ++)
{
int u, v, w;
scanf("%d %d %d 0.%d", &u, &v, &w, &buc[idx1]);
add1(u, v, w);
}
scanf("%d", &s);
for(int i = 1; i <= n; i ++) if(!dfn[i]) tarjan(i);
build();
printf("\n%d\n", dp(id[s]));
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...