2229: [Zjoi2011]最小割(最小割树)

Description

小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： “对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割” 现给定一张无向图，小白有若干个形如“图中有多少对点它们的最小割的容量不超过x呢”的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为仍然是小蓝的好友，你又有任务了。

Input

输入文件第一行有且只有一个正整数T，表示测试数据的组数。对于每组测试数据，第一行包含两个整数n,m，表示图的点数和边数。下面m行，每行3个正整数u,v,c(1<=u,v<=n,0<=c<=106)，表示有一条权为c的无向边(u,v) 接下来一行，包含一个整数q，表示询问的个数下面q行，每行一个整数x，其含义同题目描述。

Output

对于每组测试数据，输出应包括q行，第i行表示第i个问题的答案。对于点对(p,q)和(q,p)，只统计一次（见样例）。

两组测试数据之间用空行隔开。

Sample Input

1
5 0
1
0

Sample Output

【数据范围】
对于100%的数据 T<=10,n<=150,m<=3000,q<=30，x在32位有符号整数类型范围内。
图中两个点之间可能有多条边

解题思路：

最小割树，用于解决全局任意点间的最小割。

考虑对于全局任意两个点的最小割将图分成的两部分，假如说我们在这两部分之间画一条分界线。

那么在两端各取一点再跑最小割，这时再画分界线，若两者最小割容量不同，那么那么这两条分界线一定没有交集。

贪心地想，若其中一个更优那么一定会取。

若第二条比第一条更优，那么一定说明第一遍时的两个点在第二条分界线同侧。

同时也说明，第二条分界线后除第二遍的终点以外，还会有点与这个点的最小割形成的割集与第二个割集相同。

所以可以每次取两个点跑最小割，划线。

然后下次在线同侧取点跑最小割划线，在线两端的点一定以这个割集为割集，所以更新答案即可。

分治的最坏时间复杂度为$O(n^2)$的，再套个Dinic时间复杂度为$O(n^4m)$的，不过这都是最坏的。

后者达上限非常困难前者也不容易。所以还是$O(玄学)$比较合适。

代码：

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 const int oo=0x3f3f3f3f;

 struct pnt{

     int hd;

     int lyr;

     int now;

     bool vis;

 }p[];

 struct ent{

     int twd;

     int lst;

     int vls;

     int his;

 }e[];

 int cnt;

 int n,m;

 int s,t;

 int app[];

 int tmp[];

 int ans[][];

 std::queue<int>Q;

 void ade(int f,int t,int v)

 {

     cnt++;

     e[cnt].twd=t;

     e[cnt].vls=v;

     e[cnt].his=v;

     e[cnt].lst=p[f].hd;

     p[f].hd=cnt;

     return ;

 }

 bool Bfs(void)

 {

     while(!Q.empty())Q.pop();

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

         p[i].lyr=;

     p[s].lyr=;

     Q.push(s);

     while(!Q.empty())

     {

         int x=Q.front();

         Q.pop();

         for(int i=p[x].hd;i;i=e[i].lst)

         {

             int to=e[i].twd;

             if(p[to].lyr==&&e[i].vls>)

             {

                 p[to].lyr=p[x].lyr+;

                 if(to==t)

                     return true;

                 Q.push(to);

             }

         }

     }

     return false;

 }

 int Dfs(int x,int fll)

 {

     if(x==t)

         return fll;

     for(int& i=p[x].now;i;i=e[i].lst)

     {

         int to=e[i].twd;

         if(p[to].lyr==p[x].lyr+&&e[i].vls>)

         {

             int ans=Dfs(to,std::min(fll,e[i].vls));

             if(ans>)

             {

                 e[i].vls-=ans;

                 e[((i-)^)+].vls+=ans;

                 return ans;

             }

         }

     }

     return ;

 }

 int Dinic()

 {

     int ans=;

     while(Bfs())

     {

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

             p[i].now=p[i].hd;

         int dlt;

         while(dlt=Dfs(s,oo))

             ans+=dlt;

     }

     return ans;

 }

 void dfs(int x)

 {

     if(p[x].vis)

         return ;

     p[x].vis=true;

     for(int i=p[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         if(e[i].vls>)

             dfs(to);

     }

     return ;

 }

 void Build(int l,int r)

 {

     if(l==r)

         return ;

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

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

     {

         e[i].vls=e[i].his;

         e[i+].vls=e[i+].his;

         e[i+].vls=e[i+].his;

         e[i+].vls=e[i+].his;

     }

     int tmf=Dinic();

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

         p[i].vis=false;

     dfs(s);

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

         if(p[i].vis)

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

                 if(!p[j].vis)

                     ans[i][j]=ans[j][i]=std::min(ans[i][j],tmf);

     int i=l-,j=r+;

     for(int k=l;k<=r;k++)

         if(p[app[k]].vis)

             tmp[++i]=app[k];

         else

             tmp[--j]=app[k];

     for(int k=l;k<=r;k++)

         app[k]=tmp[k];

     Build(l,i);

     Build(j,r);

     return ;

 }

 int main()

 {

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

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         cnt=;

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

             app[i]=i,

             p[i].hd=;

         memset(ans,0x3f,sizeof(ans));

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

         {

             int a,b,c;

             scanf("%d%d%d",&a,&b,&c);

             ade(a,b,c);

             ade(b,a,c);

         }

         Build(,n);

         int q;

         scanf("%d",&q);

         while(q--)

         {

             int x;

             scanf("%d",&x);

             int ansl=;

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

                 for(int j=i+;j<=n;j++)

                     if(ans[i][j]<=x)

                         ansl++;

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

         }

         puts("");

     }

     return ;

 }

巴特西