求强连通分量,缩点,强连通分量内部的权值都为0,
找出每个强连通分量的权值最小的入边,
入度为0的强连通分量的入边为0
#include<stdio.h> #include<stack> #include<string.h> using namespace std; #define N 50001 #define inf 0x3fffffff int n,m,OP; int belong[N],dfs[N],low[N],ins[N],in[N],inp[N]; struct op { int count,end; struct op *next; }*e[N*2]; void addeage(int x,int y,int z) { struct op *q=new op; q->end=y; q->count=z; q->next=e[x]; e[x]=q; } stack<int>Q; int ans,idx; void Tarjan(int x) { int v; dfs[x]=low[x]=idx++; Q.push(x); ins[x]=1; for(op *j=e[x];j;j=j->next) { if(dfs[j->end]==-1) { Tarjan(j->end); low[x]=low[x]>low[j->end]?low[j->end]:low[x]; } else if(ins[j->end]==1) low[x]=low[x]>dfs[j->end]?dfs[j->end]:low[x]; } if(low[x]==dfs[x]) { while(1) { v=Q.top(); Q.pop(); ins[v]=0; belong[v]=ans; if(v==x)break; } ans++; } } int main() { int i,j,x,y,z; while(scanf("%d%d",&n,&m)!=-1) { OP=0; for(i=0;i<n;i++) { e[i]=NULL; dfs[i]=-1; ins[i]=0; in[i]=inf; inp[i]=0; } for(i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&z); addeage(x,y,z); } ans=idx=0; for(i=0;i<n;i++) { if(dfs[i]==-1) Tarjan(i); } for(i=0;i<n;i++) { for(op *j=e[i];j;j=j->next) { if(belong[i]!=belong[j->end]) { inp[belong[j->end]]++;//计算每个点的入度 if(in[belong[j->end]]>j->count) in[belong[j->end]]=j->count; } } } for(i=0;i<ans;i++) { if(inp[i]!=0)//入度为0的不加 OP+=in[i]; } printf("%d\n",OP); } return 0; }