网络流

字数统计: 2.4k字   |   阅读时长: 14min

板子

最大流

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;
const int N = 1e5+100;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

int n,m,s,t;

struct node
{
	int ne,to,w;
}edge[200100];

int head[N],cnt=1;

inline void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	edge[cnt].w=w;
	head[u]=cnt;
}

int d[N];
queue<int> q;

inline bool bfs()
{
	fill(d+1,d+1+n,-1);
	d[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(register int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to;
			if(d[v]!=-1||edge[i].w<=0) continue;
			d[v]=d[u]+1;
			q.push(v);
		}
	}
	return d[t]!=-1;
}

int dinic(int u,int mn)
{
	if(u==t||mn<=0) return mn;
	int flow=0,tmpf=0;
	for(register int i=head[u];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(d[v]==d[u]+1&&(tmpf=dinic(v,min(mn,edge[i].w)))>0)
		{
			mn-=tmpf;
			flow+=tmpf;
			edge[i].w-=tmpf;
			edge[i^1].w+=tmpf;
		}
		if(!mn) break;
	}
	if(!flow) d[u]=0;
	return flow;
}

int u,v,w,ans;

int main()
{
	read(n),read(m),read(s),read(t);
	for(register int i=1;i<=m;i++)
	{
		read(u),read(v),read(w);
		add(u,v,w);
		add(v,u,0);
	}
	while(bfs()) ans+=dinic(s,INF);
	printf("%d\n",ans);
	return 0;
}

费用流

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
const int M = 50100;
const int N = 5100;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

struct node
{
	int ne,to,w,f;
}edge[M<<1];

int head[N],cnt=1;

inline void add(int u,int v,int w,int f)
{
	edge[++cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].f=f;
	edge[cnt].ne=head[u];
	head[u]=cnt;
}

int n,m,s,t;
queue<int> q;
int vis[N],dis[N],pre[N];

inline bool spfa()
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	vis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(register int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].f&&edge[i].w>0)
			{
				dis[v]=dis[u]+edge[i].f;
				pre[v]=i;
				if(!vis[v]) vis[v]=1,q.push(v);
			}
		}
	}
	return dis[t]!=0x3f3f3f3f;
}

int flow,cost;

inline void mcmf()
{
	while(spfa())
	{
		int mn=0x7fffffff;
		for(register int i=t;i;i=edge[pre[i]^1].to)
		{
			if(i==s) continue;
			mn=min(mn,edge[pre[i]].w);
		}
		for(register int i=t;i;i=edge[pre[i]^1].to)
		{
			edge[pre[i]].w-=mn;
			edge[pre[i]^1].w+=mn;
		}
		flow+=mn;
		cost+=dis[t]*mn;
	}
}

int u,v,w,f;

int main()
{
	read(n),read(m),read(s),read(t);
	for(register int i=1;i<=m;i++)
	{
		read(u),read(v),read(w),read(f);
		add(u,v,w,f);
		add(v,u,0,-f);
	}
	mcmf();
	printf("%d %d\n",flow,cost);
	return 0;
}

P2756飞行员配对方案问题

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 1e4;
const int INF = 0x7fffffff;
int s=0,t,cnt=1,head[N*2+1],m,n;

struct node
{
    int ne,to,w,u;
}edge[N*4+1];

void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].ne=head[u];
    edge[cnt].u=u;
    head[u]=cnt;
}

int d[N*4+1];
queue<int> q;

bool bfs()
{
    q.push(s);
    fill(d+1,d+1+t,-1);
    d[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=edge[i].ne)
        {
            int v=edge[i].to;
            if(d[v]!=-1||edge[i].w<=0) continue;
            d[v]=d[u]+1;
            q.push(v);
        }
    }
    return d[t]!=-1;
}

int dinic(int u,int mn)
{
    if(u==t||mn==0)
    return mn;
    int flow=0,tmpf=0;
    for(int i=head[u];i;i=edge[i].ne)
    {
        int v=edge[i].to;
        if(d[v]==d[u]+1&&(tmpf=dinic(v,min(mn,edge[i].w)))>0)
        {
            flow+=tmpf;
            mn-=tmpf;
            edge[i].w-=tmpf;
            edge[i^1].w+=tmpf;
        }
        if(!mn) break;
    }
    if(!flow) d[u]=0;
    return flow;
}

int main()
{
    scanf("%d%d",&m,&n);
    t=n+1;
    for(int i=1;i<=m;i++)
    {
        add(s,i,1);
        add(i,s,0);
    }
    for(int i=m+1;i<=n;i++)
    {
        add(i,t,1);
        add(t,i,0);
    }
    int u,v;
    while(scanf("%d%d",&u,&v)&&u!=-1&&v!=-1)
    {
        add(u,v,1);
        add(v,u,0);
    }
    int ans=0;
    while(bfs())
    ans+=dinic(s,INF);
    printf("%d\n",ans);
    for(int i=2;i<=cnt;i+=2)
    {
        if(edge[i].w==0&&edge[i].to!=t&&edge[i].u!=s) 
        printf("%d %d\n",edge[i].u,edge[i].to);
    }
    return 0;
}

裸的二分图匹配，建立超级源点和超级汇点。

P4016 负载平衡问题

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

struct node
{
    int ne,to,f,w;
}edge[10100];

int n;
int a[110],sum,s=108,t=109;
int head[110],cnt=1;

inline void _add(int u,int v,int w,int f)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].f=f;
    edge[cnt].ne=head[u];
    head[u]=cnt;
}

inline void add(int u,int v,int w,int f)
{
    _add(u,v,w,f),_add(v,u,0,-f);
}

bool vis[110];
int pre[110],dis[110];
queue<int> q;
int cost;

inline bool spfa()
{
    memset(dis,0x3f,sizeof(dis));
    vis[s]=1;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(register int i=head[u];i;i=edge[i].ne)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].f&&edge[i].w>0)
            {
                dis[v]=dis[u]+edge[i].f;
                pre[v]=i;
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
    return dis[t]!=INF;
}

inline void mcmf()
{
    while(spfa())
    {
        int mn=INF;
        for(register int i=t;i;i=edge[pre[i]^1].to)
        {
            if(i==s) continue;
            mn=min(mn,edge[pre[i]].w);
        }
        for(register int i=t;i;i=edge[pre[i]^1].to)
        {
            edge[pre[i]].w-=mn;
            edge[pre[i]^1].w+=mn;
        }
        cost+=1ll*dis[t]*mn;
    }
}

int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
    sum/=n;
    for(register int i=1;i<=n;i++) a[i]-=sum;
    for(register int i=1;i<=n;i++)
    {
        if(a[i]>0) 
            add(s,i,a[i],0);
        if(a[i]<0) 
            add(i,t,-a[i],0);
        if(i!=1) 
            add(i,i-1,INF,1);
        if(i!=n) 
            add(i,i+1,INF,1); 
    }
    add(1,n,INF,1);
    add(n,1,INF,1);
    mcmf();
    printf("%d\n",cost);
    return 0;
}

巨佬的博客讲的非常清楚

P2765 魔术球问题

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
const int N = 500100;
const int INF = 0x3f3f3f3f;

struct node
{
    int ne,to,w;
}edge[N];

int head[N],cnt=1;

inline void _add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].ne=head[u];
    edge[cnt].w=w;
    head[u]=cnt;
}

inline void add(int u,int v,int w)
{
    _add(u,v,w),_add(v,u,0);
}

int s=100001,t=100002;
queue<int> q;
int dis[N];

inline bool bfs()
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(register int i=head[u];i;i=edge[i].ne)
        {
            int v=edge[i].to;
            if(dis[v]!=INF||edge[i].w<=0) continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    return dis[t]!=INF;
}

int nex[N];

inline int dinic(int u,int mn)
{
    if(mn<=0||u==t) return mn;
    int flow=0,tmpf=0;
    for(register int i=head[u];i;i=edge[i].ne)
    {
        int v=edge[i].to;
        if(dis[v]==dis[u]+1&&(tmpf=dinic(v,min(edge[i].w,mn)))>0)
        {
            nex[u>>1]=v>>1;
            edge[i].w-=tmpf;
            edge[i^1].w+=tmpf;
            mn-=tmpf;
            flow+=tmpf;
        }
        if(!mn) break;
    }
    if(!flow) dis[u]=0;
    return flow;
}

inline int wll()
{
    int rt=0;
    while(bfs()) rt+=dinic(s,INF);
    return rt;
}

int n,now,tot,num;
int sta[N];
bool vis[N];

int main()
{
    scanf("%d",&n);
    while(now<=n)
    {
        num++;
        add(s,num<<1,1),add((num<<1)|1,t,1);
        for(register int i=sqrt(num)+1;i*i<(num<<1);i++)
        add((i*i-num)<<1,(num<<1)|1,1);
        int tmp=wll();//若tmp!=0说明num放到了之前的柱子上，出现了新的流。
        if(!tmp) sta[++now]=num;//tmp==0说明num放到了新的柱子上                              
    }
    printf("%d\n",--num);
    for(register int i=1;i<=n;i++)
    {
        if(!vis[sta[i]])
        {
            int k=sta[i];printf("%d ",k);vis[k]=1;
            while(nex[k]&&nex[k]!=(t)>>1)
            {
                k=nex[k];
                vis[k]=true;
                printf("%d ",k);
            }
            printf("\n");
        }
    }
    return 0;
}

p2764 最小路径覆盖问题

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 0x7ffffffff;
const int N= 6100;
struct node
{
	int ne,to,w,u;
}edge[N<<2];

int head[N],cnt=1,d[N],s=0,t,m,n;

void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].ne=head[u];
	edge[cnt].u=u;
	head[u]=cnt;
}

queue<int> q;

bool bfs()
{
	q.push(s);
	fill(d+1,d+1+t,-1);
	d[t]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to;
			if(d[v]!=-1||edge[i].w<=0) continue;
			d[v]=d[u]+1;
			q.push(v);
		}
	}
	return d[t]!=-1;
}

int dinic(int u,int mn)
{
	if(u==t||mn==0) 
	return mn;
	int flow=0,tmpf=0;
	for(int i=head[u];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(d[v]==d[u]+1&&(tmpf=dinic(v,min(edge[i].w,mn)))>0)
		{
			flow+=tmpf;
			mn-=tmpf;
			edge[i].w-=tmpf;
			edge[i^1].w+=tmpf;
		}
		if(!mn) break;
	}
	if(!flow) d[u]=0;
	return flow;
}

int main()
{
	scanf("%d%d",&n,&m);
	t=2*n+1;
	for(int i=1;i<=n;i++)
	{
		add(s,i,1);
		add(i,s,0);
	}
	for(int i=n+1;i<=n<<2;i++)
	{
		add(i,t,1);
		add(t,i,0);
	}
	for(int i=1,u,v;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v+n,1);
		add(v+n,u,0);
	}
	int ans=0;
	while(bfs()) ans+=dinic(s,INF);
	printf("%d\n",ans); 
	return 0;
}

经典的转换，拆点转换为二分图，然后用二分图的定理求解

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/89b04f08.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

    			  jsonContent:
				meta: false
				pages: false
				posts:
				  title: true
				  date: true
				  path: true
				  text: false
				  raw: false
				  content: false
				  slug: false
				  updated: false
				  comments: false
				  link: false
				  permalink: false
				  excerpt: false
				  categories: false
				  tags: true


There's nothing