最小割树小记
最小割树小记
定义
首先对于一个边带权的无向图(G) ，定义无序点对((u,v)) 的割为一个边集满足在(G) 上删去这些边后((u,v)) 之间不连通，而最小割定义为满足这个边集中边的边权和的最小时的边集。
在一个(n) 个点的图(G) 上，本质不同的最小割只有至多(n-1) 种，因此一定可以形成一棵树。
图(G) 的最小割树定义为对于树上任一边((u,v)) ，满足((u,v)) 的权值为原图上((u,v)) 的最小割权值且割去这条边后产生的两个集合恰好和原图((u,v)) 的最小割将原图分为的两个集合相同。
构造
首先随意地选择两个点((u,v)) ，求出其最小割(C) ，在(u,v) 之间连接边权为(C) 的无向边。
而后找出(u,v) 分属的两个点集，对于这两个点集递归地操作即可，直至只剩下一个点。
void build(int*p,int num)
{
if(num<=1)return;
int q1[N],q2[N],p1=0,p2=0;
int val=dinic(p[1],p[2]);
add(p[1],p[2],val);
for(int i=1;i<=num;++i)
{
if(dis[p[i]]!=-1) q1[++p1]=p[i];
else q2[++p2]=p[i];
}
for(int i=1;i<=p1;++i)p[i]=q1[i];
for(int i=p1+1;i<=p1+p2;++i)p[i]=q2[i-p1];
build(p,p1),build(p+p1,p2);
}
性质
原图上((u,v)) 之间的最小割权值就是在最小割树((u,v)) 的简单路径上边权的最小值。
确实就这个性质。
题目的话都是比较板的题目，没有什么变化，因此也不太可能考到。