1797: [Ahoi2009]Mincut 最小割
题目:传送门
题解:
感觉是一道肥肠好的题目。
第二问其实比第一问简单?
用残余网络跑强联通,流量大于0才访问。
那么如果两个点所属的联通分量分别处于st和ed,那一定会被割掉,那么第一问就也会是1
但是第一问单独处理,就有点GG
膜了一发题解,发现贼尼玛niu bi:
还是利用联通分量,如果这条边满流,且连接的两个点所处的联通分量不同,就ok
太菜了不会证明...大佬hzwer
代码:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 999999999
using namespace std;
typedef long long LL;
struct node
{
int x,y,next,other;LL c;
}a[];int len,last[];
void ins(int x,int y,LL c)
{
int k1,k2;
k1=++len;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len; k2=++len;
a[len].x=y;a[len].y=x;a[len].c=;
a[len].next=last[y];last[y]=len; a[k1].other=k2;
a[k2].other=k1;
}
int n,m,st,ed,head,tail;
int list[],h[];
bool bt_h()
{
memset(h,,sizeof(h));h[st]=;
list[]=st;head=;tail=;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]== && a[k].c>)
{
h[y]=h[x]+;
list[tail++]=y;
}
}
head++;
}
if(h[ed]>)return true;
return false;
}
LL find_flow(int x,LL flow)
{
if(x==ed)return flow;
LL s=,t;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]+ && a[k].c> && s<flow)
{
s+=t=find_flow(y,min(a[k].c,flow-s));
a[k].c-=t;a[a[k].other].c+=t;
}
}
if(s==)h[x]=;
return s;
}
int low[],dfn[],belong[],sta[];
int tp,id,cnt;
bool v[];
void dfs(int x)
{
low[x]=dfn[x]=++id;
sta[++tp]=x;v[x]=true;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(a[k].c!=)
{
if(dfn[y]==-)
{
dfs(y);
low[x]=min(low[x],low[y]);
}
else
if(v[y]==true)
low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x])
{
int i;cnt++;
do{
i=sta[tp--];
v[i]=false;
belong[i]=cnt;
}while(i!=x);
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&st,&ed);
len=;memset(last,,sizeof(last));
for(int i=;i<=m;i++)
{
int x,y;LL c;
scanf("%d%d%lld",&x,&y,&c);
ins(x,y,c);
}
LL ans=;
while(bt_h())ans+=find_flow(st,inf);
memset(sta,,sizeof(sta));
memset(dfn,-,sizeof(dfn));
memset(low,,sizeof(low));
memset(v,false,sizeof(v));
id=tp=cnt=;
for(int i=;i<=n;i++)
if(dfn[i]==-)
dfs(i);
for(int i=;i<len;i+=)
{
int x=a[i].x,y=a[i].y;
if(a[i].c!=){printf("0 0\n");continue;}
if(belong[x]!=belong[y])printf("1 ");
else printf("0 ");
if((belong[x]==belong[st] && belong[y]==belong[ed]))
printf("1\n");
else printf("0\n");
}
return ;
}