蒟蒻求助,为啥我的Dinic T了最后一个点
查看原帖
蒟蒻求助,为啥我的Dinic T了最后一个点
750869
Michael_Liu楼主2023/8/19 17:00
#include <bits/stdc++.h>
using namespace std;
const int N=560;
const int INF=0x3f3f3f3f;
int head[N],dis[N],r[N],c,deep[N];
int n,m,cnt=0,sum=0,ans=0;	
int s=0,t=550;
queue<int> q;
struct edge{
	int w,to,next;
}edge[N*N];
void add(int u,int v,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	
	edge[cnt].w=0;
	edge[cnt].to=u;
	edge[cnt].next=head[v];
	head[v]=cnt++;
}

bool bfs()
{
	if(s==t) return 0;
	memset(deep,-1,sizeof(deep));
	while(!q.empty())
	{
		q.pop();
	}
	q.push(s);
	deep[s]=1;
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		for(int i=head[p];i!=-1;i=edge[i].next)
		{
			int to=edge[i].to,w=edge[i].w;
			if(deep[to]==-1 && w>0)
			{
				q.push(to);
				deep[to]=deep[p]+1;
			}
		}
	}
	return deep[t]!=-1;
}

int dfs(int s,int t,int flow)
{
	if(s==t)
	{
		return flow;
	}
	for(int i=head[s];i!=-1;i=edge[i].next)
	{
		int to=edge[i].to,w=edge[i].w;
		if(deep[to]!=deep[s]+1||w<=0)
		{
			continue;
		}
		int newflow=dfs(to,t,min(flow,w));
		if(newflow)
		{
			edge[i].w-=newflow;
			edge[i^1].w+=newflow;
			return newflow;
		}
	}
	return 0;
}

void Dinic(int s,int t)
{
	while(bfs())
	{
		while(1)
		{
			int flow=dfs(s,t,INF);
			if(flow==0)
			{
				break;
			}
			ans+=flow;
		}
	}
}

void check()
{
	for(int i=1;i<=m;i++)
	{
		int k=0;
		for(int j=head[i];j!=-1;j=edge[j].next)
		{
			int to=edge[j].to,w=edge[j].w;
			if(w==0)
			{
				cout<<to-m<<" ";
				k++;
			}
			if(k>=r[i])
			{
				break;
			}
		}
		cout<<endl;
	}
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	memset(head,-1,sizeof(head));
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		cin>>r[i];
		sum+=r[i];
		add(s,i,r[i]);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>c;
		add(m+i,t,c);
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			add(i,j+m,1);
		}
	}
	Dinic(s,t);
	if(ans==sum)
	{
		cout<<1<<endl;
	}
	else
	{
		cout<<0<<endl;
		return 0;
	}
	check();
	return 0;
}
2023/8/19 17:00
加载中...