网络流(更新ing)

E-K算法代码模板

#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int M=500005;
struct node
{
	int to,next;
	int w;
}e[M];
int head[M],vis[M],dis[M],pre[M];
int cnt=2,n,m,s,t,ans,inf=99999999;
void add(int u,int v,int w){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
	e[cnt].to=u;
	e[cnt].w=0;
	e[cnt].next=head[v];
	head[v]=cnt++;
}
int bfs()//bfs找增广路
{
	for(int i=1;i<=n;i++){vis[i]=0;}
	queue<int> q;
	q.push(s);
	vis[s]=1;
	dis[s]=inf;//dis数组表示流经该点的流量
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			if(e[i].w==0)continue;
			int v=e[i].to;
			if(vis[v]==1)continue;
			dis[v]=min(dis[x],e[i].w);
			pre[v]=i;
			q.push(v);
			vis[v]=1;
			if(v==t)return 1;
		}
	}
	return 0;
}
void update()//更新残留网络
{
	int x=t;//x=汇点,倒着更新
	while(x!=s)
	{
		int v=pre[x];
		e[v].w-=dis[t];
		e[v^1].w+=dis[t];
		x=e[v^1].to;
	}
	ans+=dis[t];
}
int main()
{
	int u,v,w;
	scanf("%d %d %d %d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
	}
	while(bfs()!=0)
	{update();}
	printf("%d\n",ans);
	return 0;
}

Dinic算法代码模板

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll inf=0x3f3f3f3f;
ll n,m,u,v,s,t;
ll w,ans,dis[530005];
ll cnt=2,now[530005],head[530005];
struct node
{
    ll to,next,w;
}e[530005];
void add(ll u,ll v,ll w)
{
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
    e[cnt].to=u;
    e[cnt].w=0;
    e[cnt].next=head[v];
    head[v]=cnt++;
}
ll bfs()//在残量网络中构造分层图
{
    for (int i=1;i<=n;i++)dis[i]=0;//将所有点初始置为inf
    queue<ll> q;//定义队列
    q.push(s);//将源点入队
    dis[s]=1;//源点为第1层
    now[s]=head[s];//当前弧优化
    while(!q.empty())
    {
        ll x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].next)
        {
            ll v=e[i].to;
            if(e[i].w>0&&dis[v]==0)
            {
                q.push(v);
                now[v]=head[v];
                dis[v]=dis[x]+1;
                if(v==t)return 1;//找到一条增广路
            }
        }
    }
    return 0;
}
ll dfs(ll x,ll sum)
{
    if(x==t)return sum;
    ll k,res=0;//k是当前最小的剩余容量
    for(int i=now[x];i&&sum;i=e[i].next)
    {
        now[x]=i;//当前弧优化
        ll v=e[i].to;
        if(e[i].w>0&&(dis[v]==dis[x]+1))
        {
            k=dfs(v,min(sum,e[i].w));
            if(k==0){dis[v]=0;} //剪枝,去掉增广完毕的点
            e[i].w-=k;
            e[i^1].w+=k;
            res+=k;//res表示经过该点的所有流量和(相当于流出的总量)
            sum-=k; //sum表示经过该点的剩余流量
        }
    }
    return res;
}
int main()
{
    scanf("%lld %lld %lld %lld",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&u,&v,&w);
        add(u,v,w);
    }
    while(bfs())
    {ans+=dfs(s,inf);}//流量守恒,(流入=流出)
    printf("%lld\n",ans);
    return 0;
} 

以下题目来自洛谷网络流24题(包括但不限于)

------------------------------------------------------------------------------------------------

飞行员配对方案问题

题目链接

二分图最大匹配问题,建一个超级源点与超级汇点,源点与外籍飞行员建容量为1的边,汇点与英国飞行员也建容量为1的边,同理外籍飞行员与英国飞行之前也是建容量为1 的边,建好之后用dinic跑一个最大流即可,最后输出方案的时候根据两点之间的流量判断该边是否被使用

代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
struct node
{
	int w,to,next;
}e[5005];
int head[5005],dis[5005],now[5005],vis[5005];
int cnt=2,n,m,s=201,t=202,u,v,inf=99999999;
void add(int u,int v,int w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
	e[cnt].to=u;
	e[cnt].w=0;
	e[cnt].next=head[v];
	head[v]=cnt++;
}
int bfs()
{
	for(int i=1;i<=n;i++)dis[i]=0;
	dis[s]=0;dis[t]=0;
	queue<int> q;
	q.push(s);
	dis[s]=1;
	//now[s]=head[s];
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int v=e[i].to;
			if(e[i].w>0&&dis[v]==0)
			{
				q.push(v);
				dis[v]=dis[x]+1;
				//now[v]=head[v];
				if(v==t){return 1;}
			}
		}
	}
	return 0;
}
int dfs(int x,int sum)
{
	if(x==t){return sum;}
	int k,res=0;
	for(int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if(e[i].w>0&&(dis[v]==dis[x]+1))
		{
			k=dfs(v,min(sum,e[i].w));
			if(k==0)dis[v]=0;
			e[i].w-=k;
			//pre[v]=x;
			e[i^1].w+=k;
			res+=k;
			sum-=k;
		}
	}
	return res;
}
int main()
{
	IOS
	cin>>m>>n;
	while(cin>>u>>v)
	{
		if(u==-1&&v==-1)
		{break;}
		if(vis[u]==0)
		{add(s,u,1);
		vis[u]=1;}
		if(vis[v]==0)
		{add(v,t,1);
		vis[v]=1;}
		add(u,v,1);
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	cout<<ans<<endl;
	for(int i=1;i<=m;i++)
	{
		for(int j=head[i];j;j=e[j].next)
		{
			if(e[j].w==0)
			{
				int to=e[j].to;
				if(to==s){continue;}
				cout<<i<<" "<<to<<endl;
				break;
			}
		}
	}
	return 0;
}

地震逃生

原题链接

很裸的最大流模板题

代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
ll n,m,cnt=2,s,t,inf=0x3f3f3f3f;
ll head[5005],dis[5005];
struct node
{
	ll to,next,w;
}e[5005];
void add(ll u,ll v,ll w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
	e[cnt].to=u;
	e[cnt].w=0;
	e[cnt].next=head[v];
	head[v]=cnt++;
}
ll bfs()
{
	for(int i=1;i<=n;i++){dis[i]=0;}
	queue<ll> q;
	q.push(s);
	dis[s]=1;
	while(!q.empty())
	{
		ll x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			ll v=e[i].to;
			if(dis[v]==0&&e[i].w>0){
				dis[v]=dis[x]+1;
				q.push(v);
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
ll dfs(ll u,ll sum)
{
	if(u==t)return sum;
	ll k,res=0;
	for(int i=head[u];i;i=e[i].next)
	{
		ll v=e[i].to;
		if((dis[v]==dis[u]+1)&&e[i].w>0)
		{
			k=dfs(v,min(sum,e[i].w));
			if(k==0)dis[v]=0;
			e[i].w-=k;
			e[i^1].w+=k;
			res+=k;
			sum-=k;
		}
	}
	return res;
}
int main()
{
	IOS
	ll a,b,c,x;
	cin>>n>>m>>x;
	s=1;t=n;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		add(a,b,c);
	}
	ll ans=0;
	while(bfs())
	{ans+=dfs(s,inf);}
	//cout<<ans<<endl;
	if(ans==0)
	{
		cout<<"Orz Ni Jinan Saint Cow!"<<endl;
		return 0;
	}
	if(x%ans==0)
	{cout<<ans<<" "<<x/ans<<endl;}
	else
	{cout<<ans<<" "<<x/ans+1<<endl;}
	return 0;
} 

酒店之王

原题链接

果然,网络流问题就像Y总说的那样,难在建图 >﹏<

类似于一个三分图匹配,题目给出了客人和房间之前的关系、客人和饭菜之间的关系,未给出饭菜和房间之间的关系,因此以 源点->房间->客人->饭菜->汇点 类似于这种方式建图。然后还有很关键的一个问题,就是会出现下面这种情况

每条边的容量是1,这样跑出来的最大流是2,但题意是一个客人只能选择一个房间和一种饭菜饭菜,因此我们对客人进行拆点

这样就可以了

代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
int n,p,q;
vector<int>a[102],b[102];
struct node
{
	int to,next,w;
}e[500005];
int head[500005],dis[500005],vis[303][303],cai[102],dian[102];
int cnt=2,s,t,inf=99999999;
void add(int u,int v,int w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
	e[cnt].to=u;
	e[cnt].w=0;
	e[cnt].next=head[v];
	head[v]=cnt++;
}
int bfs()
{
	for(int i=1;i<=500;i++)dis[i]=0;
	queue<int>q;
	q.push(s);
	dis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(dis[v]==0&&e[i].w>0)
			{
				dis[v]=dis[u]+1;
				q.push(v);
				if(v==t){return 1;}
			}
		}
	}
	return 0;
}
int dfs(int u,int sum)
{
	if(u==t)return sum;
	int k,res=0;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if((dis[v]==dis[u]+1)&&e[i].w>0)
		{
			k=dfs(v,min(sum,e[i].w));
			if(k==0)dis[v]=0;
			e[i].w-=k;
			e[i^1].w+=k;
			res+=k;
			sum-=k;
		}
	}
	return res;
}
int main()
{
	int x;
	cin>>n>>p>>q;
	s=401;t=402;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=p;j++){
			cin>>x;
			if(x==1){
				a[i].push_back(j);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=q;j++){
			cin>>x;
			if(x==1){
				b[i].push_back(j);
			}
		}
	}
	/////////////////////////////////////////////////
	for(int i=1;i<=n;i++)
    {
        if(a[i].size()==0||b[i].size()==0)continue;
        for(int j=0;j<a[i].size();j++)
        {
            if(dian[a[i][j]]==0)
            {
                dian[a[i][j]]=1;
                add(s,100+a[i][j],1);
            }
            add(a[i][j]+100,i,1);
        }
        add(i,i+200,1);
        for(int j=0;j<b[i].size();j++)
        {
            if(cai[b[i][j]]==0)
            {
                cai[b[i][j]]=1;
                add(300+b[i][j],t,1);
            }
            add(i+200,b[i][j]+300,1);
        }
    }
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	cout<<ans<<endl;
	return 0;
}

试题库问题

超级源点与试题建边,容量为1;试题与类型也建边,容量为1;类型与超级汇点建边,容量为题目所需的类型数量。然后跑最大流。最后的判断也要格外注意一下。

代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
int n,k,s,t,cnt=2,inf=0x3f3f3f;
int task[1005];
struct node
{
	int to,next,w;
}e[500005];
int head[500005],dis[5005],vis[1002];
void add(int u,int v,int w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
	e[cnt].to=u;
	e[cnt].w=0;
	e[cnt].next=head[v];
	head[v]=cnt++;
}
int bfs()
{
	for(int i=1;i<=4005;i++)dis[i]=0;
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int v=e[i].to;
			if(dis[v]==0&&e[i].w>0)
			{
				dis[v]=dis[x]+1;
				q.push(v);
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
int dfs(int x,int sum)
{
	if(x==t)return sum;
	int k,res=0;
	for(int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if((dis[v]==dis[x]+1)&&e[i].w>0)
		{
		    int minn=min(sum,e[i].w);
			k=dfs(v,minn);
			if(k==0){dis[v]=0;}
			e[i].w-=k;
			e[i^1].w+=k;
			res+=k;
			sum-=k;
		}
	}
	return res;
}
int main()
{
	s=3001,t=3003;
	cin>>k>>n;
	for(int i=1;i<=k;i++){
		cin>>task[i];
	}
	int p,x;
	for(int i=1;i<=n;i++)
	{
		cin>>p;
		if(p==0){continue;}
		add(s,i,1);
		for(int j=1;j<=p;j++)
		{
			cin>>x;
			add(i,x+1000,1);
			vis[x]=1;
		}
	}
	for(int i=1;i<=k;i++){
		if(vis[i]==1){
			add(1000+i,t,task[i]);
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	int tt=0;
	for(int i=1;i<=k;i++){
		tt+=task[i];
	}
	if(ans<tt){cout<<"No solution!"<<endl;return 0;}
	vector<int> c[1002];
	for(int i=1;i<=k;i++)
	{
		for(int j=head[1000+i];j;j=e[j].next)
		{
			int v=e[j].to;
			if(v==t)continue;
			if(e[j].w>0){
				c[i].push_back(v);
			}
		}
	}
	int flag=1;
	for(int i=1;i<=k;i++){
		if(c[i].size()<task[i]){
			flag=0;break;
		}
	}
	if(flag==0){cout<<"No solution!"<<endl;return 0;}
	for(int i=1;i<=k;i++){
		cout<<i<<": ";
		for(int j=0;j<c[i].size();j++){
			cout<<c[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

最小路径覆盖问题

二分图中,最小路径覆盖=点的总数 - 点之间的最大匹配数(网络最大流)

因此建一个二分图,超源与x建边,容量为1,x与y之前建边,容量为1,y与超汇之间建边,容量为1。然后跑一个最大流

代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
struct node
{
	int to,next,w;
}e[500005];
int head[500005],dis[500005],vis[50005];
int in[2005],out[2005];
int cnt=2,n,m,s,t,inf=99999999;
void add(int u,int v,int w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
	e[cnt].to=u;
	e[cnt].w=0;
	e[cnt].next=head[v];
	head[v]=cnt++;
}
int bfs()
{
	for(int i=1;i<=600;i++)dis[i]=0;
	queue<int>q;
	dis[s]=1;
	q.push(s);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].next){
			int v=e[i].to;
			if(dis[v]==0&&e[i].w>0){
				dis[v]=dis[x]+1;
				q.push(v);
				if(v==t){return 1;}
			}
		}
	}
	return 0;
}
int dfs(int x,int sum)
{
	if(x==t)return sum;
	int k,res=0;
	for(int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if((dis[v]==dis[x]+1)&&e[i].w>0){
			k=dfs(v,min(sum,e[i].w));
			if(k==0)dis[v]=0;
			e[i].w-=k;
			e[i^1].w+=k;
			res+=k;
			sum-=k;
		}
	}
	return res;
}
int main()
{
	int x,y;
	s=501;t=502;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		if(vis[x]==0){
			add(s,x,1);
			vis[x]=1;
		}
		if(vis[y+200]==0){
			add(200+y,t,1);
			vis[y+200]=1;
		}
		add(x,y+200,1);
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	for(int i=1+200;i<=150+200;i++){
		for(int j=head[i];j;j=e[j].next){
			if(e[j].w>0){
				int u=e[j].to;
				if(u==t)continue;
				out[u]=i-200;
				in[i-200]=u;
				break;
			}
		}
	}
	//cout<<in[2]<<endl;
	for(int i=1;i<=n;i++){
		if(in[i]==0&&out[i]!=0){
			int u=i;
			while(u!=0){
				cout<<u<<" ";
				u=out[u];
			}
		cout<<endl;
		}
	}
	cout<<n-ans<<endl;
	return 0;
}
//4,9,16,25,36,49,64,81,100,121

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注