70分求调qwq
查看原帖
70分求调qwq
413801
rabbitdit楼主2021/10/6 11:31

WA #4 #5 #7 下了个节点测了一下发现有些点度数不是0也就是拓扑排序没跑完,看了半天没找出问题```cpp

#include<bits/stdc++.h>
using namespace std;
int wea[10005];
int aftw[10005];
vector<int> graph[10005];
vector<int> aft[10005];
stack<int> st;
int dfn[10005];
int low[10005];
int dp[10005];
int bel[10005];
int degree[10005];
int zhuang[10005];
int ind=0,t=0;
int n,m;
int gg=0;
void tog(int lo) {
	ind++;
	aftw[ind]+=wea[lo];
	bel[lo]=ind;
	while(st.top()!=lo) {
		int pre=st.top();
		st.pop();
		aftw[ind]+=wea[pre];
		bel[pre]=ind;
	}
	st.pop();
}
void dfs(int lo) {
	st.push(lo);
	dfn[lo]=++t;
	low[lo]=t;
	zhuang[lo]=1;
	for(int i=0; i<graph[lo].size(); i++) {
		int to=graph[lo][i];
		if(!zhuang[to]) {
			dfs(to);
			low[lo]=min(low[lo],low[to]);
		} else if(zhuang[to]==1)low[lo]=min(low[lo],low[to]);
	}
	if(low[lo]==dfn[lo]) tog(lo);
	zhuang[lo]=2;
}
int topu() {
	int ans=0;
	queue<int> deal;
	for(int i=1; i<=ind; i++) if(!degree[i]) deal.push(i);
	while(deal.size()) {
		int pre=deal.front();
		deal.pop();
		dp[pre]+=aftw[pre];
		ans=max(ans,dp[pre]);
		for(int i=0; i<aft[pre].size(); i++) {
			int to=aft[pre][i];
			dp[to]=max(dp[to],dp[pre]);
			cout<<degree[to]<<endl;
			degree[to]--;
			if(!degree[to]) deal.push(to);
		}
	}
	return ans;
}
void mg() {
	for(int i=1; i<=n; i++) {
		for(int j=0; j<graph[i].size(); j++) {
			if(bel[i]!=bel[graph[i][j]]) {
				aft[bel[i]].push_back(bel[graph[i][j]]);
				degree[bel[graph[i][j]]]++;
			}
		}
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) scanf("%d",&wea[i]);
	while(m--) {
		int a,b;
		scanf("%d%d",&a,&b);
		graph[a].push_back(b);
	}
	for(int i=1; i<=n; i++) if(!low[i]) dfs(i);
	mg();
	cout<<topu();
	int text=0;
	return 0;
}
2021/10/6 11:31
加载中...