题意：给定n个节点m条边的有向带权图，求以0为根节点的最小树形图权值大小
1 #include<cstdio> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 const int maxn=1e3+10; 6 const int maxm=4e4+10; 7 const int inf=0x3f3f3f3f; 8 int n,m; 9 int cost[maxn],pre[maxn],vis[maxn],id[maxn]; 10 struct node 11 { 12 int u,v,w; 13 }a[maxm]; 14 int zhu_liu(int root) 15 { 16 int ans=0; 17 while(1){ 18 for(int i=0;i<n;i++) cost[i]=inf; 19 20 for(int i=0;i<m;i++){ 21 int u=a[i].u,v=a[i].v,w=a[i].w; 22 if(cost[v]>w&&u!=v){ 23 pre[v]=u; 24 cost[v]=w; 25 } 26 } 27 28 for(int i=0;i<n;i++){ 29 if(i==root) continue; 30 if(cost[i]==inf) return -1; 31 } 32 33 int cnt_circle=0; 34 memset(id,-1,sizeof(id)); 35 memset(vis,-1,sizeof(vis)); 36 cost[root]=0; 37 for(int i=0;i<n;i++){ 38 ans+=cost[i]; 39 int p=i; 40 while(vis[p]!=i&&id[p]==-1&&p!=root) 41 vis[p]=i,p=pre[p]; 42 if(id[p]==-1&&p!=root){ 43 for(int u=pre[p];u!=p;u=pre[u]){ 44 id[u]=cnt_circle; 45 } 46 id[p]=cnt_circle++; 47 } 48 } 49 if(!cnt_circle) break; 50 for(int i=0;i<n;i++) 51 if(id[i]==-1) id[i]=cnt_circle++; 52 for(int i=0;i<m;i++){ 53 int v=a[i].v; 54 a[i].u=id[a[i].u]; 55 a[i].v=id[a[i].v]; 56 if(a[i].u!=a[i].v){ 57 a[i].w=a[i].w-cost[v]; 58 } 59 } 60 n=cnt_circle; 61 root=id[root]; 62 } 63 return ans; 64 } 65 int main() 66 { 67 int T; 68 int cnt=0; 69 scanf("%d",&T); 70 while(T--){ 71 scanf("%d%d",&n,&m); 72 for(int i=0;i<m;i++) 73 scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w); 74 int ans=zhu_liu(0); 75 printf("Case #%d: ",++cnt); 76 if(ans==-1) printf("Possums!\n"); 77 else printf("%d\n",ans); 78 } 79 return 0; 80 }