社区讨论

求助!!!HLPP写到。。TLE

P5030长脖子鹿放置参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi85xlrb
此快照首次捕获于
2025/11/21 09:09
4 个月前
此快照最后确认于
2025/11/21 09:09
4 个月前
查看原帖
当成最小割来写,用的HLPP结果第一个点TLE了?? 记录:https://www.luogu.org/recordnew/show/20224465 代码如下:↓
CPP
#include<cstdio>
#include<queue>
#define Add(a,b,c) (add(a,b,c),add(b,a,0))
using namespace std;
const int MaxN=200,N=MaxN*MaxN*2+2,M=N*19,MaxK=200,inf=0x3f3f3f3f;
inline const void read(int &ans)
{
	ans=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
		ans=ans*10+c-48,c=getchar();
	return;
}
int head[N+1],to[M+2],c[M+2],next[M+2],tot=2;
inline const void add(int x,int y,int z)
{
	to[tot]=y,c[tot]=z,next[tot]=head[x],head[x]=tot++;
	return;
}
inline const int min(const int &a,const int &b)
{
	return a<b?a:b;
}
int h[N+1],gap[M<<1],f[N+1],v[N+1];
struct cmp
{
	inline const bool operator () (const int &a,const int &b) const
	{
		return h[a]<h[b];
	}
};
inline const bool BFS(int s,int t)
{
	queue<int>q;
	int x,i;
	q.push(t),h[t]=1;
	while(q.size())
	{
		x=q.front(),q.pop();
		for(i=head[x];i;i=next[i])
			if(!h[to[i]]&&!c[i])
				h[to[i]]=h[x]+1,q.push(to[i]);
	}
	return h[s];
}
inline const int HLPP(int s,int t,int n)
{
	if(!BFS(s,t))
		return 0;
	h[s]=n;
	int x,z,i,Min;
	for(i=1;i<=n;i++)
		if(h[i])
			gap[h[i]]++;
	priority_queue<int,vector<int>,cmp>q;
	for(i=head[s];i;i=next[i])
		if(c[i])
		{
			f[to[i]]+=c[i],c[i^1]+=c[i],c[i]=0;
			if(!v[to[i]])
				q.push(to[i]),v[to[i]]=1;
		}
	while(q.size())
	{
		x=q.top(),q.pop(),v[x]=0,Min=inf;
		for(i=head[x];i&&f[x];i=next[i])
			if(c[i])
			{
				if(h[to[i]]+1==h[x])
				{
					z=min(f[x],c[i]),f[x]-=z,c[i]-=z,f[to[i]]+=z,c[i^1]+=z;
					if(!v[to[i]]&&to[i]!=s&&to[i]!=t)
						q.push(to[i]),v[to[i]]=1;
				}
				if(c[i])
					Min=min(Min,h[to[i]]);
			}
		if(f[x]&&Min<inf)
		{
			if(!--gap[h[x]])
				for(i=1;i<s;i++)
					if(h[i]>h[x])
						h[i]=n+1;
			h[x]=Min+1,gap[h[x]]++,q.push(x),v[x]=1;
		}
	}
	return f[t];
}
int fx[8]={-3,-1,+1,+3,+3,+1,-1,-3},
	fy[8]={+1,+3,+3,+1,-1,-3,-3,-1};
int n,m,k,fb[MaxN+1][MaxN+1],s,t;
inline const int id(int x,int y)
{
	return (x-1)*m+y;
}
int main()
{
	int i,j,k,x,y,tmp,tx,ty;
	read(n),read(m),read(::k),s=n*m*2+1,t=s+1;
	for(i=1;i<=::k;i++)
		read(x),read(y),fb[x][y]=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(!fb[i][j])
			{
				tmp=id(i,j);
				if(i&1)
				{
					Add(s,tmp,1);
					for(k=0;k<8;k++)
					{
						tx=i+fx[k],ty=j+fy[k];
						if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!fb[tx][ty])
							Add(tmp,n*m+id(tx,ty),inf);
					}
				}
				else
					Add(n*m+tmp,t,1);
			}
	printf("%d\n",n*m-::k-HLPP(s,t,t));
	return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...