社区讨论

为什么会死循环?

学术版参与者 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 条回复,欢迎继续交流。

正在加载回复...