BZOJ2229:[Zjoi2011]最小割 最小割树

思路:

无向图的任意两点之间的最小割可以用一颗树来表示.

构造方法:

在当前的连通集合中任取两点(若当前连通集合仅有一个点退出),并在原图中求这两点之间的最小割.

在最小割树上连接这两个点,边权为刚才求出的最小割.

将当前的连通集合根据刚才的割划分为两部分,递归处理.

求出最小割树之后,两个点之间的最小割即为最小割树上两个点之间的路径上的边权最小值.

这道题就这样水就行了.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cstdlib>
#include<iostream>
using namespace std;
 
#define INF 0x3f3f3f3f
 
#define N 160
int n,m,G[N][N];
 
struct MaxflowSolver{
    int head[N],next[N*N<<1],end[N*N<<1],flow[N*N<<1],ind;
    int d[N],gap[N],stk[N],top,cur[N];
    inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline void make2(int a,int b,int f){addedge(a,b,f),addedge(b,a,f);}
    inline void bfs(int T){
        static int q[N];int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T,int cnt){
        int Min,ins,res=0,i,u=S;bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find)stk[top++]=cur[u]=ins,u=end[ins];
            else{
                Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}Curse;
 
struct Graph{
    int head[N],next[N*N<<1],end[N*N<<1],ind;
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q;}
    inline void make(int a,int b){addedge(a,b),addedge(b,a);}
}SteinsGate;
 
int totalState[N],totalid;bool totalvis[N];
void dfs(int x){
    totalvis[x]=1,totalState[++totalid]=x;
    for(int j=SteinsGate.head[x];j!=-1;j=SteinsGate.next[j])if(!totalvis[SteinsGate.end[j]])dfs(SteinsGate.end[j]);
}
 
struct Tree{
    int head[N],next[N<<1],end[N<<1],len[N<<1],ind;
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int l){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,len[q]=l;}
    inline void make(int a,int b,int l){addedge(a,b,l),addedge(b,a,l);}
}T;
 
int inS[N],q[N],fr,ta;
void Solve(int State[],int n){
    if(n==1)return;
     
    register int i,j;
    Curse.reset();
    for(i=1;i<=totalid;++i)for(j=i+1;j<=totalid;++j)if(G[totalState[i]][totalState[j]])
        Curse.make2(totalState[i],totalState[j],G[totalState[i]][totalState[j]]);
     
    int res=Curse.Maxflow(State[1],State[2],totalid);
     
    T.make(State[1],State[2],res);
     
    memset(inS,0,sizeof inS);fr=ta=0;q[ta++]=State[1];
    while(fr^ta){
        i=q[fr++];inS[i]=1;for(j=Curse.head[i];j!=-1;j=Curse.next[j])if(Curse.flow[j]&&!inS[Curse.end[j]])q[ta++]=Curse.end[j];
    }
     
    int seql[N],numl=0,seqr[N],numr=0;
    for(i=1;i<=n;++i)if(inS[State[i]])seql[++numl]=State[i];else seqr[++numr]=State[i];
     
    Solve(seql,numl);
    Solve(seqr,numr);
}
 
int ans[N][N];
inline void getans(int anc,int x,int fa,int nowans){
    ans[anc][x]=nowans;
    for(int j=T.head[x];j!=-1;j=T.next[j])if(T.end[j]!=fa)getans(anc,T.end[j],x,min(T.len[j],nowans));
}
 
int seq[N*N],nums;
int main(){
    int Tec;scanf("%d",&Tec);register int i,j;int a,b,x;
    while(Tec--){
        scanf("%d%d",&n,&m);
        memset(G,0,sizeof G);while(m--)scanf("%d%d%d",&a,&b,&x),G[a][b]+=x,G[b][a]+=x;
        SteinsGate.reset();for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(G[i][j])SteinsGate.make(i,j);
         
        memset(totalvis,0,sizeof totalvis);
        T.reset();
        for(i=1;i<=n;++i)if(!totalvis[i]){
            totalid=0;
            dfs(i);
             
            Solve(totalState,totalid);
        }
         
        nums=0;
        for(i=1;i<=n;++i){
            getans(i,i,-1,INF);
            for(j=i+1;j<=n;++j)seq[++nums]=ans[i][j];
        }
         
        int Q;scanf("%d",&Q);
        while(Q--){
            scanf("%d",&x);
            int res=0;for(i=1;i<=nums;++i)if(seq[i]<=x)++res;
            printf("%d\n",res);
        }
        puts("");
         
    }
     
    return 0;
}