[toc]

题目链接：Luogu 3329/BZOJ 2229/ZJOI2011 D1T3。

一道 最小割树 的模板题。

题目

题意简述

给出一张 $n$ 个点 $m$ 条边的无向图，$q$ 次询问，图中有多少个无序点对的最小割的容量不超过 $x$。

本题输出格式比较毒瘤。

数据范围

$$1\leq T\leq 10$$

$$1\leq n\leq 150$$

$$0\leq m\leq 3000$$

$$0\leq x\leq 2^{31}-1$$

$$0\leq q\leq 30$$

时空限制

$$\text{Luogu}:1\text{s}/125\text{MiB}$$

$$\text{BZOJ}:10\text{s}/259\text{MiB}$$

题解

思路

观察发现，这是一道最小割树的模板题，程序的流程如下。

1. 读入图；
2. 构建最小割树；
3. 回答询问：
   1. 方式一：
      每次查询用 $\text{LCA}$ 暴力查询，单次查询的渐进时间复杂度为 $\Theta(n^2\log_2n)$。
   2. 方式二：
      离散化边权+暴力预处理+树状数组查询。
      预处理的渐进时间复杂度为 $\Theta(n^2\log_2n)$，单次查询的时间复杂度为$\Theta(\log_2m)$，其中 $m$ 表示不同边权的数量。
   3. 方式三：
      普通的树形 DP。
      单次查询的时间复杂度为 $\Theta(n^2)$
   4. 方式四：
      离散化边权+普通树形 DP 预处理+树状数组查询。
      预处理的渐进时间复杂度为 $\Theta(n^2)$，单次查询的时间复杂度为$\Theta(\log_2m)$，其中 $m$ 表示不同边权的数量（即树状数组的大小）。
   5. 方式五：
      换根 DP。（该方法只是听说，没有仔细探究过）。
      渐进时间复杂度好像是 $\Theta(n)$。

总的来说，五种方法都能过。

代码

下面给出方式一的代码。

方式一

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define INF 0X7FFFFFFF
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){ //读入优化
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=150+5;
const int MAXLOG2N=8+1;
const int MAXM=3000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    reg int T=read(); //多组数据
    while(T--){
        Read();
        Work();
        putchar('\n'); //毒瘤输出格式
    }
    return 0;
}

struct Graph{ //存图的结构体
    int cnt,head[MAXN],to[MAXM<<1],w[MAXM<<1],Next[MAXM<<1];
    inline void Init(void){
        cnt=1;
        memset(head,0,sizeof(head));
        return;
    }
    inline void Add_Edge(reg int u,reg int v,reg int len){
        Next[++cnt]=head[u];
        to[cnt]=v;
        w[cnt]=len;
        head[u]=cnt;
    }
    inline void Add_Tube(reg int u,reg int v,reg int len){
        Add_Edge(u,v,len);
        Add_Edge(v,u,len);
        return;
    }
};

int n,m;
Graph G,T; //G 是原图，T 是最小割树

inline void Read(void){
    n=read(),m=read();
    G.Init();
    for(reg int i=1;i<=m;++i){
        static int u,v,c;
        u=read(),v=read(),c=read();
        G.Add_Tube(u,v,c);
    }
    return;
}

int dep[MAXN];
queue<int> Q;

inline bool BFS(int s,reg int t,Graph& G){
    memset(dep,-1,sizeof(dep));
    while(!Q.empty())Q.pop();
    dep[s]=1,Q.push(s);
    while(!Q.empty()){
        reg int ID=Q.front();
        Q.pop();
        for(reg int i=G.head[ID];i;i=G.Next[i])
            if(dep[G.to[i]]==-1&&G.w[i]>0){
                dep[G.to[i]]=dep[ID]+1;
                Q.push(G.to[i]);
            }
    }
    return dep[t]!=-1;
}

int cur[MAXN];

inline int DFS(reg int ID,reg int t,reg int lim,Graph& G){
    if(ID==t)
        return lim;
    reg int flow=0;
    for(reg int &i=cur[ID];i;i=G.Next[i])
        if(dep[G.to[i]]==dep[ID]+1&&G.w[i]>0){
            reg int f=DFS(G.to[i],t,min(lim-flow,G.w[i]),G);
            if(f){
                flow+=f;
                G.w[i]-=f;
                G.w[i^1]+=f;
                if(flow==lim)
                    break;
            }
        }
    return flow;
}

inline int Dinic(reg int s,reg int t,Graph& G){
    reg int res=0;
    while(BFS(s,t,G)){
        memcpy(cur,G.head,sizeof(G.head));
        res+=DFS(s,t,INF,G);
    }
    return res;
}

int W[MAXM<<1];
bool vis[MAXN];
int p[MAXN];

inline void DFS(reg int ID,Graph& G){
    vis[ID]=true;
    for(reg int i=G.head[ID];i;i=G.Next[i])
        if(!vis[G.to[i]]&&G.w[i]>0)
            DFS(G.to[i],G);
    return;
}

int fa[MAXN][MAXLOG2N];
int Min[MAXN][MAXLOG2N];

inline void DFS(reg int ID,reg int father,Graph& T){
    fa[ID][0]=father;
    dep[ID]=dep[father]+1;
    for(reg int i=1;i<MAXLOG2N;++i){
        fa[ID][i]=fa[fa[ID][i-1]][i-1];
        Min[ID][i]=min(Min[ID][i-1],Min[fa[ID][i-1]][i-1]);
    }
    for(reg int i=T.head[ID];i;i=T.Next[i])
        if(T.to[i]!=father){
            Min[T.to[i]][0]=T.w[i];
            DFS(T.to[i],ID,T);
        }
    return;
}

inline pair<int,int> LCA(int x,int y){
    if(dep[x]>dep[y])
        swap(x,y);
    int res_Min=INF;
    for(reg int i=MAXLOG2N-1;i>=0;--i)
        if(dep[fa[y][i]]>=dep[x]){
            res_Min=min(res_Min,Min[y][i]);
            y=fa[y][i];
        }
    if(x==y)
        return make_pair(x,res_Min);
    for(reg int i=MAXLOG2N-1;i>=0;--i)
        if(fa[x][i]!=fa[y][i]){
            res_Min=min(res_Min,min(Min[x][i],Min[y][i]));
            x=fa[x][i],y=fa[y][i];
        }
    return make_pair(fa[x][0],min(res_Min,min(Min[x][0],Min[y][0])));
}

inline void Work(void){
    for(reg int i=1;i<=G.cnt;++i)
        W[i]=G.w[i];
    T.Init();
    for(reg int i=2;i<=n;++i)
        p[i]=1;
    for(reg int i=2;i<=n;++i){
        reg int s=i,t=p[i];
        for(reg int j=1;j<=G.cnt;++j)
            G.w[j]=W[j];
        reg int ans=Dinic(s,t,G);
        memset(vis,false,sizeof(vis));
        DFS(s,G);
        T.Add_Tube(s,t,ans);
        for(reg int j=i;j<=n;++j)
            if(vis[j]&&p[j]==t)
                p[j]=s;
    }
    DFS(1,0,T); //遍历整棵树，进行 LCA 的预处理
    reg int q=read();
    while(q--){
        reg int x=read();
        reg int ans=0;
        for(reg int i=1;i<=n;++i)
            for(reg int j=i+1;j<=n;++j) //注意是无序点对
                if(LCA(i,j).second<=x)
                    ++ans;
        printf("%d\n",ans); //输出答案
    }
    return;
}

最小割树相关：「题解」「CQOI2016」不同的最小割。