【最大流+费用流】网络扩容

传送门:CodeVS1362

居然是ZJOI,可能是假的


思路:先家不扩容的边,跑最大流;再加扩容的边,跑费用流。就没了。


一切尽在代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 100000000
#define min(x,y) ((x)<(y)?(x):(y))
int n,m,k,s,t,max_flow,tot,cost,t1[10030],t2[10030],t3[10030],t4[10030];
int level[1030],head[1030],iter[1030],q[1030],dis[1030];
int pre_v[1030],pre_e[1030],pre_f[1030];
bool vis[1030];
struct edge{int v,cap,rev,cost,nxt;}E[20030];
void add(int x,int y,int xx,int yy){
E[++tot].v=y; E[tot].cap=xx; E[tot].cost=yy;
E[tot].rev=tot+1; E[tot].nxt=head[x]; head[x]=tot;
E[++tot].v=x; E[tot].cap=0; E[tot].cost=-yy;
E[tot].rev=tot-1; E[tot].nxt=head[y]; head[y]=tot;
}
void bfs(int s){
memset(level,-1,sizeof level); level[s]=0;
int tt=0,ww=1; q[1]=s;
while (tt<ww){
tt++;
int v=q[tt];
for (int i=head[v];i;i=E[i].nxt){
edge &e=E[i];
if (e.cap>0 && level[e.v]<0){
level[e.v]=level[v]+1;
q[++ww]=e.v;
}
}
}
}
int dfs(int v,int t,int f){
if (v==t) return f;
for (int &i=iter[v];i;i=E[i].nxt){
edge &e=E[i];
if (e.cap>0 && level[v]<level[e.v]){
int d=dfs(e.v,t,min(f,e.cap));
if (d>0){
e.cap-=d; E[e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int dinic(int s,int t){
int flow=0;
for (;;){
bfs(s);
if (level[t]<0) break;
for (int i=1;i<=n;i++) iter[i]=head[i];
int f=0;
while ((f=dfs(s,t,INF))>0) flow+=f;
}
return flow;
}
int spfa(int s,int t){
int cost=0;
for (;;){
for (int i=1;i<=n;i++) dis[i]=INF;
int tt=0,ww=1; q[1]=s; vis[s]=1; pre_f[s]=INF;
while (tt<ww){
tt++;
int v=q[tt]; vis[v]=0;
for (int i=head[v];i;i=E[i].nxt){
edge &e=E[i];
if (e.cap>0)
if (dis[e.v]>dis[v]+e.cost){
dis[e.v]=dis[v]+e.cost;
pre_v[e.v]=v; pre_e[e.v]=i; pre_f[e.v]=min(pre_f[v],e.cap);
if (!vis[e.v]){vis[e.v]=1; q[++ww]=e.v;}
}
}
}
if (dis[t]==INF) return cost;
for (int i=t;i;i=pre_v[i]){
edge &e=E[pre_e[i]];
e.cap-=pre_f[t]; E[e.rev].cap+=pre_f[t];
cost+=pre_f[t]*e.cost;
}
}
}
int cost_flow(int s,int t){
s=0; dis[s]=0; add(s,1,k,0);
for (int i=1;i<=m;i++) add(t1[i],t2[i],INF,t4[i]);
return spfa(s,t);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
s=1; t=n;
for (int i=1;i<=m;i++){
scanf("%d%d%d%d",&t1[i],&t2[i],&t3[i],&t4[i]);
add(t1[i],t2[i],t3[i],0);
}
max_flow=dinic(s,t);
cost=cost_flow(s,t);
printf("%d %d\n",max_flow,cost);
return 0;
}