[ZJOI2010]网络扩容

题目描述

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。

输入输出格式

输入格式：

输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

输出格式：

输出文件一行包含两个整数，分别表示问题1和问题2的答案。

输入输出样例

输入样例#1：

输出样例#1：

13 19

说明

30%的数据中，N<=100

100%的数据中，N<=1000，M<=5000，K<=10

数据规模并不准。

思路：最大流+构图+费用流

还是看了题解，构图的精髓没有掌握啊。

最大流：s->(q->z +w 0 -0 0)->t

费用流：ys-> (ys-> +k 0 -0 0)->s->残余免费网络||(q->z +k f -0 -f)->t

代码实现：

 1 #include<cstdio>
 2 #include<cstring>
 3 const int inf=2139062143;
 4 const int maxn=6000;
 5 const int maxm=500000;
 6 int n,m,k,s,t,ys,tw,tc;
 7 int eq[maxn],ez[maxn],ew[maxn],ef[maxn];
 8 int a,b,c,d;
 9 inline int min_(int x,int y){return x<y?x:y;}
10 int h[maxn],hs=1;
11 struct edge{int s,n,w,f;}e[maxm];
12 void add(int q,int z,int w,int f){
13     e[++hs]=(edge){z,h[q],w,f},h[q]=hs;
14     e[++hs]=(edge){q,h[z],0,-f},h[z]=hs;
15 }
16 int de[maxn],q[maxm],head,tail;
17 bool bfs(){
18     memset(de,0,sizeof(de));
19     head=tail=0;
20     q[head++]=s,de[s]=1;
21     while(head>tail){
22         a=q[tail++];
23         for(int i=h[a];i;i=e[i].n)
24         if(!de[e[i].s]&&e[i].w){
25             de[e[i].s]=de[a]+1;
26             if(e[i].s==t) return true;
27             q[head++]=e[i].s;
28         }
29     }
30     return false;
31 }
32 int ap(int k,int w){
33     if(k==t) return w;
34     int uw=w;
35     for(int i=h[k];uw&&i;i=e[i].n)
36     if(de[e[i].s]==de[k]+1&&e[i].w){
37         int nw=ap(e[i].s,min_(uw,e[i].w));
38         if(nw) e[i].w-=nw,e[i^1].w+=nw,uw-=nw;
39         else de[e[i].s]=0;
40     }
41     return w-uw;
42 }
43 void Dinic(){while(bfs()) tw+=ap(s,inf);}
44 int w[maxn],pp[maxn],pw[maxn];
45 void spfa(){
46     memset(w,0x7f,sizeof(w));
47     head=tail=0;
48     q[head++]=ys,w[ys]=0;
49     while(head>tail){
50         a=q[tail++];
51         for(int i=h[a];i;i=e[i].n)
52         if(e[i].w&&1ll+w[a]+e[i].f-1<w[e[i].s]){
53             pp[e[i].s]=a,pw[e[i].s]=i;
54             q[head++]=e[i].s;
55             w[e[i].s]=w[a]+e[i].f;
56         }
57     }
58 }
59 int mcmf(int k,int v){
60     if(k==ys) return v;
61     int ret=mcmf(pp[k],min_(e[pw[k]].w,v));
62     e[pw[k]].w-=ret;
63     e[pw[k]^1].w+=ret;
64     return ret;
65 }
66 bool Cost(){
67     spfa();
68     if(w[t]==inf) return false;
69     tc+=w[t]*mcmf(t,inf);
70 }
71 int main(){
72     freopen("networkzj2010.in","r",stdin);
73     freopen("networkzj2010.out","w",stdout);
74     scanf("%d%d%d",&n,&m,&k);
75     s=1,t=n;
76     for(int i=1;i<=m;i++){
77         scanf("%d%d%d%d",&eq[i],&ez[i],&ew[i],&ef[i]);
78         add(eq[i],ez[i],ew[i],0);
79     }
80     Dinic();
81     ys=0,add(ys,s,k,0);
82     for(int i=1;i<=m;i++) add(eq[i],ez[i],k,ef[i]);
83     while(Cost());
84     printf("%d %d
",tw,tc);
85     return 0;
86 }

题目来源：洛谷