社区讨论
萌新刚学网络流,关于上下界网络流的最小流的原汇连边
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 条回复,欢迎继续交流。
正在加载回复...