HDU 3667 费用流拆边 Transportation

题意：

有N个城市，M条有向道路，要从1号城市运送K个货物到N号城市。

每条有向道路<u, v>运送费用和运送量的平方成正比，系数为a_i

而且每条路最多运送C_i个货物，求最小费用。

分析：

拆边，每条边拆成费用为a, 3a, 5a的边，这样就能保证每条边的费用和流量的平方成正比。

因为最多运送K个货物，所以增加一个源点和城市1连一条容量为K费用为0的边。

跑一边最小费用最大流，如果满流才有解。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <vector>
  7 using namespace std;
  8 
  9 const int maxn = 100 + 10;
 10 const int INF = 0x3f3f3f3f;
 11 
 12 struct Edge
 13 {
 14     int from, to, cap, flow, cost;
 15     Edge(int u, int v, int cap, int flow, int cost):from(u), to(v), cap(cap), flow(flow), cost(cost) {}
 16 };
 17 
 18 int n, s, t, m, k;
 19 vector<Edge> edges;
 20 vector<int> G[maxn];
 21 
 22 void init(int n)
 23 {
 24     for(int i = 0; i < n; i++) G[i].clear();
 25     edges.clear();
 26 }
 27 
 28 void AddEdge(int u, int v, int cap, int cost)
 29 {
 30     edges.push_back(Edge(u, v, cap, 0, cost));
 31     edges.push_back(Edge(v, u, 0, 0, -cost));
 32     int m = edges.size();
 33     G[u].push_back(m - 2);
 34     G[v].push_back(m - 1);
 35 }
 36 
 37 bool inq[maxn];
 38 int p[maxn], d[maxn], a[maxn];
 39 
 40 bool SPFA()
 41 {
 42     memset(d, 0x3f, sizeof(d));
 43     d[s] = 0;
 44     queue<int> Q;
 45     Q.push(s);
 46     memset(inq, false, sizeof(inq));
 47     inq[s] = true;
 48     memset(p, -1, sizeof(p));
 49     a[s] = INF;
 50 
 51     while(!Q.empty())
 52     {
 53         int u = Q.front(); Q.pop(); inq[u] = false;
 54         for(int i = 0; i < G[u].size(); i++)
 55         {
 56             Edge& e = edges[G[u][i]];
 57             int v = e.to;
 58             if(e.cap > e.flow && d[u] + e.cost < d[v])
 59             {
 60                 d[v] = d[u] + e.cost;
 61                 p[v] = G[u][i];
 62                 a[v] = min(a[u], e.cap - e.flow);
 63                 if(!inq[v]) { inq[v] = true; Q.push(v); }
 64             }
 65         }
 66     }
 67 
 68     return d[t] < INF;
 69 }
 70 
 71 int Maxf;
 72 
 73 int Mincost()
 74 {
 75     int cost = 0;
 76     Maxf = 0;
 77     while(SPFA())
 78     {
 79         Maxf += a[t];
 80         cost += a[t] * d[t];
 81         int u = t;
 82         while(u != s)
 83         {
 84             edges[p[u]].flow += a[t];
 85             edges[p[u]^1].flow -= a[t];
 86             u = edges[p[u]].from;
 87         }
 88     }
 89     return cost;
 90 }
 91 
 92 int main()
 93 {
 94     while(scanf("%d%d%d", &n, &m, &k) == 3)
 95     {
 96         init(n + 1);
 97 
 98         s = 0, t = n;
 99         AddEdge(s, 1, k, 0);
100 
101         while(m--)
102         {
103             int u, v, a, C;
104             scanf("%d%d%d%d", &u, &v, &a, &C);
105             for(int i = 0; i < C; i++)
106                 AddEdge(u, v, 1, a * (i * 2 + 1));
107         }
108 
109         int cost = Mincost();
110         if(Maxf < k) puts("-1");
111         else printf("%d
", cost);
112     }
113 
114     return 0;
115 }

代码君

HDU 3667 费用流 拆边 Transportation

HDU 3667 费用流拆边 Transportation