ZigZagK的博客
[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解
[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解
2018年3月12日 15:45
BZOJ
查看标签

题目概述

给出一张 $n$ 个点 $m$ 条有向边的图,现在要求 $S,T$ 的最小割,问每一条边:

  1. 有没有可能出现在最小割中。
  2. 是否一定出现在最小割中。

解题报告

先跑出随意一种最小割(最大流),然后在残量网络里缩点,接下来好像有结论?

  • $(x,y)$ 可能出现:$SCC_x\not=SCC_y$ 。
  • $(x,y)$ 一定出现:$SCC_S=SCC_x,SCC_y=SCC_T$ 。

yy一下还是挺显然的。因为缩点之后只剩下满流边,所以新图中每一种割都恰好对应原来的一种最小割,只要 $x,y$ 不在同一个强连通分量中,就可以被切断(从而形成某种最小割);如果 $S$ 和 $x$ 在一起而 $y$ 和 $T$ 在一起,就说明 $(x,y)$ 必须切断才可能切断 $S$ 到 $T$ 。最后再注意一下流量为 $0$ 的边就行了。

示例程序

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
#include<cstdio> #include<cstring> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; const int maxn=4000,maxm=60000; int n,m,S,T,x[maxm+5],y[maxm+5],z[maxm+5]; int dfn[maxn+5],low[maxn+5],top,stk[maxn+5],SCC[maxn+5]; int E,lnk[maxn+5],son[(maxm<<1)+5],nxt[(maxm<<1)+5]; int cur[maxn+5],que[maxn+5],ti,vis[maxn+5],dis[maxn+5]; bool instk[maxn+5];pair<int,int> e[(maxm<<1)+5]; inline void Add(int x,int y,int z){ son[E]=y;e[E]=mp(0,z);nxt[E]=lnk[x];lnk[x]=E++; son[E]=x;e[E]=mp(0,0);nxt[E]=lnk[y];lnk[y]=E++; } inline bool Bfs(int s,int t){ int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0; while (Head!=Tail) for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j]) if (vis[u=son[j]]<ti&&e[j].fr<e[j].sc) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1; return vis[t]==ti; } int Dfs(int x,int gl,int MIN=2e9){ if (x==gl||!MIN) return MIN;int f=0,now; for (int &j=cur[x];~j;j=nxt[j]) if (dis[x]+1==dis[son[j]]&&(now=Dfs(son[j],gl,min(MIN,e[j].sc-e[j].fr)))){ f+=now;e[j].fr+=now;e[j^1].fr-=now; if (!(MIN-=now)) break; } return f; } void Tarjan(int x){ dfn[x]=low[x]=++ti;stk[++top]=x;instk[x]=true; for (int j=lnk[x];~j;j=nxt[j]) if (e[j].fr<e[j].sc) if (!dfn[son[j]]) Tarjan(son[j]),low[x]=min(low[x],low[son[j]]); else if (instk[son[j]]) low[x]=min(low[x],dfn[son[j]]); if (dfn[x]==low[x]) for (int y=(SCC[0]++,stk[top--]);;y=stk[top--]) {SCC[y]=SCC[0];instk[y]=false;if (x==y) break;} } int main(){ freopen("program.in","r",stdin); freopen("program.out","w",stdout); scanf("%d%d%d%d",&n,&m,&S,&T);E=0;memset(lnk,255,sizeof(lnk)); for (int i=1;i<=m;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]),Add(x[i],y[i],z[i]); while (Bfs(S,T)) memcpy(cur,lnk,sizeof(lnk)),Dfs(S,T); for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i); for (int i=1;i<=m;i++){ if (e[i-1<<1].fr<e[i-1<<1].sc) {puts("0 0");continue;} putchar((SCC[x[i]]!=SCC[y[i]])+48);putchar(' '); putchar((SCC[S]==SCC[x[i]]&&SCC[y[i]]==SCC[T])+48);puts(""); } return 0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 2580 天前,最后更新于 2283 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏