POJ 2516 【最小费用最大流】.cpp

题意：

给出供应商供应的商品量和商家需要的商品量以及某个商品在供应商和商家之间的消耗量

问商家是否能得到想要的商品量

如果可以那怎么安排才是最少花费

输入：

　　给出 n m k 表示有n个商家 m个供应商 k个商品

　　接下来n行有k个数值表示第 ni 个商家需要的第k个商品的商品量为ki

　　接下来m行有k个数值表示第 mi 个商家需要的第k个商品的商品量为ki

　　接下来的k个n*m矩阵表示第 ki 个商品又第 mi 个供应商给第 ni 个商家的消耗

思路：

　很明显的最小费用最大流..

　　但是建图很特别..

　　先求出每个商品的最小花费然后加起来

　　固定了超级源点和每个供应商之间的边(容量为供应商第k个商品的库存, 花费为0) 以及每个商家和超级汇点之间的边(容量为商家所需要的第k个商品的量, 花费为0)

　　然后每次得到第k个商品在商家和供应商之间的消耗

　　建图

　　求出第k个商品在商家和供应商之间的最小费用最大流..

　　求和..

Tips：

　　建图的时候..

　　对反向边要增加负消耗量的边..

Code：

View Code

  1 #include <stdio.h>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 #define clr(x) memset(x, 0, sizeof(x))
  6 const int INF = 0x1f1f1f1f;
  7 
  8 const int MAXN = 210;
  9 int cap[MAXN][MAXN], flow[MAXN][MAXN];
 10 int cost[MAXN][MAXN];
 11 int n, f, c;
 12 
 13 bool vis[MAXN];
 14 int que[MAXN], pre[MAXN], dis[MAXN];
 15 
 16 bool spfa(int s, int e)
 17 {
 18     int front = 0, rear = 0;
 19     for(int u = 0; u <= n; ++u) {
 20         if(u == s) {
 21             que[rear++] = u;
 22             dis[u] = 0;
 23             vis[u] = true;
 24         } else {
 25             dis[u] = INF;
 26             vis[u] = false;
 27         }
 28     }
 29     while(front != rear) {
 30         int u = que[front++];
 31         vis[u] = false;
 32         if(front >= MAXN) front = 0;
 33         for(int v = 0; v <= n; ++v) {
 34             if(cap[u][v] > flow[u][v] && dis[v] > dis[u]+cost[u][v]) {
 35                 dis[v] = dis[u]+cost[u][v];
 36                 pre[v] = u;
 37                 if(!vis[v]) {
 38                     vis[v] = true;
 39                     que[rear++] = v;
 40                     if(rear >= MAXN) rear = 0;
 41                 }
 42             }
 43         }
 44     }
 45     if(dis[e] >= INF) return false;
 46     else return true;
 47 }
 48 
 49 void min_c_f(int s, int e)
 50 {
 51     clr(flow);
 52     c = f = 0;
 53     while(spfa(s, e)) {
 54         int _min = INF;
 55         for(int u = e; u != s; u=pre[u])
 56             _min = min(_min, cap[pre[u]][u]-flow[pre[u]][u]);
 57         for(int u = e; u != s; u = pre[u]) {
 58             flow[pre[u]][u] += _min;
 59             flow[u][pre[u]] -= _min;
 60         }
 61         f += dis[e]*_min;
 62         c += _min;
 63     }
 64 }
 65 
 66 int order[MAXN][MAXN], sup[MAXN][MAXN];
 67 int sum[MAXN];
 68 
 69 int main()
 70 {
 71     int nn, mm, kk;
 72     int i, j, k;
 73     int ans, t;
 74     bool flag;
 75     while(scanf("%d %d %d", &nn, &mm, &kk) != EOF)
 76     {
 77         if(nn == 0 && mm == 0 && kk == 0) break;
 78         ans = 0, n = nn+mm+1;
 79         clr(sum), clr(cap), clr(flow), clr(cost);
 80         flag = true;
 81 
 82         for(i = 0; i < nn; ++i)
 83         for(j = 0; j < kk; ++j) {
 84             scanf("%d", &order[i][j]);
 85             sum[j] += order[i][j];
 86         }
 87 
 88         for(i = 0; i < mm; ++i)
 89         for(j = 0; j < kk; ++j)
 90             scanf("%d", &sup[i][j]);
 91 
 92         for(i = 1; i <= mm; ++i)
 93             for(j = mm+1; j <= nn+mm; ++j)
 94                 cap[i][j] = INF;
 95 
 96         for(int i = 0; i < kk; ++i) {
 97             for(int j = mm+1; j <= mm+nn; ++j)
 98             for(int k = 1; k <= mm; ++k) {
 99                 scanf("%d", &cost[k][j]);
100                 cost[j][k] = -cost[k][j];       ///!!!!
101             }
102             if(!flag) continue;
103 
104             for(int j = 1; j <= mm; ++j)
105                 cap[0][j] = sup[j-1][i];
106             for(int j = 1; j <= nn; ++j)
107                 cap[j+mm][n] = order[j-1][i];
108 
109             min_c_f(0, n);
110             if(c < sum[i]) flag = false;
111             else ans += f;
112         }
113 
114         if(!flag) puts("-1");
115         else printf("%d\n", ans);
116     }
117     return 0;
118 }

题目链接：http://poj.org/problem?id=2516