hdu6118 度度熊的交易计划

思路：
将生产和运输费用视作产出，将销售获利视作投入，计算最小费用可行流（不一定是最大流）。注意片区之间的高速公路是双向边。
实现：
  1 #include <iostream>
  2 #include <vector>
  3 #include <queue>
  4 using namespace std;
  5 
  6 const int INF = 0x3f3f3f3f;
  7 const int MAXV = 505;
  8 const int MAXE = 1005;
  9 
 10 typedef pair<int, int> P;
 11 struct edge
 12 {
 13     int to, cap, cost, rev;   
 14 };
 15 vector<edge> G[MAXV];
 16 int V, E;
 17 int dist[MAXV], prevv[MAXV], preve[MAXE];
 18 
 19 void add_edge(int from, int to, int cap, int cost)
 20 {
 21     edge e;
 22     e.to = to;
 23     e.cap = cap;
 24     e.cost = cost;
 25     e.rev = G[to].size();
 26     G[from].push_back(e);
 27     e.to = from;
 28     e.cap = 0;
 29     e.cost = -cost;
 30     e.rev = G[from].size() - 1;
 31     G[to].push_back(e);
 32 }
 33  
 34 int min_cost_flow(int s, int t, int f)
 35 {
 36     int res = 0;
 37     while (f > 0)
 38     {
 39         fill(dist, dist + V + 2, INF);
 40         dist[s] = 0;
 41         bool upd = true;
 42         while (upd)
 43         {
 44             upd = false;
 45             for (int v = 0; v <= V + 1; v++)
 46             {
 47                 if (dist[v] == INF) continue;
 48                 for (int i = 0; i < G[v].size(); i++)
 49                 {
 50                     edge& e = G[v][i];
 51                     if (e.cap > 0 && dist[e.to] > dist[v] + e.cost)
 52                     {
 53                         dist[e.to] = dist[v] + e.cost;
 54                         prevv[e.to] = v;
 55                         preve[e.to] = i;
 56                         upd = true;
 57                     }
 58                 }
 59             }
 60         }
 61         if (dist[t] == INF) break;
 62         if (dist[t] > 0) break;
 63         int d = f;
 64         for (int v = t; v != s; v = prevv[v])
 65         {
 66             d = min(d, G[prevv[v]][preve[v]].cap);
 67         }
 68         f -= d;
 69         res += d * dist[t];
 70         for (int v = t; v != s; v = prevv[v])
 71         {
 72             edge& e = G[prevv[v]][preve[v]];
 73             e.cap -= d;
 74             G[v][e.rev].cap += d;
 75         }
 76     }
 77     return res;
 78 }
 79 int main()
 80 {
 81     while (cin >> V >> E)
 82     {
 83         int a, b, c, d, u, v, k;
 84         for (int i = 0; i < MAXV; i++) G[i].clear();
 85         for (int i = 1; i <= V; i++)
 86         {
 87             cin >> a >> b >> c >> d;
 88             add_edge(0, i, b, a);
 89             add_edge(i, V + 1, d, -c);
 90         }
 91         for (int i = 1; i <= E; i++)
 92         {
 93             cin >> u >> v >> k;
 94             add_edge(u, v, INF, k);
 95             add_edge(v, u, INF, k);
 96         }
 97         cout << -min_cost_flow(0, V + 1, INF) << endl;
 98     }
 99     return 0;
100 }