题目大意：给一个无向图，求此图的最大密度子图。
输入：n，m，表示有n个点（1 -- n编号），接m行，每行u v，表示u到v有一条无向边。
网上各种传说这是一种分数规划的东西，然后我也不了解，搜了很多资料，也没有人给了很好的解释。貌似胡伯涛的一篇文章里提到了这样的算法，但是里面的证明各种看不懂。好吧，看不懂我就只有另寻他法了。
乍一看，毫无策略。方案核心是要找答案，那就直接枚举答案测试好了。题目要找最大密度**，也即（选中的边数/与这些边边有关的点数）。那就二分枚举这个最大密度吧！！！
假设答案是k，任意所选边集为E，与E对应的点集V，即有max{|E|/|V|} == k，也就是说|E|/|V| <= k 也等价于 |E|-|V|*k <= 0。
现在测试x是不是答案，若x>k，则不管怎么选都会有 |E|-|V|*k < 0； 若 x < k 则 能找到E使得 |E|-|V|*k > 0。
现在我们枚举要选中的边，假设选中边uv，那么必选点u、v。若H(x)=E(x)-V(x)*k，选中边uv的结果是H(x)=H(x)+1,选中点u、v的结果是H(x)=H(x)-1-1。
由于所有边都最终指向两个点，而点是截止的，这不就是最大权闭合子图吗？？？！！！
构图是不是就很水了: C(S,UV)=1, C(UV,V)=1, C(UV,U)=1, C(U,T)=x。然后最大流求出,H(x)=m-maxF();
注意一个小小的坑，用最大流求最大权闭合子图时，H(x) < 0是体现不出来的。所以祝你好运了。贴个代码……
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 using namespace std; 6 #define maxn 150 7 const int maxe = 1001000; 8 const double maxf = 1e10; 9 #define zero 1e-8 10 struct edge{ 11 int u,v; double c; 12 edge(int e1=0,int e2=0,double e3=0){ u=e1,v=e2; c=e3; } 13 }e[maxe]; 14 int ec; 15 int head[maxn]; 16 int next[maxe]; 17 void addedge(int u,int v,double c){ 18 e[ec]=edge(u,v,c); 19 next[ec]=head[u]; head[u]=ec++; 20 e[ec]=edge(v,u,0); 21 next[ec]=head[v]; head[v]=ec++; 22 } 23 //***********************************// 24 int source,sink,maxdep; 25 int dep[maxn],gap[maxn]; 26 void setGD(){ 27 for(int i=0;i<=maxdep;i++) dep[i] = maxdep; dep[sink] = 0; 28 int u,v; 29 queue<int> que; 30 que.push(sink); 31 while(!que.empty()){ 32 u = que.front(); que.pop(); 33 for(int i=head[u];i!=-1;i=next[i]){ 34 v = e[i].v; //if(v > maxdep) continue; 35 if(dep[v] < maxdep) continue; //'被访问过' 36 dep[v] = dep[u]+1; 37 que.push(v); 38 } 39 } 40 memset(gap,0,sizeof(gap)); 41 for(int i=0;i<=maxdep;i++) gap[dep[i]]++; 42 } 43 double maxF(){ 44 setGD(); 45 int u=source,i; 46 int cur[maxn],trace[maxn],top=0; 47 for(int i=0;i<=maxdep;i++) cur[i] = head[i]; 48 double flow=0; 49 while(dep[source] <= maxdep){ 50 if(u == sink){ 51 double tf = maxf; int ins; 52 for(i=0;i<top;i++) //找瓶颈边 53 if(tf - e[trace[i]].c > 0) 54 tf = e[trace[i]].c, ins = i; 55 for(i=0;i<top;i++){ 56 e[trace[i]].c -= tf; 57 e[trace[i]^1].c += tf; 58 } 59 flow += tf; 60 u = e[trace[ins]].u, top = ins; 61 } 62 if(u != sink && gap[dep[u]-1]==0) break; 63 for(i=cur[u];i!=-1;i=next[i]) 64 if(e[i].c > zero && dep[u] == dep[e[i].v] + 1) 65 break; 66 if(i != -1) { 67 trace[top++] = i; 68 cur[u] = i; 69 u = e[i].v; 70 } 71 else { 72 int mindep = maxdep; 73 for(i=head[u];i!=-1;i=next[i]){ 74 if(e[i].c > zero && dep[e[i].v] < mindep) 75 mindep = dep[e[i].v], cur[u] = i; 76 } 77 gap[dep[u]]--; 78 dep[u] = mindep + 1; 79 gap[dep[u]]++; 80 if(u != source) 81 u = e[trace[--top]].u; 82 } 83 } 84 return flow; 85 } 86 //**********************************// 87 void initial(){ 88 ec = 0; 89 memset(head,-1,sizeof(head)); 90 //initial source ,sink and maxdep; 91 } 92 int uu[1010],vv[1010],degree[maxn]; 93 double most; 94 void mapping(int n,int m,double k){ 95 initial(); 96 for(int i=1;i<=n;i++) { 97 addedge(source,i,most); 98 addedge(i,sink,most+2*k-degree[i]); 99 } 100 for(int i=1;i<=m;i++) { 101 addedge(vv[i],uu[i],1); 102 addedge(uu[i],vv[i],1); 103 } 104 } 105 bool visited[maxn]; 106 void search(int u){ 107 visited[u]=1; 108 for(int i=head[u];i>=0;i=next[i]) 109 if(e[i].c > zero && !visited[e[i].v]) 110 search(e[i].v); 111 } 112 int main() 113 { 114 int n,m; 115 while(scanf("%d%d",&n,&m) != EOF){ 116 memset(degree,0,sizeof(degree)); 117 for(int i=1;i<=m;i++) 118 scanf("%d%d",&uu[i],&vv[i]), degree[uu[i]]++, degree[vv[i]]++; 119 if(m == 0){ 120 printf("1 1 "); 121 continue; 122 } 123 source=0; 124 sink=n+1; 125 maxdep=sink+1; 126 most=m+n; 127 double left=0,right=m+n,eps=1e-5,mid; 128 while(right-left > eps){ 129 mid = (left+right)*0.5; 130 mapping(n,m,mid); 131 double hx=(n*most-maxF())*0.5; 132 if(hx>1e-5) left=mid; 133 else right=mid; 134 } 135 mid = left; //mid重新赋值，否则有可能WA掉 136 mapping(n,m,mid); 137 double flow=maxF(); 138 //printf("mid = %.10f ",mid); 139 memset(visited,0,sizeof(visited)); 140 search(source); 141 int ret=0; 142 for(int i=1;i<=n;i++) 143 if(visited[i]) ret++; 144 printf("%d ",ret); 145 for(int i=1;i<=n;i++) 146 if(visited[i]) 147 printf("%d ",i); 148 } 149 return 0; 150 }