題意：
給定一個圖(V<=100,E<=1000) 求一個子圖(V',E') 使得|E'| 與 |V'|的比值最大，要求出這個子集。
做法：
比較裸的最大密度子圖。
設(shè)密度為R 要令R最大
R=max{|E'|/|'V'|} 化簡得到 max{|E'|-R*|'V'|}=0
設(shè) g(x)=max{|E'|-x*|'V'|}
由Dinkelbach定理與該函數(shù)的單調(diào)性得到：
g(x)=0 當且僅當 x=R
g(x)<0 x>R
g(x)>0 x<R
所以可以利用二分答案 二分R （下界為1/N 上界為M）
接下來就變成了如何驗證x是否符合。
將式子進行轉(zhuǎn)化 取g(x)<0為例
兩邊取負得到 min{x*|V'|-|E'|}>0
同時加上|E|得到 min{(|E|-|E'|)+x*|V'|}>E
將式子解讀一下可以知道 要我們求的是 未選的邊與選中的點數(shù)乘x的和是否大于E
左邊的式子很熟悉
|E|中的每一條邊依附于|V|中的點 同時要使選出來的點總數(shù)*x加上選出來的邊數(shù)最小
這便是一個最大權(quán)閉合圖的問題。
我們設(shè)立源S 匯T
從S向所有的點連權(quán)值為x的邊
對于每條邊e=(u,v) u,v各向e連一條無窮的邊
從所有e向T連容量為1的邊 求出最大流
g(x)即求得
對于求方案 由最小割的定義 我們bfs一遍 求出從S可以到達的所有點 這是S集合
另外點屬于T集合。對于所有跨越S-T的邊便是割邊。
求點的方案等價于求出有一個端點為S的所有割邊 另一個端點便是選的所有點
注意點：
本題對于精度要求很奇怪 全設(shè)作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