社区讨论
求帮助查找ISAP的错误
P4843 清理雪道参与者 4已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lxk6nsp8
- 此快照首次捕获于
- 2024/06/18 17:09 2 年前
- 此快照最后确认于
- 2024/06/18 20:06 2 年前
我的代码用Dinic就可以过,ISAP会WA on 10,希望能够找到原因,已瞪眼两小时。
CPP#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(int i=l;i<=r;i++)
#define rep2(i,l,r) for(int i=l;i>=r;i--)
const int N=1e6+10;
const int inf=0x3f3f3f3f;
using namespace std;
int n,m,S,T,s,t,h[N],e[N],ne[N],w[N],idx,dep[N],now[N],low[N],limits[N],gap[N];
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f*x;
}
void add(int x,int y,int z)
{
e[idx]=y;
ne[idx]=h[x];
w[idx]=z;
h[x]=idx++;
e[idx]=x;
ne[idx]=h[y];
w[idx]=0;
h[y]=idx++;
return;
}
void bfs(int s,int t)
{
memset(dep,-1,sizeof dep);
memset(gap,0,sizeof gap);
dep[t]=0;
gap[0]=1;
queue<int> q;
q.push(t);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=h[x];~i;i=ne[i])
{
int to=e[i];
if(~dep[to]) continue;
q.push(to);
dep[to]=dep[x]+1;
++gap[dep[to]];
}
}
return;
}
int dfs(int x,int sum,int s,int t)
{
if(x==t) return sum;
int res=0;
for(int i=h[x];~i;i=ne[i])
{
int to=e[i];
if(w[i]&&dep[to]+1==dep[x])
{
int flow=dfs(to,min(w[i],sum-res),s,t);
if(flow)
{
w[i]-=flow;
w[i^1]+=flow;
res+=flow;
}
if(res==sum) return res;
}
}
--gap[dep[x]];
if(!gap[dep[x]]) dep[s]=n+1;
++dep[x];
++gap[dep[x]];
return res;
}
int ISAP(int s,int t)
{
int maxflow=0;
bfs(s,t);
while(dep[s]<=n) maxflow+=dfs(s,inf,s,t);
return maxflow;
}
signed main()
{
memset(h,-1,sizeof h);
n=read();
S=n+1;
T=n+2;
s=n+3;
t=n+4;
rep1(i,1,n)
{
int len=read();
rep1(j,1,len)
{
int x=read();
add(i,x,inf-1);
++limits[i];
--limits[x];
low[i]=1;
}
add(S,i,inf);
add(i,T,inf);
}
rep1(i,1,n)
{
if(limits[i]>0) add(i,t,limits[i]);
if(limits[i]<0) add(s,i,-limits[i]);
}
ISAP(s,t);
add(T,S,inf);
ISAP(s,t);
cout<<w[idx-1]<<endl;
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...