胡伯涛的《最小割模想在信息学竞赛中的应用》中讲到了最大密集子图。而这题是一个很裸的最大密集子图。。。
定义：无向图G中存在一个子图G‘，使得G‘中|E|/|V|最大。
即：
分数规划，设一个猜想值g，构造一个新函数
h(g) = max{sigma(Xe) - sigma(g*Xv)} (Xe属于边集，Xv属于点集)
有:
已知：
乘以-1得：
乘以2化简得：
其中C[V', !V']表示的图的最小割。
所以可以根据如下方式建图：
dv最大为m，所以U = m即可， 1/n <= g <= m/1;
同时有一个结论：任意两个密集子图，他们的密度查不小与1/n2
另外（摘自Discuss）：
这个题目是利用分数规划进行二分求解的，
但这个问题的分数规划和我之前的见过的很多分数规划是不同的，之前的分数规划表
达式很多都是在给定区间内只有一个零点的单调函数。但这个题目不同，因为
MiniCut=U*n-Maxmize{f(n)}，而MiniCut& lt;=U*n是恒成立的，所以
Maxmize{f(n)}>=0恒成立，及Maxmize{f(n)}函数会先递减，然后一直为0，我们的目
标是找出第一个零点。所以二分应该这么写：
while(r-l >= 1.0/n/n)
{
mid = (l+r) / 2;
BuildGraph();
Cut = Max_flow(s, t);
tmp = (U*n-Cut) / 2;
if(tmp > eps) l = mid;
else r = mid;
}
而不能当找出一个零点时直接break。
ps：论文上的证明太多，我这里就简单记一下结论。。。建议读读胡伯涛的论文。不然有的地方跨度太大了。。。
然后渣代码：
View Code
//#pragma comment(linker,"/STACK:327680000,327680000") #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <set> #include <functional> #include <numeric> #include <sstream> #include <stack> #include <map> #include <queue> #define CL(arr, val) memset(arr, val, sizeof(arr)) #define REP(i, n) for((i) = 0; (i) < (n); ++(i)) #define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i)) #define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i)) #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) (x) < (y) ? (x) : (y) #define Max(x, y) (x) < (y) ? (y) : (x) #define E(x) (1 << (x)) #define iabs(x) (x) < 0 ? -(x) : (x) #define OUT(x) printf("%I64d\n", x) #define lowbit(x) (x)&(-x) #define Read() freopen("data.in", "r", stdin) #define Write() freopen("data.out", "w", stdout); const double eps = 1e-8; typedef long long LL; //const int inf = ~0u>>2; using namespace std; const int N = 1024; const double inf = ~0u; struct node { int to; double val; int next; } g[N*N]; int head[N], t; int layer[N]; int q[N*1000]; int S, T; void init() { CL(head, -1); t = 0; } void add(int u, int v, double c) { g[t].to = v; g[t].val = c; g[t].next = head[u]; head[u] = t++; g[t].to = u; g[t].val = 0; g[t].next = head[v]; head[v] = t++; } bool Layer() { //分层 CL(layer, -1); int f = 0, r = 0, i, u, v; q[r++] = S; layer[S] = 1; while(f < r) { u = q[f++]; for(i = head[u]; i != -1; i = g[i].next) { v = g[i].to; if(g[i].val > eps && layer[v] == -1) { layer[v] = layer[u] + 1; if(v == T) return true; q[r++] = v; } } } return false; } double find() { //找一次增广路 int u, i, e, pos, top; double sum = 0, flow; top = 1; while(top) { u = (top == 1 ? S : g[q[top-1]].to); if(u == T) { flow = inf; FOR(i, 1, top - 1) { e = q[i]; if(g[e].val < flow) { flow = g[e].val; pos = i; } } FOR(i, 1, top - 1) { e = q[i]; g[e].val -= flow; g[e^1].val += flow; } sum += flow; top = pos; } else { for(i = head[u]; i != -1; i = g[i].next) { if(g[i].val > eps && layer[g[i].to] == layer[u] + 1) break; } if(i != -1) q[top++] = i; else { --top; layer[u] = -1; } } } return sum; } double Dinic() { double res = 0; while(Layer()) res += find(); return res; } struct num { int x, y; }p[N]; double d[N]; bool vis[N]; int n, m; double U; void build(double g) { int i; init(); for(i = 1; i <= n; ++i) { add(S, i, U); } for(i = 1; i <= n; ++i) { add(i, T, U + 2*g - d[i]); } for(i = 0; i < m; ++i) { add(p[i].x, p[i].y, 1.0); add(p[i].y, p[i].x, 1.0); } } void dfs(int t) { vis[t] = true; for(int i = head[t]; i != -1; i = g[i].next) { if(g[i].val > eps && !vis[g[i].to]) dfs(g[i].to); } } int main() { //Read(); int i, ans; double c, tmp; while(~scanf("%d%d", &n, &m)) { if(m == 0) { puts("1\n1\n"); continue; } CL(d, 0); for(i = 0; i < m; ++i) { scanf("%d%d", &p[i].x, &p[i].y); d[p[i].x]++; d[p[i].y]++; } S = 0, T = n + 1, U = m; double l, r, mid; l = 1./(n*1.); r = m; while(r - l >= 1./(n*n*1.)) { mid = (l + r)/2.; build(mid); c = Dinic(); tmp = double(U*n - c)/2.; if(tmp > eps) l = mid; else r = mid; } build(l); Dinic(); CL(vis, false); dfs(S); for(ans = 0, i = 1; i <= n; ++i) { if(vis[i]) ans++; } printf("%d\n", ans); for(i = 1; i <= n; ++i) { if(vis[i]) printf("%d\n", i); } } return 0; }