写的Dinic,这为啥会Tle啊
查看原帖
写的Dinic,这为啥会Tle啊
989997
DGL__DGL_AFO楼主2024/9/27 07:48
#include<bits/stdc++.h> //Dinic
using namespace std;
typedef long long ll;
int n,m,s,t;
int tt;
int h[114510],e[2545140],ne[2545140],idx;
ll w[114510],inf=1e18;
ll op,ans;
int tu[114][114],g[114][114];
int d[11451],cur[11451];
int q[1145100],l,r;

inline void add(int a,int b,ll c)
{
	ne[idx]=h[a];
	e[idx]=b;
	w[idx]=c;
	h[a]=idx++;
}

inline void init()
{
	memset(h,-1,sizeof h);
	cin>>n>>m>>tt;
	s=0;
	t=10450;
	for(int i=1;i<=tt;i++)
	{
		int a,b;
		cin>>a>>b;
		tu[a][b]=1;
	}
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    g[i][j]=i*m+j-m;
	 
	 //cout<<n<<' '<<m<<'\n';   
	/*for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    cout<<g[i][j]<<' ';
	cout<<' \n';*/    
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	  {
	  	if(!tu[i][j]&&((i+j)&1))
	  	{
	  		
	  		add(s,g[i][j],1ll);
	  		add(g[i][j],t,0ll);
	  		
	  		if(i+1<=n&&j+2<=m&&!tu[i+1][j+2])
	  		{
	  			add(g[i][j],g[i+1][j+2],inf);
	  			add(g[i+1][j+2],g[i][j],0);
				}
	  		if(i-1>=1&&j+2<=m&&!tu[i-1][j+2])
	  		{//cout<<i<<' '<<j<<"\n";
	  			add(g[i][j],g[i-1][j+2],inf);  
	  		  add(g[i-1][j+2],g[i][j],0);
				}
	  		  
	  		  
	  		if(i-1>=1&&j-2>=1&&!tu[i-1][j-2])
	  		{//
	  			add(g[i][j],g[i-1][j-2],inf); 
	  		  add(g[i-1][j-2],g[i][j],0);
				}
	  		  
				if(i+1<=n&&j-2>=1&&!tu[i+1][j-2])
				{
					add(g[i][j],g[i+1][j-2],inf); 
	  		  add(g[i+1][j-2],g[i][j],0);
				}
	  		  
	  		  
				if(i-2>=1&&j+1<=m&&!tu[i-2][j+1])
				{
					add(g[i][j],g[i-2][j+1],inf);
					add(g[i-2][j+1],g[i][j],0);
				}
	  		   
				if(i-2>=1&&j-1>=1&&!tu[i-2][j-1])
				{
					add(g[i][j],g[i-2][j-1],inf);
					add(g[i-2][j-1],g[i][j],0);
				}
	  		   
					
				if(i+2<=n&&j+1<=m&&!tu[i+2][j+1])
				{
					add(g[i][j],g[i+2][j+1],inf); 
	  		  add(g[i+2][j+1],g[i][j],0);
				}
	  		  
				if(i+2<=n&&j-1>=1&&!tu[i+2][j-1])
				{
					add(g[i][j],g[i+2][j-1],inf); 
					add(g[i+2][j-1],g[i][j],0);
				}
	  		  					  
			}
			else if(!tu[i][j])
			{
				add(g[i][j],t,1ll);
				add(t,g[i][j],0ll);
			}
		}
		
}

inline bool bfs()
{
	l=0;r=0;
	memset(d,-1,sizeof d);
	q[0]=s;
	d[s]=0;
	cur[s]=h[s];
	while(l<=r)
	{
		int x=q[l];
		for(int i=h[x];~i;i=ne[i])
		{
			int y=e[i];
			if(d[y]==-1&&w[i]>0)
			{
				d[y]=d[x]+1;
				cur[y]=h[y];
				if(y==t)
			    return true;
			  q[++r]=y;
			}
			  
		}
		l++;
	}
	return false;
}

inline ll find(int x,ll maxx)
{
	
	if(x==t)
		return maxx;
	
	
	ll res=0;
	
	for(int i=cur[x];~i&&res<maxx;i=ne[i])
	{
		int y=e[i];//cout<<y<<' ';
		cur[x]=i;
		if(d[y]==d[x]+1&&w[i]>0)
		{
			ll k=find(y,min(w[i],maxx-res));
			if(!k)
			  d[y]=-1;
			w[i]-=k;
			w[i^1]+=k;
			res+=k;  
		}
	}
	return res;
}

void Dinic()
{
	while(bfs())
		while(op=find(s,inf))	
			ans+=op;
}

void ANS()
{
	cout<<n*m-ans-tt;
}

int main()
{
	init();
	
	Dinic();
		
	ANS();
	
	return 0;
}
2024/9/27 07:48
加载中...