[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}$$
题解
思路
观察发现,这是一道最小割树的模板题,程序的流程如下。
- 读入图;
- 构建最小割树;
- 回答询问:
- 方式一:
每次查询用 $\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」不同的最小割。
近期评论