50pts 悬关-->WA 1,4,5,7,9
查看原帖
50pts 悬关-->WA 1,4,5,7,9
1050431
DevilsFlame楼主2024/8/8 09:35

em……没用到拓扑,就是将点合并,链接的边聚到一起,求大佬debug(下有注释说明)

#include<bits/stdc++.h>
#define N 10010
using namespace std;
int n,a,b,m,dfn[N],low[N],cnt;
int stk[N],top,s[N],to[N];
int d[N],dp[N];
bool in[N];
int ans;
vector <int> e[N],l[N];
void tarjan(int x)//tarjan
{
	stk[++ top] = x;
	dfn[x] = low[x] = ++ cnt;
	in[x] = 1;
	for(int i = 0;i < e[x].size();i ++)
	{
		int v = e[x][i];
		if(!dfn[v])
		{
			tarjan(v);
			low[x] = min(low[x],low[v]);
		}
		else if(in[v]) low[x] = min(low[x],low[v]);
	}
	if(dfn[x] == low[x])//强联通->缩点(预备)
	{
		while(stk[top] != x)
		{
			in[stk[top]] = 0;
			s[x] += s[stk[top]];//缩到一个点
			to[stk[top]] = x;//指向缩的点
			top --;
		}
		to[x] = x;//自己指自己
		in[x] = 0;
		top --;
	}
	return;
}
void dfs(int x,int fa)
{
	dp[x] = max(dp[x],dp[fa] + s[x]);//dp
	for(int i = 0;i < l[x].size();i ++) dfs(l[x][i],x);//看儿子
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> s[i];
    for(int i = 1;i <= m;i ++)
    {
        cin >> a >> b;
        e[a].push_back(b);
    }
    for(int i = 1;i <= n;i ++)
    {
    	if(!dfn[i]) tarjan(i);
	}
	for(int i = 1;i <= n;i ++)
	{
		int v = to[i];//指向缩的点
		for(int j = 0;j < e[i].size();j ++)//将边给缩点代表
		{
			int u = e[i][j];
			if(to[u] != v) l[v].push_back(u),d[u] ++;//合并边
		}
	}
	for(int i = 1;i <= n;i ++)//dp,从入度为0的开始找(d[i])
	{
		if(!d[i]) dfs(i,0);
		ans = max(ans,dp[i]);//去最大dp值
	}
	cout << ans << endl;
	return 0;
}
2024/8/8 09:35
加载中...