【bzoj 1797】 [Ahoi2009]Mincut 最小割(最大流+Tarjan缩点)

    xiaoxiao2022-08-12  66

    1797: [Ahoi2009]Mincut 最小割

    Time Limit: 10 Sec   Memory Limit: 162 MB Submit: 1977   Solved: 853 [ 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

    Day1

    [ Submit][ Status][ Discuss]

    【题解】【网络流最小割ISAP+Tarjan缩点】

    【这道题,一上来题目就已经告诉我们这是一道最小割,直接建图,以代价为每条边的流量跑isap就行】

    【跑完后,用Tajan缩点处理残量网络,通过残量网络中还有流量的边进行缩点,最后判断每条边(用 残量网络的边)所连接的每两个点是否是一个点,如果不是,证明当前边已被割掉,如果这两个点一个属于起点的集合,一个属于终点的集合,那么“对任何一个最小代价路径切断方案,都有该道路被切断”】

    #include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[120010],nxt[120010],remain[120010],p[6010],id[120010],tot; int dis[6010],cur[6010],num[6010],last[6010]; int dft[6010],dist[6010],f[6010],d[120010],top,root,cnt; bool b[6010],vis[6010]; int n,m,s,t,ans[60010][2]; inline void add(int x,int y,int v,int i) { tot++; a[tot]=y; nxt[tot]=p[x]; p[x]=tot; remain[tot]=v; id[tot]=i; tot++; a[tot]=x; nxt[tot]=p[y]; p[y]=tot; remain[tot]=0; id[tot]=i; } inline int addflow(int s,int t) { int now=t,s1=0x7fffffff; while(now!=s) { s1=min(s1,remain[last[now]]); now=a[last[now]^1]; } now=t; while(now!=s) { remain[last[now]^1]+=s1; remain[last[now]]-=s1; now=a[last[now]^1]; } return s1; } inline void bfs(int t) { queue<int>que; for(int i=1;i<=n;++i) dis[i]=n; memset(b,0,sizeof(b)); que.push(t); b[t]=true; dis[t]=0; while(!que.empty()) { int u=que.front(); que.pop(); int v=p[u]; while(v!=-1) { if(!b[a[v]]&&remain[v^1]) { dis[a[v]]=dis[u]+1; b[a[v]]=1; que.push(a[v]); } v=nxt[v]; } } return; } inline void isap(int s,int t) { bfs(t); for(int i=1;i<=n;++i) num[dis[i]]++; for(int i=1;i<=n;++i) cur[i]=p[i]; int now=s,sum=0; while(dis[s]<n) { if(now==t) { sum+=addflow(s,t); now=s; } bool h=false; int u=cur[now]; while(u!=-1) { if(dis[a[u]]+1==dis[now]&&remain[u]) { h=true; cur[now]=u; last[a[u]]=u; now=a[u]; break; } u=nxt[u]; } if(h==false) { int minn=m-1,u=p[now]; while(u!=-1) { if(remain[u]) minn=min(minn,dis[a[u]]); u=nxt[u]; } --num[dis[now]]; if(!num[dis[now]]) break; dis[now]=minn+1; num[minn+1]++; cur[now]=p[now]; if(now!=s) now=a[last[now]^1]; } } } void tarjan(int x) { dft[x]=dist[x]=++cnt; vis[x]=1; d[++top]=x; int u=p[x]; while(u!=-1) { if(!remain[u]) {u=nxt[u]; continue;} if(!dft[a[u]]) { tarjan(a[u]); dist[x]=min(dist[x],dist[a[u]]); } else if(vis[a[u]]&&dist[x]>dft[a[u]]) dist[x]=dft[a[u]]; u=nxt[u]; } int b; if(dist[x]==dft[x]) { root++; do{ b=d[top--]; vis[b]=false; f[b]=root; }while(b!=x); } } int main() { freopen("int.txt","r",stdin); freopen("my.txt","w",stdout); int i,j; tot=-1; memset(p,-1,sizeof(p)); memset(nxt,-1,sizeof(nxt)); scanf("%d%d%d%d",&n,&m,&s,&t); for(i=1;i<=m;++i) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z,i); } isap(s,t); for(i=1;i<=n;++i) if(!dft[i]) tarjan(i); int sl=f[s],sr=f[t]; for(i=1;i<=n;++i) { int u=p[i]; while(u!=-1) { if(!remain[u]) {u=nxt[u]; continue;} if(f[i]!=f[a[u]]&&u%2)//当前边一定是残量网络中的边,缩点后当前边的左右端点不属于同一个点,那么,就说明当前边被割掉了 { ans[id[u]][0]=1; if((f[i]==sl&&f[a[u]]==sr||f[a[u]]==sl&&f[i]==sr)&&u%2) ans[id[u]][1]=1; } u=nxt[u]; } } for(i=1;i<=m;++i) printf("%d %d\n",ans[i][0],ans[i][1]); return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-1132703.html
    最新回复(0)