UVA1389 Hard Life
最大密度子图模板题
最大密度子图
给出一张图 (G<V,E>) 我们选出一个子图 (G^{prime}<V^{prime},E^{prime}>) 使得其 (frac{|E^{prime}|}{|V^{prime}|}) 最大，这个图就是最大密度子图。
借01分数规划的逻辑，我们试着二分 (frac{|E^{prime}|}{|V^{prime}|})
假设 (frac{|E^{prime}|}{|V^{prime}|}le g)
整理得 (|E^{prime}|-g|V^{prime}|le 0)
我们设一个函数 (h(g)=max{|E^{prime}|-g|V^{prime}|})
我们简记 (|V^{prime}|=n,|E^{prime}|=m)
可以得到
于是我们需要对 (g) 二分查找，并对每一个得到的猜测值求解 (h(g))。
密度不超过 (m) 且 不小于 (frac{1}{n}) ，于是使他们作为二分的上下界。
然后是确定二分精度。
这里有一个推论：任意两个密度不同的子图 (G_1,G_2) 其密度差绝对值不小于 (frac{1}{n^2})
现在问题在于，已知 (g) 如何求解 (h(g))。
回顾题意，我们可以知道在选出的新图 (G^{prime}) 中，边 ((u,v)in E^{prime}) 的必要条件是 (u,vin V^{prime}) ，这与上文最大权闭合图的限制条件形式差不多。
那么我们把本问题中的边看做点，点权为 (1) ，本问题中的点带上点权 (-g) ，问题就转化为了最大权闭合图的模型。
我们发现在跑最大流时建边很多，并且上述问题在转化过程中将问题一般化了，复杂度会提高，所以我们思考能否利用这个图以及问题的特殊性质做这个问题。
回顾题意，我们可以发现，当我们的点集确定时，点集的诱导子图一定是最优解。
诱导子图：从原图 (G<V,E>) 中选出来一个子图 (G^{prime}<V^{prime},E^{prime}>) ,对于所有的 (u,vin V^{prime}) 都有 ((u,v)in E^{prime}) 。即把点集内部点之间的连边全部都选上。
假设我们选出了一个点集 (V^{prime}) ，现在我们要弄出它的诱导子图 (G^{prime}<V^{prime},E^{prime}>)，正向的思维便是把点集内的边一个一个找出来。
但我们使用逆向思维思考：根据补集思想，可以将所有与 (V^{prime}) 中的点关联，同时又不在 (E^{prime}) 中的点选出(下图中的红边)，然后用与 (V^{prime}) 关联的所有边的集合减去，就是我们要求的边集了。
画图继续探索：
于是我们发现，所有我们要选出的边是连接 (V^{prime}) 和 (V-V^{prime}) 的所有边。这与割的定义形式相近。我们可以考虑转化利用最小割来做。
首先我们在上面得出了要最大化 (|E^{prime}|-g|V^{prime}|) 的结论。只需要乘上 (-1) 就可以转化为最小化。
也就是我们要最小化 (g|V^{prime}|-|E^{prime}|)
根据上面的推论推一下式子：
其中 (d_v) 代表 (v) 点的度。
这个式子相当于在提示我们每个点多了个 (2g-d_v) 的点权。
我们怎么把它结合到最小割里呢？
只需要每个点向汇点连一条边，容量是 (2g-d_v)。
由于最小割只能接受容量非负的边权，所以我们给上面的边容量加上一个大数 (U) 保证非负。
原图内部的所有边不做改变，容量为 (1)。
建立源点，源点向每个点都连一条容量为 (U) 的边
解法正确性待会证明。
现在思考怎么算答案。
这时我们来看求出的最小割 (C(S,T))
定义 (V^{prime}=S-{s} , overline{V^{prime}}=V-V^{prime})
那么
接下来我们关注一下括号里面 ((d_u-sumlimits_{vin overline{V^{prime}}} C_{u,v})) 的含义
这个式子描述的是，从 (u) 出发的所有边减去到所有到集合外部的边，也就是在集合内部的边。
所以 ((d_u-sumlimits_{vin overline{V^{prime}}} C_{u,v})=sumlimits_{vin V^{prime}} C_{u,v})
所以：
于是我们发现，割和密度子图是由一一对应且单调的关系的。正确性有了保证。
我们可以整理一下答案：(g|V^{prime}|-|E^{prime}|=frac{Ucdot n-C(S,T)}{2})。
回到这个题，本题让我们求最大密度，输出方案，我们可以在求完最大密度子图后从源点出发，沿着容量大于 (0) 的边走，所有能走到的边就是 (S) 集合，将 (S) 集合中的源点删去，就得到了 (V^{prime})。
code
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e6+10,INF=1e8+10,U=1200;
int head[N],ver[M],nxt[M],tot=0;
double cc[N];
void add(int x,int y,double c,double d)
{
ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
ver[tot]=x; cc[tot]=d; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
int n,m,S,T;
int dg[N];//每个点的度数
struct node
{
int u,v;
} edge[M];//把所有的关系预先存好，方便每次二分重新建图
void build(double g)
{
memset(head,-1,sizeof head);
tot=0;
for(int i=1;i<=m;i++) add(edge[i].u,edge[i].v,1,1);
for(int i=1;i<=n;i++)
{
add(i,T,U+2*g-dg[i],0);
add(S,i,U,0);
}
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S; d[S]=0; cur[S]=head[S];
while(hh<=tt)
{
// cout<<hh<<" "<<tt<<"
";
int x=q[hh++];
for(int i=head[x];~i;i=nxt[i])
{
int y=ver[i];
if(d[y]==-1 && cc[i]>0)
{
d[y]=d[x]+1;
cur[y]=head[y];
if(y==T) return 1;
q[++tt]=y;
}
}
}
return 0;
}
double find(int u,double lim)
{
if(u==T) return lim;
double flow=0;
for(int i=cur[u];~i && flow<lim;i=nxt[i])
{
int y=ver[i];
cur[u]=i;
if(d[y]==d[u]+1 && cc[i]>0)
{
double tmp=find(y,min(cc[i],lim-flow));
if(tmp<=0) d[y]=-1;
cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
}
}
return flow;
}
double dinic(double g)
{
build(g);
double res=0,flow=0;
while(bfs()) while(flow=find(S,(double)INF)) res+=flow;
return res;
}
bool vis[N];
int ans=0;
void dfs(int x)
{
vis[x]=1;
if(x!=S) ans++;
for(int i=head[x];~i;i=nxt[i])
{
int y=ver[i];
if(!vis[y] && cc[i]>0) dfs(y);
}
return ;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
S=0,T=n+1;
memset(dg,0,sizeof dg);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
++dg[a]; ++dg[b];
edge[i]={a,b};
}
double l=1/n,r=m,eps=1.0/(double)(n*n);
while(r-l>eps)
{
double mid=(l+r)/2;
double tmp=dinic(mid);
if(U*n-tmp>0) l=mid;
else r=mid;
}
dinic(l);
memset(vis,0,sizeof vis);
ans=0;
dfs(S);
if(ans==0)
{
printf("1
1
");
continue;
}
printf("%d
",ans);
for(int i=1;i<=n;i++)
if(vis[i]) printf("%d
",i);
}
return 0;
}
关于最小割的各类常见题型会在之后的blogs中进行讲解。