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

网络流

传送门：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;
}