洛谷P4126 [AHOI2009]最小割

题目：洛谷P4126 [AHOI2009]最小割

思路：

结论题

在残余网络上跑tarjan求出所有SCC，记id[u]为点u所在SCC的编号。显然有id[s]!=id[t]（否则s到t有通路，能继续增广）。

对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当id[u]!=id[v]；

对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当id[u] == id[s]且id[v] == id[t]。

证明：

①将每个SCC缩成一个点，得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割，从中任取一个把id[u]和id[v]割开的割即可证明。

②假设将(u,v)的边权增大，那么残余网络中会出现s->u->v->t的通路，从而能继续增广，于是最大流流量（也就是最小割容量）会增大。这即说明(u,v)是最小割集中必须出现的边。

上述解释已经比较清楚，思维能力有限，还没有想到更好的解释方法，因此不再过多解释。

注意残量网络是指代码中实际建出的图，在跑完最大流之后所有边权大于0的边构成的子图，其中存在反向弧。

Code：

#include <bits/stdc++.h>

using namespace std;

const int N=5e5+5,inf=0x3f3f3f3f;

int n,m,s,t,d[N];

int tim,tp,scc_num,st[N],dfn[N],low[N],belong[N];

int Top=1,ver[N],val[N],nxt[N],head[N];

inline void add(int u,int v,int w){

	ver[++Top]=v;val[Top]=w;nxt[Top]=head[u];head[u]=Top;

	ver[++Top]=u;val[Top]=0;nxt[Top]=head[v];head[v]=Top;

}

bool bfs(){

	for(int i=1;i<=n;++i) d[i]=0;

	queue<int> q;

	q.push(s);

	d[s]=1;

	while(!q.empty()){

		int u=q.front();q.pop();

		for(int i=head[u];i;i=nxt[i]){

			int v=ver[i];

			if(val[i]&&!d[v]){

				d[v]=d[u]+1;

				if(v==t) return true;

				q.push(v);

			}

		}

	}

	return false;

}

int dfs(int u,int flow){

	if(u==t) return flow;

	int left=flow;

	for(int i=head[u];i&&left;i=nxt[i]){

		int v=ver[i];

		if(val[i]&&d[v]==d[u]+1){

			int res=dfs(v,min(left,val[i]));

			if(!res) d[v]=0;

			val[i]-=res;

			val[i^1]+=res;

			left-=res;

		}

	}

	return flow-left;

}

void tarjan(int u){

	dfn[u]=low[u]=++tim;

	st[++tp]=u;

	for(int i=head[u];i;i=nxt[i]){

		int v=ver[i];

		if(!val[i]) continue;//注意此处 在残量网络中tarjan

		if(!dfn[v]){

			tarjan(v);

			low[u]=min(low[u],low[v]);

		}

		else if(!belong[v]) low[u]=min(low[u],dfn[v]);

	}

	if(low[u]==dfn[u]){

		++scc_num;

		int t;

		do{

			t=st[tp--];

			belong[t]=scc_num;

		} while(t!=u);

	}

}

int main(){

	scanf("%d%d%d%d",&n,&m,&s,&t);

	for(int i=1,u,v,w;i<=m;++i){

		scanf("%d%d%d",&u,&v,&w);

		add(u,v,w);

	}

	while(bfs()) dfs(s,inf);

	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);

	for(int i=2;i<=Top;i+=2){

		int u=ver[i^1],v=ver[i];

		if(!val[i]&&belong[u]!=belong[v]) printf("%d ",1);

		else printf("%d ",0);

		if(!val[i]&&belong[u]==belong[s]&&belong[v]==belong[t]) printf("%d",1);

		else printf("%d",0);

		putchar('\n');

	}

	return 0;

}

巴特西

洛谷P4126 [AHOI2009]最小割

题目：洛谷P4126 [AHOI2009]最小割

思路：

Code：

最新文章

热门文章