Day66：HDU5520Number Link最小费用最大流

注意一下，代码在C++会TLE，G++可以过
AC代码：（在G++上提交）
  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<queue>
  4 #include<string.h>
  5 using namespace std;
  6 #define inf 0x3f3f3f3f
  7 
  8 const int N=55*100;
  9 struct node
 10 {
 11     int to,nextt,cap,flow,cost;
 12 } e[N*N];
 13 bool book[N];
 14 int n,m,tot,s,t,z,pre[10*N],head[10*N],dist[10*N];
 15 
 16 void add(int u,int v,int cap,int cost)
 17 {
 18     e[tot].to=v;
 19     e[tot].nextt=head[u];
 20     e[tot].cap=cap;
 21     e[tot].cost=cost;
 22     e[tot].flow=0;
 23     head[u]=tot++;
 24 
 25     e[tot].to=u;
 26     e[tot].nextt=head[v];
 27     e[tot].cap=0;
 28     e[tot].cost=-cost;
 29     e[tot].flow=0;
 30     head[v]=tot++;
 31 
 32 }
 33 
 34 bool SPFA()
 35 {
 36     for(int i=0; i<=t; i++)
 37     {
 38         dist[i]=inf;
 39         book[i]=0;
 40         pre[i]=-1;
 41     }
 42     book[s]=1;
 43     dist[s]=0;
 44     queue<int>Q;
 45     Q.push(s);
 46     while(!Q.empty())
 47     {
 48         int u=Q.front();
 49         Q.pop();
 50         book[u]=0;
 51         for(int i=head[u]; i!=-1; i=e[i].nextt)
 52         {
 53             int v=e[i].to;
 54             if(e[i].cap>e[i].flow&&dist[v]>dist[u]+e[i].cost)
 55             {
 56                 dist[v]=dist[u]+e[i].cost;
 57                 pre[v]=i;
 58                 if(book[v]==0)
 59                 {
 60                     book[v]=1;
 61                     Q.push(v);
 62                 }
 63             }
 64         }
 65     }
 66     if(dist[t]!=inf)
 67         return 1;
 68     return 0;
 69 }
 70 
 71 int MCMF()
 72 {
 73     int flow=0,cost=0;
 74     while(SPFA())
 75     {
 76         int minn=inf;
 77         for(int i=pre[t]; i!=-1; i=pre[e[i^1].to])
 78             minn=min(minn,e[i].cap-e[i].flow);
 79         for(int i=pre[t]; i!=-1; i=pre[e[i^1].to])
 80         {
 81             e[i].flow+=minn;
 82             e[i^1].flow-=minn;
 83             cost+=e[i].cost*minn;
 84         }
 85         flow+=minn;
 86     }
 87     if(z==flow)
 88         return cost;
 89     return -1;
 90 }
 91 
 92 int main()
 93 {
 94     int T,pp=1,x,y;
 95     scanf("%d",&T);
 96     for(int i=1; i<=T; i++)
 97     {
 98         memset(head,-1,sizeof(head));
 99         scanf("%d %d",&n,&m);
100         y=n*m;
101         tot=z=0;
102         s=n*m*2+1,t=s+1;
103         for(int i=1; i<=n; i++)
104         {
105             for(int j=1; j<=m; j++)
106             {
107                 scanf("%d",&x);
108                 if(x==0)
109                 {
110                     add(s,(i-1)*m+j,1,0);
111                     z++;
112                     add((i-1)*m+j+y,t,1,0);
113                 }
114                 else
115                 {
116                     if(x%2==1)
117                     {
118                         add(s,(i-1)*m+j,1,0);
119                         z++;
120                     }
121                     else
122                         add((i-1)*m+j+y,t,1,0);
123                 }
124             }
125         }
126         for(int i=1; i<n; i++)
127         {
128             for(int j=1; j<=m; j++)
129             {
130                 scanf("%d",&x);
131                 add((i-1)*m+j,i*m+j+y,1,x);
132                 add(i*m+j,(i-1)*m+j+y,1,x);
133             }
134         }
135         for(int i=1; i<=n; i++)
136         {
137             for(int j=1; j<m; j++)
138             {
139                 scanf("%d",&x);
140                 add((i-1)*m+j,(i-1)*m+j+1+y,1,x);
141                 add((i-1)*m+j+1,(i-1)*m+j+y,1,x);
142             }
143         }
144         int ans=MCMF();
145         printf("Case #%d: %d\n",pp++,ans);
146     }
147     return 0;
148 }
View Code