【BZOJ】【1834】【ZJOI2010】Network 网络扩容
网络流/费用流这题……我一开始sb了。第一问简单的最大流……
第二问是要建费用流的图的……但是是在第一问的最大流跑完以后的残量网络上建，而不是重建……
我们令残量网络上原有的弧的费用全部为0（因为如果还能走就不需要扩容），而新加的弧容量为INF，费用为给定的w。
然后跑费用流就好了……这样建的话如果是不用扩容的边它就会自己走费用为0的弧。
RE/TLE：费用流扩展时的队列/边集数组的大小 M 开小了，队列长度从N改成M，M大小从20000改成50000后AC
1 /**************************************************************
2 Problem: 1834
3 User: Tunix
4 Language: C++
5 Result: Accepted
6 Time:36 ms
7 Memory:3824 kb
8 ****************************************************************/
9
10 //BZOJ 1834
11 #include<vector>
12 #include<cstdio>
13 #include<cstring>
14 #include<cstdlib>
15 #include<iostream>
16 #include<algorithm>
17 #define rep(i,n) for(int i=0;i<n;++i)
18 #define F(i,j,n) for(int i=j;i<=n;++i)
19 #define D(i,j,n) for(int i=j;i>=n;--i)
20 #define pb push_back
21 using namespace std;
22 inline int getint(){
23 int v=0,sign=1; char ch=getchar();
24 while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
25 while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
26 return v*sign;
27 }
28 const int N=1002,M=50000,INF=~0u>>2;
29 typedef long long LL;
30 /******************tamplate*********************/
31 int n,m,k,ans;
32 struct edge{int from,to,v,c,w;};
33 struct Net{
34 edge E,G;
35 int head,next,cnt;
36 void ins(int x,int y,int v,int c){
37 E[++cnt]=(edge){x,y,v,0,c};
38 next=head; head=cnt;
39 }
40 void add(int x,int y,int v,int c){
41 ins(x,y,v,c); ins(y,x,0,-c);
42 }
43 void Ins(int x,int y,int v,int c){
44 E[++cnt]=(edge){x,y,v,c,0};
45 next=head; head=cnt;
46 }
47 void Add(int x,int y,int v,int c){
48 Ins(x,y,v,c); Ins(y,x,0,-c);
49 }
50 int s,t,d,Q;
51 bool mklevel(){
52 F(i,1,n) d=-1;
53 d=0;
54 int l=0,r=-1;
55 Q[++r]=s;
56 while(l<=r){
57 int x=Q;
58 for(int i=head;i;i=next)
59 if (d.to]==-1 && E.v){
60 d.to]=d+1;
61 Q[++r]=E.to;
62 }
63 }
64 return d!=-1;
65 }
66 int dfs(int x,int a){
67 if (x==t) return a;
68 int flow=0;
69 for(int i=head;i && flow<a;i=next)
70 if (E.v && d.to]==d+1){
71 int f=dfs(E.to,min(a-flow,E.v));
72 E.v-=f;
73 E.v+=f;
74 flow+=f;
75 }
76 if (!flow) d=-1;
77 return flow;
78 }
79 void Dinic(){
80 while(mklevel()) ans+=dfs(s,INF);
81 }
82 int from;
83 bool inq;
84 bool spfa(){
85 int l=0,r=-1;
86 F(i,0,n) d=INF;
87 d=0; Q[++r]=s; inq=1;
88 while(l<=r){
89 int x=Q;
90 inq=0;
91 for(int i=head;i;i=next)
92 if (E.v>0 && d+E.c<d.to]){
93 d.to]=d+E.c;
94 from.to]=i;
95 if (!inq.to]){
96 Q[++r]=E.to;
97 inq.to]=1;
98 }
99 }
100 }
101 return d!=INF;
102 }
103 void mcf(){
104 int x=INF;
105 for(int i=from;i;i=from.from])
106 x=min(x,E.v);
107 for(int i=from;i;i=from.from]){
108 E.v-=x;
109 E.v+=x;
110 ans+=x*E.c;
111 }
112 }
113 void build(){
114 int t=cnt;
115 for(int i=2;i<=t;i+=2)
116 Add(E.from,E.to,INF,E.w);
117 }
118 void init(){
119 n=getint(); m=getint(); k=getint();
120 int x,y,z,w;
121 cnt=1;
122 s=1; t=n;
123 F(i,1,m){
124 x=getint(); y=getint(); z=getint(); w=getint();
125 add(x,y,z,w);
126 }
127 Dinic(); build();
128 printf("%d ",ans);
129 ans=0; s=0;
130 ins(s,1,k,0);
131 while(spfa()) mcf();
132 printf("%d\n",ans);
133 }
134 }G1;
135
136 int main(){
137 #ifndef ONLINE_JUDGE
138 freopen("1834.in","r",stdin);
139 freopen("1834.out","w",stdout);
140 #endif
141 G1.init();
142 return 0;
143 }
View Code
1834: network 网络扩容
Time Limit: 3 Sec Memory Limit: 64 MB
Submit: 1976 Solved: 986
Description
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。
Input
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
Output
输出文件一行包含两个整数，分别表示问题1和问题2的答案。
Sample Input
5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
Sample Output
13 19
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
HINT
Source
Day1
文档来源：51CTO技术博客https://blog.51cto.com/u_15320872/3267114
页:
[1]