http://acm.hdu.edu.cn/showproblem.php?pid=3435
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <queue> 5 #include <algorithm> 6 #define inf 0x3f3f3f3f 7 #define maxn 54444 8 using namespace std; 9 10 queue<int>q; 11 struct node 12 { 13 int u,v,next,val,f; 14 } p[maxn]; 15 int head[maxn]; 16 bool vis[maxn]; 17 int dis[maxn]; 18 int pre[maxn]; 19 int n,m,s,t,e; 20 21 void add(int u,int v,int f,int c) 22 { 23 p[e].u=u; 24 p[e].v=v; 25 p[e].f=f; 26 p[e].val=c; 27 p[e].next=head[u]; 28 head[u]=e++; 29 p[e].u=v; 30 p[e].v=u; 31 p[e].f=0; 32 p[e].val=-c; 33 p[e].next=head[v]; 34 head[v]=e++; 35 36 } 37 38 bool spfa() 39 { 40 int j,k,i; 41 while(!q.empty()) q.pop(); 42 memset(vis,false,sizeof(vis)); 43 memset(dis,0x3f,sizeof(dis)); 44 memset(pre,-1,sizeof(pre)); 45 vis[s]=true; 46 dis[s]=0; 47 q.push(s); 48 while(!q.empty()) 49 { 50 int u=q.front(); 51 q.pop(); 52 vis[u]=false; 53 for(j=head[u]; j!=-1; j=p[j].next) 54 { 55 int v=p[j].v; 56 if(p[j].f&&dis[u]+p[j].val<dis[v]) 57 { 58 dis[v]=dis[u]+p[j].val; 59 pre[v]=j; 60 if(!vis[v]) 61 { 62 vis[v]=true; 63 q.push(v); 64 } 65 } 66 } 67 } 68 return dis[t]!=inf; 69 } 70 71 72 int mincost() 73 { 74 int ret=0,u; 75 while(spfa()) 76 { 77 u=pre[t]; 78 ret+=dis[t]; 79 while(u!=-1) 80 { 81 p[u].f--; 82 p[u^1].f++; 83 u=pre[p[u].u]; 84 } 85 } 86 return ret; 87 } 88 int main() 89 { 90 int case1; 91 scanf("%d",&case1); 92 for(int k=1; k<=case1; k++) 93 { 94 e=0; 95 memset(head,-1,sizeof(head)); 96 scanf("%d%d",&n,&m); 97 s=0; 98 t=2*n+1; 99 for(int i=1; i<=m; i++) 100 { 101 int a,b,c; 102 scanf("%d%d%d",&a,&b,&c); 103 add(a,b+n,1,c); 104 add(b,a+n,1,c); 105 } 106 for(int i=1; i<=n; i++) 107 { 108 add(s,i,1,0); 109 add(i+n,t,1,0); 110 } 111 int j; 112 int ans=mincost(); 113 for(j=head[s]; j!=-1; j=p[j].next) 114 if(p[j].f!=0) break; 115 if(j==-1) printf("Case %d: %d ",k,ans); 116 else printf("Case %d: NO ",k); 117 } 118 return 0; 119 }