hdu 3435 A new Graph Game

  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\n",k,ans);
116         else printf("Case %d: NO\n",k);
117     }
118     return 0;
119 }