题目链接: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}$$
题解
思路
观察发现,这是一道最小割树的模板题,程序的流程如下。
- 读入图;
- 构建最小割树;
- 回答询问:
- 方式一:
每次查询用 $\text{LCA}$ 暴力查询,单次查询的渐进时间复杂度为 $\Theta(n^2\log_2n)$。 - 方式二:
离散化边权+暴力预处理+树状数组查询。
预处理的渐进时间复杂度为 $\Theta(n^2\log_2n)$,单次查询的时间复杂度为$\Theta(\log_2m)$,其中 $m$ 表示不同边权的数量。 - 方式三:
普通的树形 DP。
单次查询的时间复杂度为 $\Theta(n^2)$ - 方式四:
离散化边权+普通树形 DP 预处理+树状数组查询。
预处理的渐进时间复杂度为 $\Theta(n^2)$,单次查询的时间复杂度为$\Theta(\log_2m)$,其中 $m$ 表示不同边权的数量(即树状数组的大小)。 - 方式五:
换根 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」不同的最小割。
Howdy! This post couldn’t be written any better! Looking at this article reminds me of my previous roommate!
He always kept preaching about this. I’ll send this article to him.
Pretty sure he’s going to have a great read. Thank you for
sharing!