[AHOI2009]最小割最小割可行边&必须边

~~~题面~~~

题解：

做这题的时候才知道有最小割可行边和必须边这种东西。。。。。

1，最小割可行边,

意思就是最小割中可能出现的边。

充要条件：

　　1，满流

　　2，在残余网络中找不到x ---> y的路径

解释：

如果在残余网络中还找得到x ---> y的路径的话，要割掉这条边就还需要割掉另一条路径，这显然是不够优的。

如果是满流的话显然不是割掉了这条边

2，最小割必须边

　　1，满流

　　2，在残余网络中s 可以到 x， y 可以到 t。

解释：

满流的原因和上面原因，同时必须边肯定也是可行边（显然可行边的范围就要大一些嘛）。

如果满流但s不能到x or y 不能到 t，因为这样的话说明在s 到 x（y 到 t）的路上就已经被割掉了，而不是在这里割的。

但是因为满流了，所以这是可行的，但是由于割在别的地方，说明不是必须的。

因此s 必须可以到 x， y 必须可以到s才能保证是必须边，而不是可行边

至于实现方法就比较妙了。

如果两个点在一个scc中则表示可以到。

因此可行边需要保证x和y不在一个scc中。

而必须边则还需要额外保证s 和 x 属于一个scc， y 和 t属于一个scc

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define R register int
  4 #define getchar() *o++
  5 #define inf 2139062143
  6 #define AC 5000
  7 #define ac 150000
  8 #define D printf("line in %d
", __LINE__);
  9 char READ[7000100], *o = READ;
 10 int n, m, s, t, ans, x, cnt, addflow;
 11 int last[AC], c[AC], have[AC], good[AC];
 12 int date[ac], Next[ac], belong[ac], haveflow[ac], Head[AC], tot = 1;//前向星
 13 int low[AC], dfn[AC], scc[AC], timer;//tarjan
 14 int q[AC], head, tail;//队列
 15 int Stack[AC], top;
 16 bool z[AC];//用于tarjan
 17 
 18 inline int read()
 19 {
 20     int x = 0; char c = getchar();
 21     while(c > '9' || c < '0') c = getchar();
 22     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
 23     return x; 
 24 }
 25 
 26 inline void upmin(int &a, int b)
 27 {
 28     if(a > b) a = b;
 29 }
 30 
 31 inline void add(int f, int w, int S)
 32 {
 33     date[++tot] = w, Next[tot] = Head[f], Head[f] = tot, haveflow[tot] = S, belong[tot] = f;
 34     date[++tot] = f, Next[tot] = Head[w], Head[w] = tot;
 35 }
 36 
 37 void pre()
 38 {
 39     int u, v, e;
 40     n = read(), m = read(), s = read(), t = read();
 41     for(R i = 1; i <= m; i++)
 42     {
 43         u = read(), v = read(), e = read();
 44         add(u, v, e);
 45     }
 46 }
 47 
 48 void bfs()
 49 {
 50     int x, now;
 51     c[t] = 1, have[1] = 1, q[++tail] = t;
 52     while(head < tail)
 53     {
 54         x = q[++head]; 
 55         for(R i = Head[x]; i ; i = Next[i])
 56         {
 57             now = date[i];
 58             if(haveflow[i ^ 1] && !c[now])
 59             {
 60                 c[now] = c[x] + 1;
 61                 ++have[c[now]];
 62                 q[++tail] = now;
 63             }
 64         }
 65     }
 66     memcpy(good, Head, sizeof(good));
 67 }
 68 
 69 void aru()
 70 {
 71     while(x != s)
 72     {
 73         haveflow[last[x]] -= addflow;
 74         haveflow[last[x] ^ 1] += addflow;
 75         x = date[last[x] ^ 1];
 76     }
 77     ans += addflow;
 78 }
 79 
 80 void isap()
 81 {
 82     int now; bool done;
 83     x = s, addflow = inf;
 84     while(c[s] != 4801)
 85     {
 86         if(x == t) aru(), addflow = inf;
 87         done = false;
 88         for(R i = good[x]; i ; i = Next[i])
 89         {
 90             now = date[i];
 91             if(haveflow[i] && c[now] == c[x] - 1)
 92             {
 93                 done = true;
 94                 upmin(addflow, haveflow[i]);
 95                 good[x] = last[now] = i;
 96                 x = now;
 97                 break;
 98             }
 99         }
100         if(!done)
101         {
102             int go = 4800;
103             for(R i = Head[x]; i ; i = Next[i])
104             {
105                 now = date[i];
106                 if(haveflow[i] && c[now]) upmin(go, c[now]);
107             }
108             good[x] = Head[x];//error！！！不要忘了重置
109             if(!(--have[c[x]])) break;
110             ++have[c[x] = go + 1];
111             if(x != s) x = date[last[x] ^ 1];
112         }
113     }
114 }
115 
116 void tarjan(int x)
117 {
118     int now;
119     dfn[x] = low[x] = ++timer;
120     z[x] = true;
121     Stack[++top] = x;
122     for(R i = Head[x]; i ; i = Next[i])
123     {
124         if(!haveflow[i]) continue;//流满表示不联通
125         now = date[i];
126         if(!dfn[now]) 
127         {
128             tarjan(now);
129             upmin(low[x], low[now]);
130         }
131         else if(z[now]) upmin(low[x], low[now]);
132     }
133     if(dfn[x] == low[x])
134     {
135         ++cnt;
136         while(Stack[top] != x)
137         {
138             now = Stack[top--];
139             scc[now] = cnt;
140             z[now] = false;
141         }
142         now = Stack[top--];
143         scc[now] = cnt;
144         z[now] = false;
145     }
146 }
147 
148 void work()
149 {
150     int x, y;
151     for(R i = 2; i <= tot; i += 2)
152     {
153         x = belong[i], y = date[i];
154     //    printf("%d %d
", x, y);
155         if(!haveflow[i] && scc[x] != scc[y])
156         {
157             printf("1 ");
158             if(scc[x] == scc[s] && scc[y] == scc[t]) printf("1
");
159             else printf("0
");
160         }
161         else printf("0 0
");
162     }
163 }
164 
165 int main()
166 {
167 //    freopen("in.in", "r", stdin);
168     fread(READ, 1, 7000000, stdin);
169     pre();
170     bfs();
171     isap();
172     for(R i=1;i<=n;i++) 
173         if(!dfn[i]) tarjan(i);
174 //    for(R i=1;i<=n;i++) printf("%d ", scc[i]);
175 //    printf("
");
176 //    for(R i=2;i<=tot;i++) printf("%d ", haveflow[i]);
177     work();
178 //    fclose(stdin);
179     return 0;
180 }

[AHOI2009]最小割 最小割可行边&必须边

[AHOI2009]最小割最小割可行边&必须边