bzoj1797: [Ahoi2009]Mincut 最小割

时间:2024-08-27 19:35:56

最大流+tarjan。然后因为原来那样写如果图不连通的话就会出错,WA了很久。

jcvb:

在残余网络上跑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]。

#include<cstdio>
#include<stack>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define op() pt=edges;clr(head,0);
const int nmax=50000;
const int maxn=200000;
const int inf=0x7f7f7f7f;
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
struct edge{
int to,cap,id;edge *next,*rev;
};
edge edges[maxn],*pt,*head[nmax],*p[nmax],*cur[nmax];
int cnt[nmax],h[nmax],ans[60005][2],sccno[nmax],dfs_clock=0,scc_cnt=0,pre[nmax];
stack<int>s;
void add(int uu,int vv,int w,int x){
pt->to=vv;pt->cap=w;pt->id=x;pt->next=head[uu];head[uu]=pt++;
}
void adde(int uu,int vv,int w,int x){
add(uu,vv,w,x);add(vv,uu,0,-1);head[uu]->rev=head[vv];head[vv]->rev=head[uu];
}
int maxflow(int s,int t,int n){
clr(cnt,0);cnt[0]=n;clr(h,0);
int flow=0,a=inf,x=s;edge *e;
while(h[s]<n){
for(e=cur[x];e;e=e->next) if(e->cap>0&&h[x]==h[e->to]+1) break;
if(e){
a=min(a,e->cap);p[e->to]=cur[x]=e;x=e->to;
if(x==t){
while(x!=s) p[x]->cap-=a,p[x]->rev->cap+=a,x=p[x]->rev->to;
flow+=a,a=inf;
}
}else{
if(!--cnt[h[x]]) break;
h[x]=n;
for(e=head[x];e;e=e->next) if(e->cap>0&&h[x]>h[e->to]+1) h[x]=h[e->to]+1,cur[x]=e;
cnt[h[x]]++;
if(x!=s) x=p[x]->rev->to;
}
}
return flow;
}
int dfs(int x){
int lowu=pre[x]=++dfs_clock;
s.push(x);
for(edge *e=head[x];e;e=e->next) if(e->cap>0){
int to=e->to;
if(!pre[to]) lowu=min(lowu,dfs(to));
else if(!sccno[to])lowu=min(lowu,pre[to]);
}
if(lowu>=pre[x]){
scc_cnt++;
while(1){
int X=s.top();s.pop();
sccno[X]=scc_cnt;
if(X==x) break;
}
}
return lowu;
}
int main(){
/*freopen("data.out","r",stdin);
freopen("orz.out","w",stdout);*/
op();
int n=read(),m=read(),s=read(),t=read(),u,v,d;
rep(i,m) u=read(),v=read(),d=read(),adde(u,v,d,i);
maxflow(s,t,n);
rep(i,n) if(!pre[i]) dfs(i);
rep(i,n){
for(edge *o=head[i];o;o=o->next) if(o->id>0&&!o->cap){
if(sccno[i]!=sccno[o->to]) ans[o->id][0]=1;
if(sccno[i]==sccno[s]&&sccno[o->to]==sccno[t]) ans[o->id][1]=1;
}
}
// rep(i,n) printf("%d:%d\n",i,sccno[i]);
/*rep(i,m){
if(sccno[u[i]]!=sccno[v[i]]) printf("1 ");else printf("0 ");
if(sccno[u[i]]==sccno[s]&&sccno[v[i]]==sccno[t]) printf("1\n");else printf("0\n");
}*/
rep(i,m) printf("%d %d\n",ans[i][0],ans[i][1]);
return 0;
}

 

1797: [Ahoi2009]Mincut 最小割

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1812  Solved: 783
[Submit][Status][Discuss]

Description

A,B两个国家正在交战,其中A国的物资运输网中有N个中转站,M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站,那么中转站vi可以通过该道路到达ui中转站,如果切断这条道路,需要代价ci。现在B国想找出一个路径切断方案,使中转站s不能到达中转站t,并且切断路径的代价之和最小。 小可可一眼就看出,这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题: 问题一:是否存在一个最小代价路径切断方案,其中该道路被切断? 问题二:是否对任何一个最小代价路径切断方案,都有该道路被切断? 现在请你回答这两个问题。

Input

第一行有4个正整数,依次为N,M,s和t。第2行到第(M+1)行每行3个正 整数v,u,c表示v中转站到u中转站之间有单向道路相连,单向道路的起点是v, 终点是u,切断它的代价是c(1≤c≤100000)。 注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。

Output

对每条单向边,按输入顺序,依次输出一行,包含两个非0即1的整数,分 别表示对问题一和问题二的回答(其中输出1表示是,输出0表示否)。 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

Sample Input

6 7 1 6
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3

Sample Output

1 0
1 0
0 0
1 0
0 0
1 0
1 0

HINT

设第(i+1)行输入的边为i号边,那么{1,2},{6,7},{2,4,6}是仅有的三个最小代价切割方案。它们的并是{1,2,4,6,7},交是 。 【数据规模和约定】 测试数据规模如下表所示 数据编号 N M 数据编号 N M 1 10 50 6 1000 20000 2 20 200 7 1000 40000 3 200 2000 8 2000 50000 4 200 2000 9 3000 60000 5 1000 20000 10 4000 60000

2015.4.16新加数据一组,可能会卡掉从前可以过的程序。

Source

[Submit][Status][Discuss]