为什么我的当前弧优化是负优化???
查看原帖
为什么我的当前弧优化是负优化???
191993
six_小6猪楼主2021/4/21 07:29

这是加优化的

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') 
   {
   	 s=(s<<3)+(s<<1)+(ch^48);
   ch=getchar();
   }
   return s*w;
}
const int inf=1<<28; 
struct node{
	int to,nxt,w; 
}e[1000001];
int head[200005];
int cur[200005];
int cnt=1;
int m,n,p,q;
queue<int > qq;
void add(int x,int y,int z)
{
	e[++cnt].to=y;
	e[cnt].w=z;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}
int s,t;
int maxflow;
int d[200005],gap[200005];
void bfs()
{
	for(int i=0;i<=n+1;i++)
	{
		 d[i]=-1;gap[i]=0;
	}
	d[t]=0;
	gap[s]=1;
	qq.push(t);
	while(!qq.empty())
	{
		int x=qq.front();
		qq.pop();
		for(int i=head[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(d[y]!=-1)
			  continue;
			d[y]=d[x]+1;
			gap[d[y]]++;
			qq.push(y);
		}
		
	}
	return;
}
inline int dfs(int x,int flow)
{
	if(x==t)
	  {
	  	maxflow+=flow;
	  	return flow;	
	  }
	  int used=0;
	for(register int &i=cur[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(d[x]==d[y]+1&&e[i].w)
		{
			cur[x]=i;
			int mi=dfs(y,min(flow-used,e[i].w));
			if(mi)
			{
				e[i].w-=mi;
				e[i^1].w+=mi;
				used+=mi;
			}
	if(flow==used)
		return used;
		}
	}
	--gap[d[x]];
	if(!gap[d[x]])
	  	d[s]=n+1;
     d[x]++;
     gap[d[x]]++;
    cur[x]=head[x];
     return used;
}
int main()
{
	m=read();
	p=read();
	q=read();
	s=0;
	n=p+q+m+m+1;
	t=n;
	for(register int i=1;i<=m;i++)
	{
		add(p+i,p+i+m,1);
		add(p+i+m,p+i,0);
		for(register int j=1;j<=p;j++)
		{
			int pd=read();
			if(!pd)
			  continue;
			add(j,i+p,1);
			add(i+p,j,0);
		}
	}
	for(register int i=1;i<=p;i++)
	 {
	 	add(s,i,1);
	 	add(i,s,0);
	 }
	for(register int i=1;i<=m;i++)
	{
		for(register int j=1;j<=q;j++)
		{
			int pd=read();
			if(!pd)
			  continue;
			add(p+m+i,p+m+m+j,1);
			add(p+m+m+j,p+m+i,0);
		}
	}
	for(register  int i=1;i<=q;i++)
	{
		add(p+m+m+i,t,1);
		add(t,p+m+m+i,0);
	}
	bfs();
	memcpy(cur,head,sizeof(head));
	while(d[s]<n)
	{
		dfs(s,inf);
	}
	printf("%d",maxflow);
}

2021/4/21 07:29
加载中...