社区讨论
求助!!!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 条回复,欢迎继续交流。
正在加载回复...