网络最大流dinic

2023-12-16 19:30:33

假的写法

实测836ms~~比EK还慢~~
（来自Blueqwq)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
#define maxn 210
#define maxm 10010
#define int long long
using namespace std;
template<typename T>
inline void read(T &x){
	x=0; bool flag=0; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

const int inf=1e18;
int n,m,s,t,u,v,w;
int ans=0,cnt,head[maxn],dep[maxn],now[maxn],depth,lim;
bool vis[maxn];
struct node{
    int nxt;
    int to;
    int v;
}e[maxm];

void add(int from,int to,int v){
    e[cnt].to=to;
    e[cnt].nxt=head[from];
    e[cnt].v=v;
    head[from]=cnt++;
}

bool bfs(){
    memset(dep,0,sizeof(dep));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);
    dep[s]=1;
    vis[s]=true;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i!=-1;i=e[i].nxt){
            int y=e[i].to,v=e[i].v;
            if(v&&!vis[y]){
                vis[y]=1;
                dep[y]=dep[x]+1;
                q.push(y);
            }
        }
    }
    return vis[t];
}

int dfs(int x,int lim){
    if(x==t) return lim;
    int res=0;//res必为局部变量，因为如果是全局变量，中间就清零了，返回值就奇奇怪怪，可能会有负数 
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int y=e[i].to,v=e[i].v;
        if(v&&dep[y]>dep[x]){
            int flow=dfs(y,min(v,lim));//因为这里还要dfs的 
            e[i].v-=flow;
            e[i^1].v+=flow;
            res+=flow;
            lim-=flow;
        }
    }
    if(res==0) dep[x]=0;
    return res;
}

int dinic(){
    while(bfs()) ans+=dfs(s,inf);
    return ans;
}

signed main(){
    read(n),read(m),read(s),read(t);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++){
        read(u),read(v),read(w);
        add(u,v,w);
        add(v,u,0);
    }
    cout<<dinic()<<endl;
    return 0;
}

orz XiEn1847,orz Blueqwq

真的写法1

实测57ms
（来自AWR2020）

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef long long ll;
const int N = 5010;
const long long inf = 0x0fffffffffffffff;

int n, m, s, t;
int ct = 1, hd[N], ver[N<<1], nxt[N<<1]; ll wt[N<<1];
int dep[N]; bool inque[N];
int cur[N];

void add(int u, int v, ll w) {
	ct ++;
	ver[ct] = v;
	wt[ct] = w;
	nxt[ct] = hd[u];
	hd[u] = ct;
	ct ++;
	ver[ct] = u;
	wt[ct] = 0;
	nxt[ct] = hd[v];
	hd[v] = ct;
}

bool bfs() {
	memset(dep, 0x3f, sizeof(dep));
	memset(inque, 0, sizeof(inque));
	queue<int> q;
	q.push(s);
	dep[s] = 0;
	cur[s] = hd[s];
	inque[s] = true;
	while(q.size()) {
		int x = q.front();
		q.pop();
		inque[x] = false;
		for(int i = hd[x]; i; i = nxt[i]) {
			int y = ver[i];
			if(wt[i] && dep[y] > dep[x] + 1) {
				dep[y] = dep[x] + 1;
				cur[y] = hd[y];
				if(!inque[y]) {
					q.push(y);
					inque[y] = true;
				}
			}
		}
	}
	if(dep[t] != 0x3f3f3f3f)
		return true;
	return false;
}

ll dfs(int x, ll flow) {
	ll ret = 0;
	if(x == t)
		return flow;
	for(int i = cur[x]; i; i = nxt[i]) {
		cur[x] = i;
		int y = ver[i];
		if(wt[i] && dep[y] == dep[x] + 1) {
			if(ret = dfs(y, min(flow, wt[i]))) {
				wt[i] -= ret;
				wt[i^1] += ret;
				return ret;
			}
		}
	}
	return 0;
}

ll dinic() {
	ll maxflow = 0, flow;
	while(bfs())
		while(flow = dfs(s, inf))
			maxflow += flow;
	return maxflow;
}

int main() {
	cin >> n >> m >> s >> t;
	for(int i = 1; i <= m; i ++) {
		int u, v; ll w;
		scanf("%d%d%lld", &u, &v, &w);
		add(u, v, w);
	}
	cout << dinic() << endl;
	return 0;
}

orz AWR2020

真的写法2

实测54ms
(来自lhm_)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
#define maxn 10010
#define maxm 200010
#define int long long
using namespace std;
template<typename T>
inline void read(T &x){
	x=0; bool flag=0; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

const int inf=1e18;
int n,m,s,t,u,v,w;
int ans,cnt=1,head[maxn],dep[maxn],cur[maxn],depth,lim,res;//pay attention! ans=1!!!
struct node{
	int nxt;
	int to;
	int v;
}e[maxm];

void add(int from,int to,int v){
	e[++cnt].to=to;
	e[cnt].nxt=head[from];
	head[from]=cnt;
	e[cnt].v=v;
}

bool bfs(){
	memcpy(cur,head,sizeof(head));//********
	memset(dep,0,sizeof(dep));
	queue<int>q;
	q.push(s);
	dep[s]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].to,v=e[i].v;
			if(!v||dep[y]) continue;
			dep[y]=dep[x]+1;
			q.push(y);
		}
	}
	return dep[t];
}

int dfs(int x,int lim){
	if(x==t) return lim;
	int res=lim,flow;
	for(int &i=cur[x];i;i=e[i].nxt){//当前弧优化，cur会和i一起改 
		int y=e[i].to,v=e[i].v;
		if(!v||dep[y]!=dep[x]+1) continue;
		flow=dfs(y,min(v,res));
		res-=flow;
		e[i].v-=flow;
		e[i^1].v+=flow;
		if(res<=0) break;
	}
	return lim-res;
}

/*
int dfs(int x,int lim){
	if(x==t) return lim;
	int res=lim,flow;
	for(int i=cur[x];i;i=e[i].nxt){//和上面的写法等效 
		cur[x]=i;
		int y=e[i].to,v=e[i].v;
		if(!v||dep[y]!=dep[x]+1) continue;
		flow=dfs(y,min(v,res));
		res-=flow;
		e[i].v-=flow;
		e[i^1].v+=flow;
		if(res<=0) break;
	}
	return lim-res;
}
*/

int dinic(){
	while(bfs()) while(int flow=dfs(s,inf)) ans+=flow;
	return ans;
}

signed main(){
	read(n),read(m),read(s),read(t);
	for(int i=1;i<=m;i++){
		read(u),read(v),read(w);
		add(u,v,w);
		add(v,u,0);
	}
	cout<<dinic()<<endl;
	return 0;
}

orz lhm_,orz i207M,orz AWR2020,orz XiEn1847,orz wsy_jim

码农公寓

假的写法

真的写法1

真的写法2

相关文章