HDU 3667 Transportation

LRJ老师白书2上讲网络流的例题，只不过没有给出题号，今天偶然发现了这道题。这里，费用随流量的变化而变化，且正好与流量的平方成正比，可以巧妙的将原本1,4,9,16,25的5种不同情况下的费用拆成5条容量为1的边，他们的费用分别为1,3,5,7,9。因为每次增广的时候，肯定会选择去走费用最小的边，比如说走了cost=1的边之后，如果要再走这条路，肯定会去走cost=3的边（不可能去走cost=5,7,9的边），这样一来，把两条边加起来就是flow=2,cost=4。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <queue>
 5 #define maxn 110
 6 #define maxm 50100
 7 #define INF 1<<30
 8 using namespace std;
 9 struct MCMF{
10     int src,sink,e,n;
11     int first[maxn];
12     int cap[maxm],cost[maxm],v[maxm],next[maxm];
13     bool flag;
14     void init(){
15         e = 0;
16         memset(first,-1,sizeof(first));
17     }
18 
19     void add_edge(int a,int b,int cc,int ww){
20         //printf("add:%d to %d,cap = %d,cost = %d
",a,b,cc,ww);
21         cap[e] = cc;cost[e] = ww;v[e] = b;
22         next[e] = first[a];first[a] = e++;
23         cap[e] = 0;cost[e] = -ww;v[e] = a;
24         next[e] = first[b];first[b] = e++;
25     }
26 
27     int d[maxn],pre[maxn],pos[maxn];
28     bool vis[maxn];
29 
30     bool spfa(int s,int t){
31         memset(pre,-1,sizeof(pre));
32         memset(vis,0,sizeof(vis));
33         queue<int> Q;
34         for(int i = 0;i <= n;i++)   d[i] = INF;
35         Q.push(s);pre[s] = s;d[s] = 0;vis[s] = 1;
36         while(!Q.empty()){
37             int u = Q.front();Q.pop();
38             vis[u] = 0;
39             for(int i = first[u];i != -1;i = next[i]){
40                 if(cap[i] > 0 && d[u] + cost[i] < d[v[i]]){
41                     d[v[i]] = d[u] + cost[i];
42                     pre[v[i]] = u;pos[v[i]] = i;
43                     if(!vis[v[i]])  vis[v[i]] = 1,Q.push(v[i]);
44                 }
45             }
46         }
47         return pre[t] != -1;
48     }
49 
50     int Mincost;
51     int Maxflow;
52 
53     int MinCostFlow(int s,int t,int nn){
54         Mincost = 0,Maxflow = 0,n = nn;
55         while(spfa(s,t)){
56             int min_f = INF;
57             for(int i = t;i != s;i = pre[i])
58                 if(cap[pos[i]] < min_f) min_f = cap[pos[i]];
59             Mincost += d[t] * min_f;
60             Maxflow += min_f;
61             for(int i = t;i != s;i = pre[i]){
62                 cap[pos[i]] -= min_f;
63                 cap[pos[i]^1] += min_f;
64             }
65         }
66         return Mincost;
67     }
68 };
69 MCMF g;
70 
71 int N,M,K;
72 
73 int main(){
74     while(scanf("%d%d%d",&N,&M,&K) != EOF){
75         g.init();
76         int S = 0,T = N;
77         for(int i = 0;i < M;i++){
78             int from,to,a,cap;
79             scanf("%d%d%d%d",&from,&to,&a,&cap);
80             for(int j = 1;j <= cap;j++)
81                 g.add_edge(from,to,1,a*(2*j-1));
82         }
83         g.add_edge(0,1,K,0);
84         int ans = g.MinCostFlow(S,T,T);
85         if(g.Maxflow != K)  ans = -1;
86         printf("%d
",ans);
87     }
88     return 0;
89 }

View Code