题解 P4123 【[CQOI2016]不同的最小割】

· · 题解

你要相信一件事，dinic的渐进复杂度下界是O(V^2E)不是，一般情况下跑的比香港记者还快……，比如这道题的渐进复杂度是O(V^2E^2)……但是你可以凭借信仰过去

最小割树

最短路有最短路径树，那么最小割也有最小割树，我们考虑这样一个过程，我们现在做完了一个最小割，那么我们根据最小割的定义，我们可以推出来这样一个事实，如果原来的图是一个连通图，那么我们会发现，整个图被分为了两个联通块，而且只能分为两个联通块

那么这种做一个操作使得联通块一分为二的想法，让我们很自然的想到了树的一个性质，删一条边，整棵树分为两个联通块

那么我们似乎发现一件事，如果我们将最小割视为一条边，那么我们可以以一种奇妙的方式将无向图最小割间的逻辑关系映射到一只树上

具体来讲，对于树上任意两个相邻的节点S，T，我们满足删去它们之间的边之后两个不联通点集分布情况和对这个图执行一个S-T最小割之后，无向图分裂为的两个不联通点集的点分布情况相等，并且这个边的边权等于最小割

(通俗一点讲，最小割操作之后图分为两个联通块，删边操作后树分裂为两个联通块，我们通过一些技巧保证这4个联通块在点集意义上相等)

那么我们现在至少对于N-1个点，我们已经确保了对它们执行删边操作完全等价于执行最小割了，现在我们考虑树上任意两点u-v，我们枚举删除路径上的随意一条边，会发现这样相当于枚举删除后联通块情况，因此选取最小的边割掉即可

(也可用反证法，如果路径上的所有值都小于u-v最小割，由于割后必然分开了路径上的一些点，因此也就找出了新的最小割，与原来任意相邻点的边权都是最小割矛盾，得证)

现在我们发现对于最小割树上任意两点，最小割总是等于树上路径边权最小值，此时我们不要犯傻去写个倍增，而是采取枚举最小值，由于每个边权都有可能成为最小值，所以我们呢只需unique一下这个边权就好，或者可以直接set在线维护

求最小割树

答案很简单，分治

为什么是分治？，请注意我们在映射的时候是如何映射的，我们要求删掉这条边后联通块分布是等价于最小割的，因此我们可以这样做，我们一开始随便选两个点，之后跑一个最小割，那么此时我们分裂为两个点集，由于树的特点，我们不可以在两个点集之间再次连边，所以我们再次在两个点集间任意选择点连边即可，以后每次递归处理问题，只要保证分开的点集不会被再次连边即可

确定分开点集的方式，残量网络上和s相连的归到一个点集，然后补集归到T的点集，可以证明这总是一种可行方案

连边操作是在原图上跑最小割，因为我们连边本来是没有次序的，我们的映射保证的相邻点删边在点集意义上等价于相邻点最小割，而这个最小割明显是全图意义的。

那么具体来讲肯定有一些trick啦，比如写代码的时候每次按深度排一下序，那么我们呢会发现两个点集以深度是否为∞分成了两个区间，此时我们就可以像CDQ分治一样写这个程序了

本体中由于只是统计边的值种类，不需要真的把树建出来

剩下的细节就交给代码好了233

上代码~

#include<cstdio>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
const int N=900;const int M=9000;
struct data{int v;int nxt;int cot;}edge[2*M];
int alist[N];int cnt=1;int reset[2*M];int n;int m;
inline void add(int u,int v,int cot)
{
    edge[++cnt].v=v;edge[cnt].nxt=alist[u];alist[u]=cnt;edge[cnt].cot=cot;reset[cnt]=cot;
    edge[++cnt].v=u;edge[cnt].nxt=alist[v];alist[v]=cnt;edge[cnt].cot=cot;reset[cnt]=cot;
}int dep[N];queue <int> q;int a[N];//按深度排序 
inline bool cmp(int a,int b){return dep[a]<dep[b];}
inline bool bfs(int s,int t)//dinic板子 
{
    for(int i=1;i<=n;i++){dep[i]=0x3f3f3f3f;}
    dep[s]=0;q.push(s);
    while(!q.empty())
    {
        int now=q.front();q.pop();int nxt=alist[now];
        while(nxt)
        {
            int v=edge[nxt].v;int cot=edge[nxt].cot;
            if(dep[v]==0x3f3f3f3f&&cot!=0)
            {dep[v]=dep[now]+1;q.push(v);}
            nxt=edge[nxt].nxt;
        }
    }return dep[t]!=0x3f3f3f3f;
}
int dfs(int x,int t,int lim)
{
    if(x==t){return lim;}int nxt=alist[x];int nowflow=0;
    while(nxt)
    {
        if(lim==0)break;
        int v=edge[nxt].v;int cot=edge[nxt].cot;
        if(dep[v]==dep[x]+1&&cot!=0)
        {
            int del=dfs(v,t,min(lim,cot));lim-=del;nowflow+=del;
            edge[nxt].cot-=del;edge[nxt^1].cot+=del;
        }nxt=edge[nxt].nxt;
    }if(nowflow==0){dep[x]=0x3f3f3f3f;}
    return nowflow;
}set <int> se;
inline void solve(int l,int r)//由于按深度排序了，一个点集就是一个区间 
{
    if(r==l){return;}int res=0;int s=a[l];int nxt=alist[a[l]];
    while(bfs(a[l],a[r])){res+=dfs(a[l],a[r],0x3f3f3f3f);}//计算边权 
    se.insert(res);sort(a+l,a+r+1,cmp);int cut;//暴力找分割点了，懒得写lower_bound 
    for(int i=l;i<=r;i++){if(dep[a[i]]==0x3f3f3f3f){cut=i;break;}}
    for(int i=1;i<=cnt;i++){edge[i].cot=reset[i];}//记得复位整个图 
    solve(l,cut-1);solve(cut,r);//然后分治就好了 
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {int u;int v;int cot;scanf("%d%d%d",&u,&v,&cot);add(u,v,cot);}
    for(int i=1;i<=n;i++){a[i]=i;}solve(1,n);//初始化点集 
    printf("%d",se.size());return 0;//拜拜程序~ 
}