社区讨论

求帮助查找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 条回复,欢迎继续交流。

正在加载回复...