UVa1486 Transportation（最小费用最大流）

题目大概说有n个城市，m条有向边连着它们，每条边都有两个属性一个是ai一个是ci，ai表示运送x单位货物时花费ai*x*x的价钱，ci表示边最多能运送的货物数量（<=5）。问从城市1运送k单位货物到城市n的最少代价。

这种单位费用不固定的费用流很经典的建图方式就是拆边，这题把边拆成ci条，每条单位费用分别为ai*1、ai*3、ai*5、ai*7。。这样如果只有一单位流量通过这条边那么费用就是ai，如果两单位流量那么费用就是ai*1+ai*3=ai*2*2 。。。

那么这题就迎刃而解了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 111
 7 #define MAXM 55555
 8 #define INF (1<<30)
 9 
10 struct Edge{
11     int v,cap,cost,next;
12 }edge[MAXM];
13 int vs,vt,NV,NE,head[MAXN];
14 void addEdge(int u,int v,int cap,int cost){
15     edge[NE].v=v; edge[NE].cap=cap; edge[NE].cost=cost;
16     edge[NE].next=head[u]; head[u]=NE++;
17     edge[NE].v=u; edge[NE].cap=0; edge[NE].cost=-cost;
18     edge[NE].next=head[v]; head[v]=NE++;
19 }
20 
21 int d[MAXN],pre[MAXN];
22 bool inque[MAXN];
23 bool SPFA(){
24     for(int i=0; i<NV; ++i){
25         d[i]=INF; inque[i]=0;
26     }
27     d[vs]=0; inque[vs]=1;
28     queue<int> que;
29     que.push(vs);
30     while(!que.empty()){
31         int u=que.front(); que.pop();
32         for(int i=head[u]; i!=-1; i=edge[i].next){
33             int v=edge[i].v;
34             if(edge[i].cap && d[v]>d[u]+edge[i].cost){
35                 d[v]=d[u]+edge[i].cost;
36                 pre[v]=i;
37                 if(!inque[v]){
38                     inque[v]=1;
39                     que.push(v);
40                 }
41             }
42         }
43         inque[u]=0;
44     }
45     return d[vt]!=INF;
46 }
47 int mxflow;
48 int MCMF(){
49     mxflow=0;
50     int res=0;
51     while(SPFA()){
52         int flow=INF,cost=0;
53         for(int u=vt; u!=vs; u=edge[pre[u]^1].v){
54             flow=min(flow,edge[pre[u]].cap);
55         }
56         mxflow+=flow;
57         for(int u=vt; u!=vs; u=edge[pre[u]^1].v){
58             edge[pre[u]].cap-=flow;
59             edge[pre[u]^1].cap+=flow;
60             cost+=edge[pre[u]].cost;
61         }
62         res+=cost*flow;
63     }
64     return res;
65 }
66 
67 int main(){
68     int n,m,k;
69     while(~scanf("%d%d%d",&n,&m,&k)){
70         vs=0; vt=n; NV=vt+1; NE=0;
71         memset(head,-1,sizeof(head));
72         addEdge(vs,1,k,0);
73 
74         int u,v,a,c;
75         while(m--){
76             scanf("%d%d%d%d",&u,&v,&a,&c);
77             for(int i=1; i<=c; ++i){
78                 addEdge(u,v,1,a*(2*i-1));
79             }
80         }
81         int res=MCMF();
82         if(mxflow!=k) puts("-1");
83         else printf("%d
",res);
84     }
85     return 0;
86 }