社区讨论

萌新刚学网络流,关于上下界网络流的最小流的原汇连边

P4843 清理雪道参与者 1已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@lonqt7g5
此快照首次捕获于
2023/11/07 10:59
2 年前
此快照最后确认于
2023/11/07 15:18
2 年前
查看原帖
看一些题解都是先跑一遍,然后加边再跑一下,但我的加边不一样,我是直接按加了然后跑两遍。
例如第二个题解
CPP

	add(t,s,inf);//有源汇变成无源汇
	s=ss,t=tt;
	Dinic();
	int ans=edge[top].w;//这是最后一条边的反向边,含义是可行流的大小
	edge[top].w=edge[top-1].w=0;//最后一条边要删掉
	s=n+1,t=0;//把可行流减到最小流(把反向边都流回去且满足流量守恒)
	Dinic();
我的做法
CPP
	add(t,s,inf);
    add(s,t,0);
    dinic(S,T);
    printf("%d\n",inf-dinic(t,s));
求两者的区别。
总代码如何下:
CPP
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=110,M=2e4;
#define FHD(x) for(int i=head[x],y;y=ver[i],i;i=nxt[i])
#define FOR(i,a,b) for(int i=a;i<=b;++i)
int head[N],ver[M*2],nxt[M*2],edge[M*2],tot,fl[N],v[N],d[N];
void add(int x,int y,int z){ver[++tot]=y;edge[tot]=z;nxt[tot]=head[x];head[x]=tot;}
int rd(int &res){char c;int sign=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')sign=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=sign;return res;
}
bool bfs(int s,int t){
    memset(v,0,sizeof(v));
    memset(d,0,sizeof(d));
    queue<int>q;q.push(s);d[s]=1;
    while(q.size()){
        int x=q.front();q.pop();
        v[x]=1;
        FHD(x)if(!d[y]&&edge[i]){
            d[y]=d[x]+1;
            if(y==t)return true;
            q.push(y);
        }
    }
    return false;
}
int dfs(int x,int t,int flow){
    if(x==t)return flow;
    int res=flow;
    FHD(x)if(edge[i]&&d[y]==d[x]+1){
        int k=dfs(y,t,min(res,edge[i]));
        if(!k)d[y]=0;
        edge[i]-=k;
        edge[i^1]+=k;
        res-=k;
        if(!res)break;
    }
    return flow-res;
}
int dinic(int s,int t){
    int maxflow=0,flow=0,inf=1e6;
    while(bfs(s,t))while(flow=dfs(s,t,inf))maxflow+=flow;
    return maxflow;
}
int main(){
    int s,t,S,T,n,m,dw,up,inf=1e5,sum=0,flwsum=0,y,c,k;tot=1;
    rd(n);s=n+1;t=n+2;S=0,T=n+3;
    FOR(i,1,n){
        add(s,i,n);add(i,s,0);
        add(i,t,n);add(t,i,0);
        rd(m);
        FOR(j,1,m){
            rd(y);
            dw=1;up=n;
            fl[i]-=dw;fl[y]+=dw;
            add(i,y,up-dw);
            add(y,i,0);
        }
    }
    add(t,s,inf);
    add(s,t,0);
    FOR(i,1,n){
        if(fl[i]<0)add(i,T,-fl[i]),add(T,i,0);
        if(fl[i]>0)add(S,i,fl[i]),add(i,S,0);
    }
    dinic(S,T);
    printf("%d\n",inf-dinic(t,s));
    return 0;
}

回复

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

正在加载回复...