poj3155（网络流最大密度子图模型）

/* translation: 公司里面有若干职员，每个职员都有一个或者若干个和自己不和的人，如果让两个不和的人在一起工作，则效率必然下降。 定义一个hard因子。hard:=互相不和的职工对数 / 总人数。现在求从公司里面选出一些人出来，使得hard因子最大。 solution: 网络流解决最大密度子图。 paper题，参考论文“最小割模型在信息学竞赛中的应用”一文。 note: * 怒怼两天，主要思路参考论文，不难写出代码，但是精度特别难调。最后改来改去，也不知道怎么就过了，淦！！ date: 2017.2.2 */ #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <utility> #include <algorithm> #include <vector> using namespace std; const int maxn = 116; const double INF = 0x3fffffff; const double eps = 1e-8; struct Edge { int to, rev; double cap; Edge(int to_, int rev_, double cap_):to(to_),rev(rev_),cap(cap_){} }; vector<Edge> G[maxn]; vector<int> ans; int level[maxn], n, m, s, t; int iter[maxn], sum; struct node { int first, second; } p[1024]; bool vis[maxn]; int d[maxn]; void add_edge(int from, int to, double cap) { //printf("add edge from %d to %d, cap = %lf\n", from, to, cap); G[from].push_back(Edge(to, G[to].size(), cap)); G[to].push_back(Edge(from, G[from].size() - 1, 0.0)); } void bfs(int s) { memset(level, -1, sizeof(level)); queue<int> q; level[s] = 0; q.push(s); while(!q.empty()) { int v = q.front(); q.pop(); for(int i = 0; i < G[v].size(); i++) { Edge& e = G[v][i]; if(e.cap > eps && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } } double min(double a, double b) { return a > b ? b : a; } double dfs(int v, int t, double f) { //printf("@%d %d\n", v, t); if(v == t) return f; for(int& i = iter[v]; i < G[v].size(); i++) { Edge& e = G[v][i]; if(e.cap > 0 && level[e.to] > level[v]) { double dt = dfs(e.to, t, min(f, e.cap)); if(dt > eps) { e.cap -= dt; G[e.to][e.rev].cap += dt; return dt; } } } return 0; } double max_flow(int s, int t) { double flow = 0; for(;;) { bfs(s); if(level[t] < 0) return flow; memset(iter, 0, sizeof(iter)); double f; while((f = dfs(s, t, INF)) > eps) flow += f; } } bool check(double k) { for(int i = 0; i < maxn; i++) G[i].clear(); for(int i = 1; i <= n; i++) { add_edge(s, i, m); add_edge(i, t, m + 2 * k - d[i]); } for(int i = 0; i < m; i++) { int u = p[i].first, v = p[i].second; add_edge(u, v, 1.0); add_edge(v, u, 1.0); } double tmp = (n * m - max_flow(s, t)) / 2; if(tmp > eps) return true; else return false; } void dfs1(int v) { vis[v] = true; for(int i = 0; i < G[v].size(); i++) { Edge e = G[v][i]; if(e.cap > eps && !vis[e.to]) dfs1(e.to); } } int main() { //freopen("in.txt", "r", stdin); while(~scanf("%d%d", &n, &m)) { memset(d, 0, sizeof(d)); for(int i = 0; i < m; i++) { scanf("%d%d", &p[i].first, &p[i].second); d[p[i].first]++; d[p[i].second]++; } if(m == 0) { printf("1\n1\n"); } else { s = 0; t = n + 1; double lb = 0.0, ub = m * 1.0, mid; double precision = (double)(1.0 / n / n); while(ub - lb >= precision) { mid = (lb + ub) / 2; //printf("# %lf %lf\n", lb, ub); if(check(mid)) lb = mid; else ub = mid; } check(lb); memset(vis, 0, sizeof(vis)); dfs1(0); sum = 0; for(int i = 1; i <= n; i++) if(vis[i]) sum++; printf("%d\n", sum); for(int i = 1; i <= n; i++) if(vis[i]) printf("%d\n", i); } } return 0; }