最小割树 简单题。
题目链接:CodeForces 343E。
题目
题目描述
一张 $n$ 个点 $m$ 条边的带权无向图。构造一个排列,求
$$\max\{\sum^n _ {i=2}\operatorname{mincut}(a _ {i-1},a _ i)\}$$
其中 $\operatorname{mincut}(s,t)$ 表示 $s$ 到 $t$ 的最小割。
求答案,并输出构造的排列。
数据范围
变量 | 数据范围 |
---|---|
$n$ | $2\leq n\leq 200$ |
$m$ | $1\leq n\leq 1000$ |
边权 | $\leq 100$ |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
CodeForces 343E | $2\text{s}$ | $256\text{MiB}$ |
题解
思路
先列出结论,下面再证明。
结论:答案是最小割树上的边权和。构造时将最小割树每次沿边权最小的边割开,递归求解,最后合并。
证明
证明构造方法的正确性。
不妨设当前树的最小边权为 $d$,这条边会将最小割树分为两个连通块 $P,Q$。
设 $u _ 1,v _ 1\in P,u _ 2,v _ 2\in Q$,那么我们来讨论顺序问题。
- 顺序为 $u _ 1,v _ 1,u _ 2,v _ 2$,即先在两个连通块内,最后合并。
由最小割树的性质:两点间的最小割为他们对应节点在最小割树上的路径的边权最小值。
我们有
$$\operatorname{mincut}(v _ 1,u _ 2)=d$$
此外,由于 $d$ 为最小边权,所以
$$\begin{cases}\operatorname{mincut}(u _ 1,v _ 1)\geq d\\\operatorname{mincut}(u _ 2,v _ 2)\geq d\end{cases}$$
把上面三式相加,我们可以得到
$$\operatorname{mincut}(u _ 1,v _ 1)+\operatorname{mincut}(v _ 1,u _ 2)+\operatorname{mincut}(u _ 2,v _ 2)\geq 3d$$
即对答案的贡献 $\omega$ 满足
$$\omega\geq 3d$$ - 顺序为 $u _ 1,u _ 2,v _ 1,v _ 2$,即在连通块之间反复横跳。
由最小割树的性质:两点间的最小割为他们对应节点在最小割树上的路径的边权最小值。
我们有
$$\begin{cases}\operatorname{mincut}(v _ 1,u _ 2)=d\\\operatorname{mincut}(u _ 1,v _ 1)=d\\\operatorname{mincut}(u _ 2,v _ 2)=d\end{cases}$$
把上面三式相加,我们可以得到
$$\operatorname{mincut}(u _ 1,v _ 1)+\operatorname{mincut}(v _ 1,u _ 2)+\operatorname{mincut}(u _ 2,v _ 2)=3d$$
即对答案的贡献 $\omega$ 满足
$$\omega=3d$$
这就证明了构造方法的正确性。
通过构造方法我们不难发现,每条边的边权只会计算一次,所以我们直接求出最小割树的边权和就是答案了。
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #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 char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=200+5; const int MAXM=1000+5; int n,m; namespace Graph{ //在图上跑网络流 int cnt=1,head[MAXN],to[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; 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); //无向图,所以反向边边权一样 return; } int dep[MAXN]; queue<int> Q; inline bool BFS(int s,reg int t){ 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; } } 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 res[MAXN],tot; namespace Tree{ //最小割树 int cnt=1,head[MAXN],to[MAXN<<1],w[MAXN<<1],Next[MAXN<<1]; 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; return; } 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 d; //d 表示当前发现的最小边权 int id,x,y; //id 表示边的编号,x,y 表示边的端点 bool vis[MAXN<<1]; //vis[i] 表示 i 是否被删除 inline bool DFS(reg int ID,reg int father){ reg bool flag=false; //判断是否只剩下一个点 for(reg int i=head[ID];i;i=Next[i]) if(to[i]!=father&&!vis[i]){ if(w[i]<d){ //更新 id=i; x=ID; y=to[i]; d=w[i]; } DFS(to[i],ID); flag=true; } return flag; } inline void Solve(reg int ID){ d=INF; //初始化 if(!DFS(ID,0)){ //只有一个点 res[++tot]=ID; //直接加入方案中 return; } vis[id]=vis[id^1]=true; //删边 reg int p=x,q=y; //这里要用变量保存,防止递归后变化 Solve(p),Solve(q); return; } } int W[MAXM<<1]; int main(void){ n=read(),m=read(); for(reg int i=1;i<=m;++i){ static int u,v,w; u=read(),v=read(),w=read(); Graph::Add_Tube(u,v,w); } static int fa[MAXN]; for(reg int i=2;i<=n;++i) fa[i]=1; for(reg int i=1;i<=Graph::cnt;++i) W[i]=Graph::w[i]; reg int ans=0; for(reg int i=2;i<=n;++i){ for(reg int j=1;j<=Graph::cnt;++j) Graph::w[j]=W[j]; reg int s=fa[i],t=i; reg int res=Graph::Dinic(s,t); ans+=res; Tree::Add_Tube(s,t,res); memset(Graph::vis,false,sizeof(Graph::vis)); Graph::DFS(s); for(reg int j=i+1;j<=n;++j) if(!Graph::vis[j]&&fa[j]==s) fa[j]=t; } printf("%d\n",ans); Tree::Solve(1); for(reg int i=1;i<=tot;++i) printf("%d%c",res[i],i==n?'\n':' '); //输出方案 return 0; }
近期评论