[ZJOI2011]最小割 & [CQOI2016]不同的最小割分治求最小割

题面：

[ZJOI2011]最小割

[CQOI2016]不同的最小割

题解：

其实这两道是同一道题。。。。

最小割是用的dinic，不同的最小割是用的isap

其实都是分治求最小割

简单讲讲思路吧

就是首先全部的点都在一个集合里，然后随意定两个点为s和t，这里默认是第一个和最后一个。

然后找到最小割，最小割将整张图分为了s集和t集，于是我们再用这个最小割更新跨集合点对之间的最小割。

这个很好理解，因为当前找到的最小割将s集和t集分开了，显然对于任意一组跨集合的点对而言，当前最小割都是一个可能的最小割。

然后我们再递归处理s集和t集（重复以上步骤）。

每次找到最小割后就更新跨集合点对。

本质上是分治吧。

之前看有些地方提到了最小割树，这里放个链接（这是我找到的写的最全的一篇了）

Gomory-Hu tree 最小割树

下面放代码吧，个人觉得看代码会更好理解，尤其是对分治不熟悉的人（比如我）

不同的最小割（isap）：

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 900

 #define ac 20000

 #define inf 2139062143

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

 char READ[], *o = READ;

 int n, m, s, addflow, t, answer, tt;

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

 int Head[AC], date[ac], Next[ac], haveflow[ac], tot = ;

 int q[AC], head, tail;

 int ss[], cnt;

 bool z[AC];

 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 add(int f, int w, int S)

 {

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

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

     //printf("%d ---> %d %d\n", f, w, S);

 }

 inline void upmin(int &a, int b)

 {

     if(b < a) a = b;

 }

 void pre()

 {

     int u, v, e;

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

     for(R i = ; i <= n; i++) a[i] = i;

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

     {

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

         add(u, v, e);

     }

     memset(ans, , sizeof(ans));

 }

 bool bfs()

 {

     int x, now;

     memset(have, , sizeof(have));

     memset(c, , sizeof(c));

     have[] = , c[t] = , x = t;

     head = tail = ;

     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]];//error...忘记统计了

                 q[++tail] = now;

             }

         }

     }

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

     return c[s];

 }

 inline void aru()

 {

     int x = t;

     while(x != s)

     {

         haveflow[last[x]] -= addflow;

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

         x = date[last[x] ^ ];

     }

     tt += addflow;

 }

 void isap()

 {

     int x = s, now; bool done;

     tt = , addflow = inf;

     while(c[s] != )

     {

         if(x == t) aru(), addflow = inf, x = s;//忘记设置全局了，，，那在这里手动改一下吧

         done = false;

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

         {

             now = date[i];

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

             {

                 upmin(addflow, haveflow[i]);

                 done = true;

                 last[now] = i;

                 good[x] = 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];

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

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

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

         }

     }

 }

 void restore()//还原

 {

     for(R i = ; i <= tot; i += )//对于无向图而言，这还是非常妙的

         haveflow[i] = haveflow[i ^ ] = (haveflow[i] + haveflow[i ^ ]) / ;

 }

 void dfs(int x)

 {

     int now;

     z[x] = true;//....

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

     {

         now = date[i];

         if(haveflow[i] && !z[now]) dfs(now);

     }

 }

 void solve(int l, int r)

 {

     if(l == r) return ;

     s = a[l], t = a[r];

     restore();

     //printf("%d %d\n", l, r);

     bfs();//重新定层次

     isap();

     memset(z, , sizeof(z));

     dfs(s);

     for(R i=;i<=n;i++)//更新最小割

         if(z[i])

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

                 if(!z[j])

                     ans[i][j] = ans[j][i] = min(ans[i][j], tt);

     int ll = l - , rr = r + ;

     for(R i = l; i <= r; i++)

         if(z[a[i]]) q[++ll] = a[i];

         else q[--rr] = a[i];//不知道取什么名字了，先借这个用一下吧

     for(R i = l; i <= r; i++) a[i] = q[i];

     solve(l, ll), solve(rr, r);

 }

 void work()

 {

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

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

             ss[++cnt] = ans[i][j];

     sort(ss + , ss + cnt + );

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

         if(ss[i] != ss[i + ]) ++answer;

     printf("%d\n", answer);

 }

 int main()

 {

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

     pre();

     solve(, n);

     work();

 //    fclose(stdin);

     return ;

 }

最小割（dinic）：

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define LL long long

 #define inf 2139062143

 #define getchar() *o++

 #define AC 155

 #define ac 101000

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

 char READ[], *o = READ;

 int s, t, T, Q, n, m;

 int last[AC], ans[AC][AC], a[AC], tmp[AC], c[AC];

 int date[ac], Next[ac], haveflow[ac], Head[AC], tot;

 int q[AC], head, tail;

 bool z[AC];

 inline int read()

 {

     int x = ;char c = getchar();bool z = false;

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

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

     if(!z) return x;

     else return -x;

 }

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

 {//因为是双向边，所以反向边就可以省掉了

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

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

 //    printf("%d ---> %d %d\n", f, w, S);

 }

 bool bfs()

 {

     int now, x;

     head  = tail = ;

     memset(c, , sizeof(c));

     c[s] = , q[++tail] = s;

     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] + ;

                 q[++tail] = now;

             }

         }

     }

     return c[t];

 }

 int dfs(int x, int flow)

 {

     if(x == t) return flow;

     int addflow, used = , now;

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

     {

         now = date[i];

         if(c[now] == c[x] + )

         {//流到下一个点去的流量在haveflow和剩余流量中取最小值

             addflow = dfs(now, min(haveflow[i], flow - used));

             haveflow[i] -= addflow;

             haveflow[i^] += addflow;

             used += addflow;

             if(used == flow) return flow;

         }

     }

     if(!used) c[x] = ;

     return used;

 }

 int dinic()

 {

     int rnt = ;

     while(bfs()) rnt += dfs(s, inf);

     return rnt;

 }

 void DFS(int x)//标记能到的点，便于区分

 {

     int now;

     z[x]= ;

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

     {

         now = date[i];

         if(haveflow[i] && !z[now]) DFS(now);

     }

 }

 void restore()//挺妙的还原流量的方法，因为这两条边即是双向边，又可以当反向边

 {//因此总流量肯定是不会变的，所以加起来取个平均值就相当于还原了

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

         haveflow[i] = haveflow[i+] = (haveflow[i] + haveflow[i+]) / ;

 }

 void solve(int l, int r)

 {

     if(l == r) return ;

     restore();

     s = a[l], t = a[r];//随便选两个作为s和t

     int tt = dinic();//跑最小割

     memset(z, , sizeof(z));

     DFS(s);//查看哪些点是能到的(即没有被割断）

     for(R i=;i<=n;i++)//这里是在每次找到一个最小割的时候，就对跨集合点对的割进行更新，

         if(z[i])//因此每次是需要枚举所有点对的。不然的话因为i是枚举的s集里面的东西，可能会导致某些点对没有被统计到

             for(R j=;j<=n;j++)//获取跨集合点对的割的大小

                 if(!z[j]) ans[i][j] = ans[j][i] = min(ans[i][j], tt);

     int ll = l - , rr = r + ;

     for(R i = l; i <= r; i++)

         if(z[a[i]])//如果这个点可以属于s集

             tmp[++ll] = a[i];//加入左边（从左边开始塞）

         else tmp[--rr] = a[i];//不然就放在右边

     for(R i=l;i<=r;i++) a[i] = tmp[i];//类似于归并排序的，，，放回数组内

     solve(l, ll), solve(rr, r);

 }

 void pre()

 {

     int u, v, k;

     tot  = ;

     memset(ans, , sizeof(ans));

     memset(Head, , sizeof(Head));

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

     for(R i=;i<=n;i++) a[i] = i;//先把点按顺序放进来

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

     {

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

         add(u, v, k);

     }

     solve(, n);//找出所有最小割

 }

 void work()

 {

     int k, cnt;

     Q = read();

     while(Q--)

     {

         k = read(), cnt = ;

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

             for(R j=;j<i;j++)//不能一个点对重复统计了

                 if(ans[i][j] <= k) ++cnt;

         printf("%d\n", cnt);

     }

     printf("\n");

 }

 int main()

 {

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

     fread(READ, , , stdin);

     T = read();

     while(T--)

     {

         pre();

         work();

     }

 //    fclose(stdin);

     return ;

 }

巴特西

[ZJOI2011]最小割 & [CQOI2016]不同的最小割分治求最小割

最新文章

热门文章

巴特西

[ZJOI2011]最小割 & [CQOI2016]不同的最小割 分治求最小割

最新文章

热门文章

[ZJOI2011]最小割 & [CQOI2016]不同的最小割分治求最小割