思路
- 首先明确是图论题,而图论题最重要的是抽象出题意。
- 通过读题我们可以明白这道题就是对每一个点的值进行计算即可
- 直观的想,我们可以遍历所有边并去更新点的值,但是这样并不能保证那个点的值已经被计算出来了
- 计算点的值要有一定的顺序,我们一定要保证用来更新当前点的点的值已经被计算出来了
- 为了满足3,我们可以进行拓扑排序
- 最后寻找终点时,可由出度为0来判断
- 时间复杂度:拓扑排序O(n+m)
参考代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110,M=N*N/2;
int h[N],e[M],ne[M],w[M],idx;
int q[N];
int din[N],dout[N];
int f[N];
int n,m;
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
void topsort()
{
int tt=-1,hh=0;
for(int i=1;i<=n;++i)
if(!din[i])
q[++tt]=i;
while(hh<=tt){
int t = q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
din[j]--;
if(!din[j])
q[++tt]=j;
}
}
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
int a;
cin>>f[i]>>a;
if(!f[i])
f[i]-=a;
}
for(int i=0;i<m;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
din[b]++;
dout[a]++;
}
topsort();
for(int i=0;i<n;++i){
int j=q[i];
if(f[j]>0){
for(int k=h[j];k!=-1;k=ne[k]){
f[e[k]]+=w[k]*f[j];
}
}
}
bool flag = true;
for(int i=1;i<=n;++i){
if(!dout[i]&&f[i]>0){
printf("%d %d\n",i,f[i]);
flag = false;
}
}
if(flag)puts("NULL");
return 0;
}