bzoj 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

Sample Output

10

【資料範圍】

對于100%的資料 T<=10,n<=150,m<=3000,q<=30，x在32位有符号整數類型範圍内。

圖中兩個點之間可能有多條邊

分治求最小割

s到t最小割為s.則s在殘餘網絡可以到的點集和t可以到的最小割可能為目前最小割。

然後分兩塊分治做取min即可求出兩兩間最小割

最後n^2暴力統計即可

#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int map[201][201];
struct line
{
     int s,t;
     int f;
     int la;
     bool flag;
     int next;
}a[6001];
int head[201];
int edge;
inline void add(int s,int t,int f)
{
	 a[edge].next=head[s];
	 head[s]=edge;
     a[edge].s=s;
     a[edge].t=t;
     a[edge].f=f;
     a[edge].la=f;
     a[edge].flag=true;
}
queue<int> Q;
int dep[201];
inline bool bfs(int ss,int tt)
{
	 memset(dep,-1,sizeof(dep));
	 Q.push(ss);
	 dep[ss]=0;
	 int i;
	 while(!Q.empty())
	 {
	      int d=Q.front();
	      Q.pop();
	      for(i=head[d];i!=0;i=a[i].next)
	      {
	           int t=a[i].t;
	           if(a[i].f>0&&dep[t]==-1) 
	           {
	                dep[t]=dep[d]+1;
	                Q.push(t);
	           }
	      }
	 }
     if(dep[tt]==-1)
          return false;
     return true;
}
inline int dfs(int d,int s,int tt)
{
     if(d==tt)
          return s;
     int i;
     int ts=s;
     for(i=head[d];i!=0;i=a[i].next)
     {
          int t=a[i].t;
		  if(dep[t]==dep[d]+1&&a[i].f>0)
		  {
		       int x=dfs(t,min(s,a[i].f),tt);
		       s-=x;
		       a[i].f-=x;
		       if(i%2==1)
		            a[i+1].f+=x;
		       else
		            a[i-1].f+=x;
		  }
	 }
	 if(ts==s)
	      dep[d]=-1;
	 return ts-s;
}
inline int dinic(int s,int t)
{
	 int ans=0;
     while(bfs(s,t))
          ans+=dfs(s,2100000000,t);
     return ans;
}
int sx[3001],tx[3001],xx[3001];
int n;
/*int v[1001];
inline void bfsx(int s,int xx)
{
     Q.push(s);
     v[s]=xx;
     int i;
     while(!Q.empty())
     {
          int d=Q.front();
          Q.pop();
          for(i=head[d];i!=0;i=a[i].next)
          {
               int t=a[i].t;
               int xt;
               if(i%2==0)
                    xt=a[i-1].f;
               else
                    xt=a[i+1].f;
               if(v[t]==0&&a[i].f>0&&a[i].flag)
               {
                    v[t]=1;
                    Q.push(t);
               }
          }
     }
}*/
bool vx[1001];
inline void bfsx2(int s,int xx)
{
	 memset(vx,false,sizeof(vx));
     Q.push(s);
  //   v[s]=xx;
     vx[s]=true;
     int i;
     while(!Q.empty())
     {
          int d=Q.front();
          Q.pop();
          for(i=head[d];i!=0;i=a[i].next)
          {
               int t=a[i].t;
               if(a[i].f>0/*&&xt>0*/&&!vx[t])
               {
               	    vx[t]=true;
               	   // if(v[t]==1)
                    //     v[t]=2;
                    Q.push(t);
               }
          }
     }
}
int b[1001],c[1001];
inline void solve(int s,int t)
{
	 if(s>=t)
	      return ;
   //  memset(v,0,sizeof(v));
//	 bfsx(s,1);
     int xt=dinic(b[s],b[t]);
     bfsx2(b[s],2);
     int i,j;
     for(i=1;i<=n;i++)
     {
     	/*  if(v[i]==2&&i!=s)
     	       s1=i;
     	  else if(v[i]==1&&i!=t)
     	       s2=i;*/
     	  if(!vx[i])
     	       continue;
     	  for(j=1;j<=n;j++)
     	  {
     	  	   if(vx[j]||i==j)
     	  	        continue;
     	  	  // {
                    map[i][j]=min(map[i][j],xt);
                    map[j][i]=min(map[j][i],xt);
               //}
          }
     }
     int p=0;
     for(i=s;i<=t;i++)
     {
          if(vx[b[i]])
          {
               p++;
               c[p]=b[i];
          }
     }
     int pp=p+s-1;
     for(i=s;i<=t;i++)
     {
          if(!vx[b[i]])
          {
               p++;
               c[p]=b[i];
          }
     }
     int p1=0;
     for(i=s;i<=t;i++)
     {
     	  p1++;
          b[i]=c[p1];
     }
     for(i=1;i<=edge;i++)
          a[i].f=a[i].la;
  //   if(xt!=0)
    // {
          solve(s,pp);
          solve(pp+1,t);
     //}
}
int px[1001];
int main()
{
     int T;
	 scanf("%d",&T);
	 while(T>0)
	 {
	 T--;
     int m;
     scanf("%d%d",&n,&m);
     int i,j,k;
     memset(head,0,sizeof(head));
     edge=0;
     for(i=1;i<=m;i++)
     {
          scanf("%d%d%d",&sx[i],&tx[i],&xx[i]);
          edge++;
          add(sx[i],tx[i],xx[i]);
          edge++;
          add(tx[i],sx[i],xx[i]);
     }
     memset(map,127/3,sizeof(map));
     for(i=1;i<=n;i++)
          map[i][i]=0;
     for(i=1;i<=n;i++)
          b[i]=i;
     solve(1,n);
     int q;
     scanf("%d",&q);
     int x;
     for(k=1;k<=q;k++)
     {
     scanf("%d",&x);
     int ans=0;
     for(i=1;i<=n;i++)
     {
          for(j=i+1;j<=n;j++)
          {
               if(map[i][j]==map[0][0]||map[i][j]<=x)
                    ans++;
          }
     }
     printf("%d\n",ans);
     }
     if(k!=q)
          printf("\n");
     }
     return 0;
}