BZOJ1797 [AHOI2009] Mincut 最小割-布布扣-bubuko.com

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

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

技术分享

先跑一遍最大流

学到新姿势：跑最大流后Tarjan缩点

1. 如果一条边满流，且起点和终点不在一个SCC内，则存在一个最小割方案该边；

2. 如果一条边满流，且起点在源点SCC内，终点在汇点SCC内，则任意一个最小割包括该边。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <queue>
  6 #include <stack>
  7 #define rep(i,l,r) for(int i=l; i<=r; i++)
  8 #define clr(x,y) memset(x,y,sizeof(x))
  9 #define travel(x) for(Edge *p=last[x]; p; p=p->pre)
 10 using namespace std;
 11 const int INF = 0x7fffffff;
 12 const int maxn = 4010;
 13 struct Edge{
 14     Edge *pre,*rev; int from,to; int cost;
 15 }edge[120010];
 16 Edge *last[maxn],*cur[maxn],*pt;
 17 int n,m,x,y,z,S,T,ans=0,dfsclock=0,scc=0,d[maxn],dfn[maxn],low[maxn],belong[maxn];
 18 bool isin[maxn];
 19 queue <int> q;
 20 stack <int> s;
 21 inline int read(){
 22     int ans = 0, f = 1;
 23     char c = getchar();
 24     while (!isdigit(c)){
 25         if (c == ‘-‘) f = -1;
 26         c = getchar();
 27     }
 28     while (isdigit(c)){
 29         ans = ans * 10 + c - ‘0‘;
 30         c = getchar();
 31     }
 32     return ans * f;
 33 }
 34 inline void addedge(int x,int y,int z){
 35     pt->pre = last[x]; pt->from = x; pt->to = y; pt->cost = z; last[x] = pt++;
 36 }
 37 inline void add(int x,int y,int z){
 38     addedge(x,y,z); addedge(y,x,0); last[x]->rev = last[y]; last[y]->rev = last[x];
 39 }
 40 bool bfs(){
 41     while (!q.empty()) q.pop();
 42     clr(d,-1); d[S] = 0; q.push(S);
 43     while (!q.empty()){
 44         int now = q.front(); q.pop();
 45         travel(now){
 46             if (d[p->to] == -1 && p->cost > 0){
 47                 d[p->to] = d[now] + 1;
 48                 q.push(p->to);
 49                 if (p->to == T) return 1;
 50             }
 51         }
 52     }
 53     return 0;
 54 }
 55 int dfs(int x,int flow){
 56     if (x == T || (!flow)) return flow; int w = 0;
 57     for(Edge *p=cur[x]; p && w < flow; p=p->pre){
 58         if (d[p->to] == d[x] + 1 && p->cost > 0){
 59             int delta = dfs(p->to,min(p->cost,flow-w));
 60             p->cost -= delta;
 61             p->rev->cost += delta;
 62             w += delta;
 63             if (p->cost) cur[x] = p;
 64         }
 65     }
 66     if (w < flow) d[x] = -1;
 67     return w;
 68 }
 69 void tarjan(int x){
 70     dfn[x] = low[x] = ++dfsclock;
 71     isin[x] = 1; s.push(x);
 72     travel(x) if (p->cost){
 73         if (!dfn[p->to]){
 74             tarjan(p->to);
 75             low[x] = min(low[x],low[p->to]);
 76         }
 77         else if (isin[p->to]) low[x] = min(low[x],dfn[p->to]);
 78     }
 79     if (low[x] == dfn[x]){
 80         scc++;
 81         while (s.top() != x){
 82             isin[s.top()] = 0;
 83             belong[s.top()] = scc;
 84             s.pop();
 85         }
 86         isin[x] = 0; belong[x] = scc; s.pop();
 87     }
 88 }
 89 int main(){
 90     n = read(); m = read(); S = read(); T = read();
 91     clr(last,0); pt = edge;
 92     rep(i,1,m){
 93         x = read(); y = read(); z = read();
 94         add(x,y,z);
 95     }
 96     while (bfs()){
 97         rep(i,1,n) cur[i] = last[i];
 98         dfs(S,INF);
 99     }
100     clr(dfn,0); clr(isin,0); rep(i,1,n) if (!dfn[i]) tarjan(i);
101     for (Edge *p=edge; p<=pt-2; p += 2){
102         if (p->cost) printf("0 0\n");
103         else{
104             if (belong[p->from] != belong[p->to]) printf("1 ");
105             else printf("0 ");
106             if (belong[p->from] == belong[S] && belong[p->to] == belong[T])
107             printf("1\n"); else printf("0\n");
108         }
109     }
110     return 0;
111 }

View Code

BZOJ1797 [AHOI2009] Mincut 最小割

Description

Input

Output