POJ 2516 Minimum Cost 最小费用最大流费用流

题意跟题目输入这里写的很明白：http://blog.csdn.net/lyy289065406/article/details/6742534
无非就是k种物品，直接对每种物品进行一次最大流就OK了~
View Code
  1 #include <iostream>
  2 #include <queue>
  3 #include <iostream>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <vector>
  7 using namespace std;
  8 const int maxn = 350;
  9 const int inf = 10000000;
 10 struct node
 11 {
 12     int u,v,cap,flow,cost;
 13 };
 14 
 15 vector<struct node> edge;
 16 vector<int> g[maxn];
 17 
 18 void init(int n)
 19 {
 20     int i;
 21     for(i = 0;i <= n;i++)
 22     g[i].clear();
 23     edge.clear();
 24 
 25     return ;
 26 }
 27 void addedge(int u,int v,int cap,int flow,int cost)
 28 {
 29     edge.push_back((struct node){u,v,cap,flow,cost});
 30     edge.push_back((struct node){v,u,0,flow,-cost});
 31     int m;
 32     m = edge.size();
 33     g[u].push_back(m-2);
 34     g[v].push_back(m-1);
 35 }
 36 int shop[55][55];
 37 int supply[55][55];
 38 int vis[maxn],a[maxn],pre[maxn],dis[maxn];
 39 int spfa(int s,int t,int n,int &flow,int & cost)
 40 {
 41     int i;
 42     queue <int >q;
 43     for(i = 0;i <= n;i++)
 44     dis[i] = inf;
 45     dis[s] = 0;
 46     pre[s] = 0;memset(vis,0,sizeof(vis));
 47     vis[s] = 1;
 48     a[s] = inf;
 49 
 50     int u,v;
 51     q.push(s);
 52 
 53     while(!q.empty())
 54     {
 55         u = q.front();
 56         q.pop();
 57         vis[u] = 0;
 58 
 59         for(i = 0;i < g[u].size();i++)
 60         {
 61             struct node& e = edge[g[u][i]];
 62             v = e.v;
 63             if(e.cap > e.flow &&dis[v] > dis[u] + e.cost)
 64             {
 65                 dis[v] = dis[u]+e.cost;
 66                 a[v] = min(a[u],e.cap-e.flow);
 67                 pre[v] = g[u][i];
 68                 if(!vis[v])
 69                 {
 70                     vis[v] = 1;
 71                     q.push(v);
 72                 }
 73             }
 74         }
 75     }
 76     if(dis[t] == inf)
 77     return 0;
 78 
 79     flow += a[t];
 80     cost += dis[t]*a[t];
 81 
 82     u = t;
 83     while( u != s)
 84     {
 85         edge[pre[u]].flow += a[t];
 86         edge[pre[u]^1].flow -= a[t];
 87         u = edge[pre[u]].u;
 88     }
 89     return 1;
 90 }
 91 
 92 int MCMF(int s,int t,int n)
 93 {
 94     int flow = 0,cost = 0;
 95     while(spfa(s,t,n,flow,cost));
 96     return cost;
 97 }
 98 int main()
 99 {
100     int n,m,k;
101     while (scanf("%d %d %d",&n,&m,&k)&&(n||m||k))
102     {
103         int i,j;
104         for(i = 1;i <= n;i++)
105         {
106             for(j = 1;j <= k;j++)
107             cin>>shop[i][j];
108         }
109 
110         for(j = 1;j <= m;j++)
111         for(i = 1;i <= k;i++)
112         cin>>supply[j][i];
113 
114         int leap = 1;
115         for(i = 1;i <= k;i++)
116         {
117             int need,support;
118             need = support = 0;
119 
120             for(j = 1;j <= m;j++)
121             support += supply[j][i];
122 
123             for(j = 1;j <= n;j++)
124             need += shop[j][i];
125 
126             if(support < need)
127             {
128                 leap = 0;
129                 break;
130             }
131         }
132         int ii;
133         int ans = 0;
134         for(ii = 1;ii <= k;ii++)
135         {
136             init(n+m+2);
137             for(i = 1;i <= m;i++)
138             addedge(0,i,supply[i][ii],0,0);
139 
140             for(i = 1;i <= n;i++)
141             addedge(i+m,n+m+1,shop[i][ii],0,0);
142 
143             for(i = 1;i <= n;i++)
144             for(j = 1;j <= m;j++)
145             {
146                 int cost;
147                 cin>>cost;
148                 addedge(j,i+m,inf,0,cost);
149             }
150             if(leap)
151             ans += MCMF(0,n+m+1,n+m+2);
152         }
153         if(leap)
154         cout<<ans<<endl;
155         else
156         puts("-1");
157 
158     }
159 
160     return 0;
161 }
POJ 2516 Minimum Cost 最小费用最大流 费用流

POJ 2516 Minimum Cost 最小费用最大流费用流
