题意：
给定一个图(V<=100,E<=1000) 求一个子图(V',E') 使得|E'| 与 |V'|的比值最大，要求出这个子集。
做法：
比较裸的最大密度子图。
设密度为R 要令R最大
R=max{|E'|/|'V'|} 化简得到 max{|E'|-R*|'V'|}=0
设 g(x)=max{|E'|-x*|'V'|}
由Dinkelbach定理与该函数的单调性得到：
g(x)=0 当且仅当 x=R
g(x)<0 x>R
g(x)>0 x<R
所以可以利用二分答案 二分R （下界为1/N 上界为M）
接下来就变成了如何验证x是否符合。
将式子进行转化 取g(x)<0为例
两边取负得到 min{x*|V'|-|E'|}>0
同时加上|E|得到 min{(|E|-|E'|)+x*|V'|}>E
将式子解读一下可以知道 要我们求的是 未选的边与选中的点数乘x的和是否大于E
左边的式子很熟悉
|E|中的每一条边依附于|V|中的点 同时要使选出来的点总数*x加上选出来的边数最小
这便是一个最大权闭合图的问题。
我们设立源S 汇T
从S向所有的点连权值为x的边
对于每条边e=(u,v) u,v各向e连一条无穷的边
从所有e向T连容量为1的边 求出最大流
g(x)即求得
对于求方案 由最小割的定义 我们bfs一遍 求出从S可以到达的所有点 这是S集合
另外点属于T集合。对于所有跨越S-T的边便是割边。
求点的方案等价于求出有一个端点为S的所有割边 另一个端点便是选的所有点
注意点：
本题对于精度要求很奇怪 全设作1e-7 自己电脑上跑不过 pku上能过..好吧我的g++版本太低了
1
#include <cstdio>
2#include <cstring>
3#define min(a,b) ((a)<(b)?(a):(b))
4#define oo 1e10
5#define eps 1e-7
6#define n 2005
7#define m 20005
8
9int vtx[m],ne[m],tot;
10int d[n],L[n],q[n],pre[n],x[n],y[n],S,T,now,N,M,ret;
11double f[m],Mincut;
12bool mk[n],vis[n],cut[m];
13
14inline void Ins(int u,int v,double fl)
15
{
16
vtx[++tot]=v;f[tot]=fl;ne[tot]=L[u];L[u]=tot;
17 vtx[++tot]=u;f[tot]=0;ne[tot]=L[v];L[v]=tot;
18
}
19inline void push()
20{
21 double fl=oo;
22 for (int i=T;i!=S;i=vtx[pre[i]^1])
23 fl=min(fl,f[pre[i]]);
24 Mincut+=fl;
25 for (int i=T;i!=S;i=vtx[pre[i]^1])
26
{
27 f[pre[i]]-=fl,f[pre[i]^1]+=fl;
28 if (f[pre[i]]<eps) now=vtx[pre[i]^1];
29
}
30}
31inline void dinic(int u)
32{
33 if (u==T) push();
34 else
35 {
36 for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
37 if (f[p]>eps&&d[u]+1==d[v])
38 {
39 pre[v]=p,dinic(v);
40 if (d[now]<d[u]) return;
41 now=T;
42 }
43 d[u]=-1;
44 }
45}
46inline bool extend()
47{
48 memset(d,63,sizeof(d));
49 d[q[1]=S]=0;
50 for (int h=1,t=1,u=q[h];h<=t;u=q[++h])
51 for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
52 if (f[p]>eps&&d[v]>(1<<29))
53 {
54 d[v]=d[u]+1;
55 if (v==T) return 1;
56 q[++t]=v;
57 }
58 return 0;
59}
60inline double check(double g)
61{
62 memset(L,0,sizeof(L));
63 tot=1;
64 for (int i=1;i<=N;++i)
65 Ins(S,i,g);
66 for (int i=1;i<=M;++i)
67 Ins(x[i],N+i,oo),Ins(y[i],N+i,oo),Ins(N+i,T,1);
68 for (Mincut=0;extend();dinic(S));
69 return Mincut<M;
70}
71inline void findcut()
72{
73 vis[q[1]=S]=1;
74 for (int h=1,t=1,u=q[h];h<=t;u=q[++h])
75 for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
76 if (f[p]>1e-4&&!vis[v]) vis[q[++t]=v]=1;
77 for (int u=1;u<=T;++u)
78 for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
79 if (!(p&1)&&(vis[u]^vis[v])) cut[p]=1;
80}
81int main()
82{
83 scanf("%d%d",&N,&M);
84 if (!M) return printf("1\n1\n"),0;
85 for (int i=1;i<=M;++i)
86 scanf("%d%d",&x[i],&y[i]);
87 S=N+M+1,T=S+1;
88 int Time=24;
89 double l=1/N,r=M,mid;
90 for (mid=(l+r)/2;Time--;mid=(l+r)/2)
91 if (check(mid)) l=mid;
92 else r=mid;
93 check(l),findcut();
94 for (int p=L[S],v=vtx[p];p;v=vtx[p=ne[p]])
95 if (cut[p]) ++ret,mk[v]=1;
96 printf("%d\n",ret);
97 for (int i=1;i<=N;++i)
98 if (mk[i]) printf("%d\n",i);
99 return 0;
100}
101