题目描述
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）
输出
一行，包含一个正整数，即为该网络的最大流。
样例输入
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40样例输出
50数据规模：
对于30%的数据：N<=10，M<=25
对于70%的数据：N<=200，M<=1000
对于100%的数据：N<=10000，M<=100000
网络流的模板题。汇总一些增广路算法。（Ford-Fulkerson, Edmond-Karp, Dinic, ISAP）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std; struct edge {
int to,cap,rev;
}; const int maxn=, INF=0x7F7F7F7F;
int n,m;
vector <edge> G[maxn+]; edge make_edge(int to, int cap, int rev) {
edge x;
x.to=to, x.cap=cap, x.rev=rev;
return x;
} void add_edge(int from, int to, int cap) {
G[from].push_back(make_edge(to,cap,G[to].size()));
G[to].push_back(make_edge(from,,G[from].size()-));
} void init() {
for (int i=; i<=m; i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
}
} namespace Ford_Fulkerson {
bool used[maxn+]; int dfs(int x, int t, int f) {
if (x==t) return f;
used[x]=true;
for (int i=; i<G[x].size(); i++) {
edge &e=G[x][i];
if (!used[e.to]&&e.cap>) {
int d=dfs(e.to,t,min(f,e.cap));
if (d>) {
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return ;
} int max_flow(int s, int t) {
int flow=;
for(;;) {
memset(used,,sizeof(used));
int f=dfs(s,t,INF);
if (f==) return flow;
flow+=f;
}
}
} namespace Edmond_Karp {
bool vis[maxn+];
int prev[maxn+];
int pree[maxn+]; void bfs(int s) {
memset(vis,,sizeof(vis));
memset(prev,-,sizeof(prev));
memset(pree,-,sizeof(pree));
queue <int> q;
vis[s]=true;
q.push(s); while(!q.empty()) {
int x=q.front();
q.pop();
for (int i=; i<G[x].size(); i++) {
edge &e=G[x][i];
if (e.cap>&&!vis[e.to]) {
prev[e.to]=x;
pree[e.to]=i;
vis[e.to]=true;
q.push(e.to);
}
}
}
} int max_flow(int s, int t) {
int flow=;
for(;;) {
bfs(s);
if (!vis[t]) return flow;
int d=INF;
for (int i=t; prev[i]!=-; i=prev[i])
d=min(d,G[prev[i]][pree[i]].cap);
for (int i=t; prev[i]!=-; i=prev[i]) {
edge &e=G[prev[i]][pree[i]];
e.cap-=d;
G[e.to][e.rev].cap+=d;
}
flow+=d;
}
}
} namespace Dinic {
int level[maxn+];
int iter[maxn+]; void bfs(int s) {
memset(level,-,sizeof(level));
queue <int> q;
level[s]=;
q.push(s); while (!q.empty()) {
int x=q.front();
q.pop();
for (int i=; i<G[x].size(); i++) {
edge &e=G[x][i];
if (e.cap>&&level[e.to]<) {
level[e.to]=level[x]+;
q.push(e.to);
}
}
}
} int dfs(int x, int t, int f) {
if (x==t) return f;
for (int &i=iter[x]; i<G[x].size(); i++) {
edge &e=G[x][i];
if (e.cap>&&level[e.to]>level[x]) {
int d=dfs(e.to,t,min(f,e.cap));
if (d>) {
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return ;
} int max_flow(int s, int t) {
int flow=;
for(;;) {
bfs(s);
if (level[t]<) return flow;
memset(iter,,sizeof(iter));
int f;
while ((f=dfs(s,t,INF))>)
flow+=f;
}
}
} namespace ISAP {
int gap[maxn+];
int iter[maxn+];
int level[maxn+]; void bfs(int t) {
memset(gap,,sizeof(gap));
memset(level,-,sizeof(level));
queue <int> q;
level[t]=;
gap[level[t]]=;
q.push(t); while (!q.empty()) {
int x=q.front();
q.pop();
for (int i=; i<G[x].size(); i++) {
edge &e=G[x][i];
if (level[e.to]<) {
level[e.to]=level[x]+;
gap[level[e.to]]++;
q.push(e.to);
}
}
}
} int dfs(int x, int s, int t, int f) {
if (x==t) return f;
int flow=;
for (int &i=iter[x]; i<G[x].size(); i++) {
edge &e=G[x][i];
if (e.cap>&&level[x]==level[e.to]+) {
int d=dfs(e.to,s,t,min(f-flow,e.cap));
e.cap-=d;
G[e.to][e.rev].cap+=d;
flow+=d;
if (f==flow) return f;
}
} gap[level[x]]--;
if (gap[level[x]]==)
level[s]=n+;
iter[x]=;
gap[++level[x]]++;
return flow;
} int max_flow(int s, int t) {
int flow=;
bfs(t);
memset(iter,,sizeof(iter));
while (level[s]<=n)
flow+=dfs(s,s,t,INF);
return flow;
}
} int main() {
int s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
init();
printf("%d\n",ISAP::max_flow(s,t));
return ;
}