P3376 【模板】网络最大流
题目描述
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入输出格式
输入格式：
第一行包含四个正整数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算法，需要注意许多点：
- 反向边初始值容量为0，
- 异或符号，x^1，x为偶数+1，奇数-1；所以第一条边为偶数，所以我的第一条边是2，他的反向边是3；
- 数据范围，这个就不多说了，反向建边，数组大小要乘2
code
#include<cstdio>
#include<algorithm> using namespace std; const int N = ;
const int INF = 1e9; struct Edge{
int to,c,nxt;
}e[]; int q[],head[N],dis[N],cur[N];
int S,T,n,m,L,R,tot = ; inline char nc() {
static char buf[],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2) ? EOF : *p1++;
}
inline int read() {
int x = ,f = ;char ch = nc();
for (; ch<''||ch>''; ch = nc()) if (ch=='-') f = -;
for (; ch>=''&&ch<=''; ch = nc()) x = x * + ch - '';
return x * f;
}
inline void add_edge(int u,int v,int w) {
e[++tot].to = v,e[tot].c = w,e[tot].nxt = head[u],head[u] = tot;
e[++tot].to = u,e[tot].c = ,e[tot].nxt = head[v],head[v] = tot;
}
inline bool bfs() {
for (int i=; i<=n; ++i) {
cur[i] = head[i];dis[i] = -;
}
L = ;R = ;
q[++R] = S;
dis[S] = ;
while (L <= R) {
int u = q[L++];
for (int i=head[u]; i; i=e[i].nxt) {
int v = e[i].to,c = e[i].c;
if (dis[v]==- && c>) {
q[++R] = v;
dis[v] = dis[u] + ;
if (v==T) return true;
}
}
}
return false;
}
int dfs(int u,int flow) {
if (u==T) return flow;
int used = ;
for (int & i=cur[u]; i; i=e[i].nxt) {
int v = e[i].to,c = e[i].c;
if (dis[v]==dis[u]+ && c>) {
int tmp = dfs(v,min(c,flow-used));
if (tmp > ) {
e[i].c -= tmp;e[i^].c += tmp;
used += tmp;
if (used==flow) break;
}
}
}
if (used != flow) dis[u] = -;
return used;
}
inline int dinic() {
int ans = ;
while (bfs())
ans += dfs(S,INF);
return ans;
}
int main() {
n = read(),m = read(),S = read(),T = read();
for (int a,b,c,i=; i<=m; ++i) {
a = read(),b = read(),c = read();
add_edge(a,b,c);
}
printf("%d",dinic());
return ;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std; const int MAXN = ;
const int INF = 1e9; struct Edge{
int to,c,nxt;
Edge(){}
Edge(int tt,int cc,int nn) {to = tt,c = cc,nxt = nn;}
}e[];
queue<int>q; int head[MAXN],dis[MAXN];
int s,t,n,m,tot = ; int read()
{
int x = , f = ;char ch = getchar();
while (ch<''||ch>'') {if (ch=='-') f = -; ch = getchar();}
while (ch>=''&&ch<='') {x = x*+ch-''; ch = getchar();}
return x*f;
}
bool bfs()
{
q.push(s);
memset(dis,-,sizeof(dis));
dis[s] = ;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i=head[u]; i; i=e[i].nxt)
{
int v = e[i].to;
if (dis[v]==-&&e[i].c>)
{
dis[v] = dis[u]+;
q.push(v);
}
}
}
if (dis[t]!=-) return true;
return false;
}
int dfs(int u,int low)
{
if (u==t) return low;
int w,used = ;
for (int i=head[u]; i; i=e[i].nxt)
{
int v = e[i].to;
if (dis[v]==dis[u]+&&e[i].c>)
{
w = dfs(v,min(low-used,e[i].c));
e[i].c -= w;
e[i^].c += w;
used += w;
if (used==low) return low;
}
}
if (!used) dis[u] = -;
return used;
}
int dinic()
{
int ans = ,t;
while (bfs())
ans += dfs(s,INF);
return ans;
}
int main()
{
n = read();m = read();s = read();t = read();
for (int u,v,w,i=; i<=m; ++i)
{
u = read();v = read();w = read();
e[++tot] = Edge(v,w,head[u]);
head[u] = tot;
e[++tot] = Edge(u,,head[v]);
head[v] = tot;
}
printf("%d",dinic());
return ;
}
很早以前的代码