【bzoj1797】 Ahoi2009—Mincut 最小割

http://www.lydsy.com/JudgeOnline/problem.php?id=1797 (题目链接)

题意

  求一条边是否可能在一个最小割集中,以及这条边是否一定在最小割集中。

Solution

  DaD3zZ大爷

  跑完最大流以后,在残余网络上跑tarjan求出所有SCC,记belong[u]为点u所在SCC的编号。显然有belong[s]!=belong[t](否则s到t有通路,能继续增广)。
  ①对于任意一条满流边(u,v),(u,v)能够出现在某个最小割集中,当且仅当belong[u]!=belong[v];
  ②对于任意一条满流边(u,v),(u,v)必定出现在最小割集中,当且仅当belong[u]==belong[s]且belong[v]==belong[t]。

细节

  我也不知道为什么犯了若干sb错误= =

代码

// bzoj1797
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define inf (1ll<<60)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std; const int maxn=1000010;
int head[maxn],bel[maxn],low[maxn],dfn[maxn],st[maxn],id[maxn],n,m,S,T,top,scc,cnt=1;
struct edge {int from,to,next,w;}e[maxn]; namespace Dinic {
int d[maxn];
bool bfs() {
memset(d,-1,sizeof(d));
queue<int> q;q.push(S);d[S]=0;
while (!q.empty()) {
int x=q.front();q.pop();
for (int i=head[x];i;i=e[i].next)
if (e[i].w && d[e[i].to]<0) d[e[i].to]=d[x]+1,q.push(e[i].to);
}
return d[T]>0;
}
int dfs(int x,LL f) {
if (x==T || f==0) return f;
int w,used=0;
for (int i=head[x];i;i=e[i].next) if (e[i].w && d[e[i].to]==d[x]+1) {
w=dfs(e[i].to,min(1LL*e[i].w,f-used));
used+=w,e[i].w-=w,e[i^1].w+=w;
if (used==f) return used;
}
if (!used) d[x]=-1;
return used;
}
void main() {
while (bfs()) dfs(S,inf);
}
} void link(int u,int v,int w) {
e[++cnt]=(edge){u,v,head[u],w};head[u]=cnt;
e[++cnt]=(edge){v,u,head[v],0};head[v]=cnt;
}
void Tarjan(int x) {
low[x]=dfn[x]=++cnt;
st[++top]=x;
for (int i=head[x];i;i=e[i].next) if (e[i].w) {
if (!dfn[e[i].to]) {
Tarjan(e[i].to);
low[x]=min(low[x],low[e[i].to]);
}
else if (!bel[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
}
if (dfn[x]==low[x]) {
scc++;
for (;st[top]!=x;top--) bel[st[top]]=scc;
bel[st[top--]]=scc;
}
}
int main() {
scanf("%d%d%d%d",&n,&m,&S,&T);
for (int u,v,w,i=1;i<=m;i++) {
scanf("%d%d%d",&u,&v,&w);
id[i]=cnt+1;
link(u,v,w);
}
Dinic::main();cnt=0;
for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
for (int i=1;i<=m;i++) {
int j=id[i];
if (e[j].w!=0 || bel[e[j].from]==bel[e[j].to]) {puts("0 0");continue;}
if (bel[e[j].from]==bel[S] && bel[e[j].to]==bel[T]) puts("1 1");
else puts("1 0");
}
return 0;
}
上一篇:原生js为页面添加爱心特效和判断手机端还是电脑端登录


下一篇:centos安装Tesseract