• 欢迎光临~

2172. Dinic/ISAP求最大流

开发技术 开发技术 2022-08-04 次浏览

题目链接

2172. Dinic/ISAP求最大流

给定一个包含 (n) 个点 (m) 条边的有向图,并给定每条边的容量,边的容量非负。

图中可能存在重边和自环。求从点 (S) 到点 (T) 的最大流。

输入格式

第一行包含四个整数 (n,m,S,T)

接下来 (m) 行,每行三个整数 (u,v,c),表示从点 (u) 到点 (v) 存在一条有向边,容量为 (c)

点的编号从 (1)(n)

输出格式

输出点 (S) 到点 (T) 的最大流。

如果从点 (S) 无法到达点 (T) 则输出 (0)

数据范围

(2 le n le 10000),
(1 le m le 100000),
(0 le c le 10000),
(S neq T)

输入样例:

7 14 1 7
1 2 5
1 3 6
1 4 5
2 3 2
2 5 3
3 2 2
3 4 3
3 5 3
3 6 7
4 6 5
5 6 1
6 5 1
5 7 8
6 7 7

输出样例:

14

解题思路

(dinic)

(dinic) 基于 (EK) 算法做了一些优化:每次搜索时多路增广,同时为了防止出现环而导致出现死循环的情况,引入多层图的概念,即每次扩展到下一个节点时都是一层一层扩展。
具体操作:先 (bfs) 预处理出多层图的层数,然后 (dfs) 开始多路增广,同时引入当前弧优化:即每一次 (dfs) 时,如果前面已经选择该边,则下一次一定不选该边,即引入 (cur) 数组,判断当前节点从哪条边开始 (dfs)

(dinic) 的时间复杂度的上界也比较松,一般处理 (10^4sim 10^5) 规模的网络

  • 时间复杂度:(O(n^2m))

代码

// Problem: Dinic/ISAP求最大流
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2174/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=10005,M=200005,inf=0x3f3f3f3f;
int n,m,s,t;
int h[N],e[M],ne[M],f[M],idx;
int cur[N],d[N],q[N],hh,tt,res;
void add(int a,int b,int c)
{
	e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
	e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}

bool bfs()
{
	memset(d,-1,sizeof d);
	q[0]=s;
	cur[s]=h[s];
	tt=hh=d[s]=0;
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=h[x];~i;i=ne[i])
		{
			int y=e[i];
			if(d[y]==-1&&f[i])
			{
				d[y]=d[x]+1;
				cur[y]=h[y];
				if(y==t)return true;
				q[++tt]=y;
			}
		}
	}
	return false;
}
int dfs(int x,int limit)
{
	if(x==t)return limit;
	int flow=0;
	for(int i=cur[x];~i&&flow<limit;i=ne[i])
	{
		cur[x]=i;
		int y=e[i];
		if(d[y]==d[x]+1&&f[i])
		{
			int t=dfs(y,min(f[i],limit-flow));
			if(!t)d[y]=-1;
			f[i]-=t,f[i^1]+=t,flow+=t;
		}
	}
	return flow;
}
int dinic()
{
	while(bfs())res+=dfs(s,inf);
	return res;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
    	int u,v,c;
    	scanf("%d%d%d",&u,&v,&c);
    	add(u,v,c);
    }
    printf("%d",dinic());
    return 0;
}
程序员灯塔
转载请注明原文链接:2172. Dinic/ISAP求最大流
喜欢 (0)