洛谷 3376: 【模板】网络最大流

2018-03-27Chentiancai_nn?

题目描述

如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。

输入输出格式

输入格式:

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)

输出格式:

一行,包含一个正整数,即为该网络的最大流。

输入输出样例

输入样例#1:

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40

输出样例#1:

50

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=25

对于70%的数据:N<=200,M<=1000

对于100%的数据:N<=10000,M<=100000

样例说明:

题目中存在3条路径:

4–>2–>3,该路线可通过20的流量

4–>3,可通过20的流量

4–>2–>1–>3,可通过10的流量(边4–>2之前已经耗费了20的流量)

故流量总计20+20+10=50。输出50。

题解

是一道板子题,事实上只是来存代码的

代码

这是dinic的写法

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
ll x = 0,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}
return x*f;
}

const ll N = 10005,M = 200005;
ll n,m,s,t;
ll head[N],dep[N],cut[N],to[M],w[M],nxt[M],cnt = -1,cur[N];
inline void insert(ll x,ll y,ll z){to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; w[cnt] = z;}

inline ll dfs(ll x,ll flow){
if(x == t) return flow;
for(ll &i = cur[x];i != -1;i = nxt[i])
if(dep[to[i]] == dep[x]+1 && w[i] != 0){
ll di = dfs(to[i],min(flow,w[i]));
if(di > 0){w[i] -= di; w[i^1] += di; return di;}
}
return 0;
}

inline bool bfs(){
queue<ll> Q;
while(!Q.empty()) Q.pop();
memset(dep,0,sizeof(ll)*(n+1));
dep[s] = 1; Q.push(s);
do{
ll x = Q.front(); Q.pop();
for(ll i = head[x];i != -1;i = nxt[i])
if(dep[to[i]] == 0 && w[i] > 0){
dep[to[i]] = dep[x]+1;
Q.push(to[i]);
}
}while(!Q.empty());
return dep[t] > 0;
}

void dinic(){
ll ans = 0,d;
while(bfs()){
for(ll i = 1;i <= n;++i) cur[i] = head[i];
while((d = dfs(s,1e9))) ans += d;
}
printf("%lld\n", ans);
}

signed main(){
n = read(); m = read(); s = read(); t = read();
memset(head,-1,sizeof(ll)*(n+1));
for(ll i = 1;i <= m;++i){ll x = read(),y = read(),z = read(); insert(x,y,z);insert(y,x,0);}
dinic();
return 0;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close