[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

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define getchar() *o++

 #define inf 2139062143

 #define AC 5000

 #define ac 150000

 #define D printf("line in %d\n", __LINE__);

 char READ[], *o = READ;

 int n, m, s, t, ans, x, cnt, addflow;

 int last[AC], c[AC], have[AC], good[AC];

 int date[ac], Next[ac], belong[ac], haveflow[ac], Head[AC], tot = ;//前向星

 int low[AC], dfn[AC], scc[AC], timer;//tarjan

 int q[AC], head, tail;//队列

 int Stack[AC], top;

 bool z[AC];//用于tarjan

 inline int read()

 {

     int x = ; char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 inline void upmin(int &a, int b)

 {

     if(a > b) a = b;

 }

 inline void add(int f, int w, int S)

 {

     date[++tot] = w, Next[tot] = Head[f], Head[f] = tot, haveflow[tot] = S, belong[tot] = f;

     date[++tot] = f, Next[tot] = Head[w], Head[w] = tot;

 }

 void pre()

 {

     int u, v, e;

     n = read(), m = read(), s = read(), t = read();

     for(R i = ; i <= m; i++)

     {

         u = read(), v = read(), e = read();

         add(u, v, e);

     }

 }

 void bfs()

 {

     int x, now;

     c[t] = , have[] = , q[++tail] = t;

     while(head < tail)

     {

         x = q[++head];

         for(R i = Head[x]; i ; i = Next[i])

         {

             now = date[i];

             if(haveflow[i ^ ] && !c[now])

             {

                 c[now] = c[x] + ;

                 ++have[c[now]];

                 q[++tail] = now;

             }

         }

     }

     memcpy(good, Head, sizeof(good));

 }

 void aru()

 {

     while(x != s)

     {

         haveflow[last[x]] -= addflow;

         haveflow[last[x] ^ ] += addflow;

         x = date[last[x] ^ ];

     }

     ans += addflow;

 }

 void isap()

 {

     int now; bool done;

     x = s, addflow = inf;

     while(c[s] != )

     {

         if(x == t) aru(), addflow = inf;

         done = false;

         for(R i = good[x]; i ; i = Next[i])

         {

             now = date[i];

             if(haveflow[i] && c[now] == c[x] - )

             {

                 done = true;

                 upmin(addflow, haveflow[i]);

                 good[x] = last[now] = i;

                 x = now;

                 break;

             }

         }

         if(!done)

         {

             int go = ;

             for(R i = Head[x]; i ; i = Next[i])

             {

                 now = date[i];

                 if(haveflow[i] && c[now]) upmin(go, c[now]);

             }

             good[x] = Head[x];//error！！！不要忘了重置

             if(!(--have[c[x]])) break;

             ++have[c[x] = go + ];

             if(x != s) x = date[last[x] ^ ];

         }

     }

 }

 void tarjan(int x)

 {

     int now;

     dfn[x] = low[x] = ++timer;

     z[x] = true;

     Stack[++top] = x;

     for(R i = Head[x]; i ; i = Next[i])

     {

         if(!haveflow[i]) continue;//流满表示不联通

         now = date[i];

         if(!dfn[now])

         {

             tarjan(now);

             upmin(low[x], low[now]);

         }

         else if(z[now]) upmin(low[x], low[now]);

     }

     if(dfn[x] == low[x])

     {

         ++cnt;

         while(Stack[top] != x)

         {

             now = Stack[top--];

             scc[now] = cnt;

             z[now] = false;

         }

         now = Stack[top--];

         scc[now] = cnt;

         z[now] = false;

     }

 }

 void work()

 {

     int x, y;

     for(R i = ; i <= tot; i += )

     {

         x = belong[i], y = date[i];

     //    printf("%d %d\n", x, y);

         if(!haveflow[i] && scc[x] != scc[y])

         {

             printf("1 ");

             if(scc[x] == scc[s] && scc[y] == scc[t]) printf("1\n");

             else printf("0\n");

         }

         else printf("0 0\n");

     }

 }

 int main()

 {

 //    freopen("in.in", "r", stdin);

     fread(READ, , , stdin);

     pre();

     bfs();

     isap();

     for(R i=;i<=n;i++)

         if(!dfn[i]) tarjan(i);

 //    for(R i=1;i<=n;i++) printf("%d ", scc[i]);

 //    printf("\n");

 //    for(R i=2;i<=tot;i++) printf("%d ", haveflow[i]);

     work();

 //    fclose(stdin);

     return ;

 }

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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