POJ2516

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

解题思路：

　　最小费用最大流，这个没什么疑问。但此题小难点在于读题，大难点在于建图。

　　首先，供应量小于需求量的时候直接输出“-1”。

　　供大于或等于求的情况，一开始我将每个供应商和每个购买人都拆成K个点，将所有供应商的点和超级源点相连，流量限制为库存量，费用为0；将所有购买人的点和超级汇点相连，流量限制为购买量，费用为0；而购买方和供应方之间的连线的流量限制则为inf，费用如题目中给出的。但是这种建图方式一直T......一度绝望到以为我的模板有问题，修修补补了半天，还是T......上网查了题解，发现大家的建图方式跟我不一样：大家都是把根据K种商品，建K个图逐一求最小费用最大流，答案就是K个图的最小费用之和。稍微改了一下，AC.......醉........至于为什么........我也不太懂，容我明天去问问师兄。

AC代码：

 #include <cstdio>

 #include <vector>

 #include <queue>

 #include <cstring>

 using namespace std;

 const int MAXN = ;

 const int MAXM = ;

 const int INF = 0x3f3f3f3f;

 struct rec {

     int from, to, cost, cap;

 }r[][];

 struct Edge {

     int to, next, cap, flow, cost;

 }edge[MAXM];

 int head[MAXN], tol;

 int pre[MAXN], dis[MAXN];

 bool vis[MAXN];

 int N;

 void init(int n) {

     N = n;

     tol = ;

     memset(head, -, sizeof(head));

 }

 void addedge(int u, int v, int cap, int cost) {

     edge[tol].to = v;

     edge[tol].cap = cap;

     edge[tol].cost = cost;

     edge[tol].flow = ;

     edge[tol].next = head[u];

     head[u] = tol++;

     edge[tol].to = u;

     edge[tol].cap = ;

     edge[tol].cost = -cost;

     edge[tol].flow = ;

     edge[tol].next = head[v];

     head[v] = tol++;

 }

 bool spfa(int s, int t) {

     queue<int>q;

     for (int i = ; i < N; i++) {

         dis[i] = INF;

         vis[i] = false;

         pre[i] = -;

     }

     dis[s] = ;

     vis[s] = true;

     q.push(s);

     while (!q.empty()) {

         int u = q.front();

         q.pop();

         vis[u] = false;

         for (int i = head[u]; i != -; i = edge[i].next) {

             int v = edge[i].to;

             if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost){

                 dis[v] = dis[u] + edge[i].cost;

                 pre[v] = i;

                 if (!vis[v]){

                     vis[v] = true;

                     q.push(v);

                 }

             }

         }

     }

     if (pre[t] == -)    return false;

     else    return true;

 }

 int minCostMaxflow(int s, int t, int &cost){

     int flow = ;

     cost = ;

     while (spfa(s, t)) {

         int Min = INF;

         for (int i = pre[t]; i != -; i = pre[edge[i ^ ].to]) {

             if (Min > edge[i].cap - edge[i].flow)

                 Min = edge[i].cap - edge[i].flow;

         }

         for (int i = pre[t]; i != -; i = pre[edge[i ^ ].to]) {

             edge[i].flow += Min;

             edge[i ^ ].flow -= Min;

             cost += edge[i].cost * Min;

         }

         flow += Min;

     }

     return flow;

 }

 int sup[][], buy[][];

 int main() {

     int N, M, K;

     int need[], have[];

     while (scanf("%d%d%d", &N, &M, &K) ==  && (N || M || K)) {

         memset(need, , sizeof(need));

         memset(have, , sizeof(have));

         int c;

         for (int i = ; i <= N; i++) {

             for (int j = ; j <= K; j++) {

                 scanf("%d", &c);

                 need[j] += c;

                 buy[j][i] = c;

             }

         }

         for (int i = ; i <= M; i++) {

             for (int j = ; j <= K; j++) {

                 scanf("%d", &c);

                 have[j] += c;

                 sup[j][i] = c;

             }

         }

         bool yes = true;

         for (int j = ; j <= K; j++) {

             if (have[j]<need[j]) yes = false;

         }

         int ans = ;

         for (int k = ; k <= K; k++) {

             if (yes)

                 init(N + M + );

             for (int i = ; i <= N; i++) {

                 for (int j = ; j <= M; j++) {

                     scanf("%d", &c);

                     if (yes)

                         addedge(j, M + i, INF, c);

                 }

             }

             if (yes) {

                 for (int i = ; i <= M; i++)

                     addedge(, i, sup[k][i], );

                 for (int i = ; i <= N; i++)

                     addedge(M + i, N + M + , buy[k][i], );

                 int cost;

                 minCostMaxflow(, N + M + , cost);

                 ans += cost;

             }

         }

         if (!yes)

             printf("-1\n");

         else

             printf("%d\n", ans);

     }

     return ;

 }

巴特西

POJ2516

最新文章

热门文章