本人蒟蒻,请问此题拓扑排序的意义是什么
查看原帖
本人蒟蒻,请问此题拓扑排序的意义是什么
920270
Wei_scky楼主2024/7/17 14:56

这是我的代码,没有拓扑也能A过,求dalao指点

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=N*N/2;
queue<int>q;
int n,m;
int in[N],out[N];
int k,pre[N];
struct re {
	int to,nxt,w;
}a[N];
int f[N],u[N],ans[N],len;//信号值和阈值 
void add(int x,int y,int z) {
	a[k].to=y;
	a[k].w=z;
	a[k].nxt=pre[x];
	pre[x]=k++;
}
//void topsort() {
//	for(int i=1;i<=n;i++) {
//		if(!in[i]) q.push(i);
//	}
//	while(!q.empty()) {
//		int x=q.front(); q.pop();
//		ans[len++]=x; 
//		for(int i=pre[x];~i;i=a[i].nxt) {
//			in[a[i].to]--;
//			if(!in[a[i].to]) q.push(a[i].to);
//		}
//	}
//}
int main() {
	ios::sync_with_stdio(false);
	memset(pre,-1,sizeof pre);
    cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>f[i]>>u[i];
	} 
	for(int i=0;i<m;i++) {
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		in[y]++; out[x]++;
	}
	for(int i=1;i<=n;i++) {
		if(in[i]) f[i]-=u[i];
	}
//	topsort();
	for(int i=0;i<n;i++) {
		if(f[i]>0) {
			for(int k=pre[i];~k;k=a[k].nxt) f[a[k].to]+=f[i]*a[k].w;
		}
	}
	bool sf=0;
	for(int i=1;i<=n;i++) {
		if(f[i]>0&&!out[i]) cout<<i<<" "<<f[i]<<"\n",sf=1;
	}
	if(!sf) cout<<"NULL";
	return 0;
}

2024/7/17 14:56
加载中...