(未完待续)
题目链接:Luogu P4123/BZOJ 4519/LibreOJ 2042/CQOI2016 D1T1。
一道 最小割树 的模板题,或者是一道 CDQ 分治 的好题。
题目
题意简述
一张 $n$ 个点 $m$ 条边的图,每一对点的最小割中,有多少个互不相同。
数据范围
$$1\leq n\leq 850$$
$$1\leq m\leq 8500$$
$$1\leq w\leq 10^5$$
时空限制
$$\text{Luogu}:3\text{s}/500\text{MiB}$$
$$\text{BZOJ}:20\text{s}/512\text{MiB}$$
$$\text{LibreOJ}:1\text{s}/256\text{MiB}$$
题解
思路
下面先介绍最小割树。
显然,对于某一个点来说,如果我们将它与另外一个点先求一遍最小割,那么整个图将会变成具有两个残留网络(如果原图不连通将会有更多)。
形如下面这个样子:

其中 $1$ 和 $2$ 的最小割为 $4$,有两种割法(用红、蓝标识)。而残余的边则分别属于两个联通块,把满流的边去掉,发现分成了 $(1,3,4)$、$(2,6)$ 和 $(5)$。
这里把 $2,6$ 看作和 $5$ 在一起。

为了生成最小割树,我们应该向最小割树中的 $1$ 和 $2$ 连一条边权为 $4$ 的边。
再举一个例子。

$1$ 和 $3$ 的最小割为 $9$,所以我们应该向最小割树中的 $1$ 和 $3$ 连一条边权为 $9$ 的边。
最后生成的最小割树长下面这个样子。

我们可以发现,每对点间路径的边权最小值即为它们之间的最小割。这就是最小割树的性质。
当然本题并不需要我们真的生成最小割树,然后在树上进行一番神奇的操作,只需要按层次来构造这棵树即可,保留边权,用 std::set
统计答案。
最后提醒一下,因为本题是无向边,所以反向边流量直接设成 $w_i$ 即可,防止加更多的边浪费空间。
代码
鉴于使用了网络流,本题不分析时间复杂度。但还是给出了大致的结果 $\Theta(2^{\left\lceil\log n\right\rceil}\alpha(n))$,其中 $\alpha(n)$ 为求一次网络流的时间复杂度。
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define INF 0X3F3F3F3F
#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=850+5; //点数数据范围
const int MAXM=8500+5; //边数数数据范围
inline void Read(void);
inline void Work(void);
int main(void){
Read();
Work();
return 0;
}
int n,m;
int cnt=1,head[MAXN],to[MAXM<<1],w[MAXM<<1],W[MAXM<<1],Next[MAXM<<1]; //邻接表存边
inline void Add_Edge(reg int u,reg int v,reg int len){
Next[++cnt]=head[u];
to[cnt]=v;
w[cnt]=len;
W[cnt]=len; //用 W[] 存储原图的边权,防止 Dinic 后边权出现变化
head[u]=cnt;
return;
}
inline void Add_Tube(reg int u,reg int v,reg int len){
Add_Edge(u,v,len); //正常的边
Add_Edge(v,u,len); //本题是无向边,所以反向边流量直接设为 w,防止加更多的边浪费空间。
return;
}
inline void Read(void){
n=read(),m=read();
for(reg int i=1;i<=m;++i){ //按照要求读入
static int u,v,w;
u=read(),v=read(),w=read();
Add_Tube(u,v,w); //加边
}
return;
}
int dep[MAXN];
queue<int> Q;
inline bool BFS(int s,reg int t){ //BFS 判断是否联通
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=head[ID];i;i=Next[i])
if(dep[to[i]]==-1&&w[i]>0){
dep[to[i]]=dep[ID]+1;
Q.push(to[i]);
}
}
return dep[t]!=-1; //返回汇点是否可达
}
int cur[MAXN]; //用于当前弧优化
inline int DFS(reg int ID,reg int t,reg int lim){
if(ID==t)
return lim;
reg int flow=0;
for(reg int &i=cur[ID];i;i=Next[i])
if(dep[to[i]]==dep[ID]+1&&w[i]>0){
reg int f=DFS(to[i],t,min(lim-flow,w[i]));
if(f){
flow+=f;
w[i]-=f;
w[i^1]+=f;
if(flow==lim)
break;
}
}
return flow;
}
inline int Dinic(reg int s,reg int t){
reg int res=0;
while(BFS(s,t)){
memcpy(cur,head,sizeof(head)); //复制邻接表表头
res+=DFS(s,t,INF);
}
return res;
}
bool vis[MAXN];
inline void DFS(reg int ID){
vis[ID]=true;
for(reg int i=head[ID];i;i=Next[i])
if(!vis[to[i]]&&w[i]>0)
DFS(to[i]);
return;
}
int fa[MAXN];
set<int> S;
inline void Work(void){
for(reg int i=2;i<=n;++i)
fa[i]=1; //初始化
for(reg int i=2;i<=n;++i){
reg int s=i,t=fa[i]; //求最小割的点对
memcpy(w,W,sizeof(W)); //拷贝边权
int ans=Dinic(s,t); //记录最小割
S.insert(ans); //插入 set
memset(vis,false,sizeof(vis)); //清空标记
DFS(s); //开始寻找被隔开的点对
for(reg int j=i;j<=n;++j)
if(fa[j]==t&&vis[j])
fa[j]=s;
}
printf("%d\n",(int)S.size()); //输出多少种,set 自动去重
return;
}
I was suggested this website by my cousin.
I’m not sure whether this post is written by him as nobody else know such detailed about my
difficulty. You’re amazing! Thanks!