UVA1389 Hard Life
大意
求最大密度子图。
思路
对于这个题，我们要求 \(\dfrac{|E|}{|V|}\) 的值尽可能的大，我们将其变形一下， \(\dfrac{|E|}{|V|} \ge g\)，那么我们设 \(h(g) = |E| - g|V|\)，那么我们如果 \(h(g) \ge 0\) 就说明我们可以有更大的密度 \(g\)。
对于一条边来说，选它的贡献是 \(1\)，对于一个点来说，选其的代价是 \(g\)。由于选边必选点，我们将其转化为最大权闭合图来处理。
- 源点 \(S\) \(\rightarrow\) 边点 \(e_i\)：容量为 \(1\)（表示这条边的潜在收益）。
- 点 \(v_j\) \(\rightarrow\) 汇点 \(T\)：容量为 \(g\)（表示选这个点的成本）。
- 边点 \(e_i\) \(\rightarrow\) 端点 \(u, v\)：容量为 \(\infty\)（表示这种依赖关系不可割断）。
所以我们的 \(h(g) = 边权数 - 最小割\)。
我们尝试二分答案，只需要找到使得 \(h(g) = 0\) 的最小的 \(g\) 即可。
那么二分答案的精度呢？
一般来说下届直接用 \(0\)，上界就 \(m\)，毕竟只有 \(m\) 条边，那么对于两个子图的密度精度：
\[\dfrac{m_1}{n_1} - \dfrac{m_2}{n_2} = \dfrac{m_1n_2 - m_2n_1}{n_1n_2} \ge \dfrac{1}{n_1n_2} \ge \dfrac{1}{n ^ 2}
\]
那么显然的事情是，我们把 \(\dfrac{1}{n ^ 2}\) 定为精度即可，也可以再乘 \(0.1\)，看习惯吧。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 1200;
const int MAXM = 20000;
const double eps = 1e-9;struct Edge {int v, nxt;double c;
} e[MAXM];int h[MAXN], cur[MAXN], d[MAXN], cnt;
int n, m, S, T;
int U[MAXM], V[MAXM];void add(int u, int v, double c){e[cnt] = {v, h[u], c}; h[u] = cnt++;e[cnt] = {u, h[v], 0}; h[v] = cnt++;
}bool bfs(){queue<int> q;memset(d, -1, sizeof(d));d[S] = 0;q.push(S);while(!q.empty()){int u = q.front();q.pop();for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c > eps && d[v] == -1){d[v] = d[u] + 1;q.push(v);}}}return (d[T] == -1) ? false : true;
}double dfs(int u, double flow){if(u == T || flow < eps){return flow;}double res = 0;for(int &i = cur[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c > eps && d[v] == d[u] + 1){double tmp = dfs(v, min(flow, e[i].c));if(tmp > eps){e[i].c -= tmp;e[i ^ 1].c += tmp;res += tmp;flow -= tmp;if(flow < eps) break;}}}if(res < eps){d[u] = -1;}return res;
}double Dinic(){double res = 0;while(bfs()){memcpy(cur, h, sizeof(h));res += dfs(S, 1e9);}return res;
}bool check(double g){cnt = 0;memset(h, -1, sizeof(h));S = 0, T = n + m + 1;for(int i = 1;i <= m;i ++){add(S, n + i, 1.0);add(n + i, U[i], 1e9);add(n + i, V[i], 1e9);}for(int i = 1;i <= n;i ++){add(i, T, g);}return (double)m - Dinic() > eps;
}int main(){while(cin >> n >> m){if(m == 0){cout << 1 << endl << 1 << endl;continue;}for(int i = 1;i <= m;i ++) cin >> U[i] >> V[i];double L = 0, R = m;for(int i = 0;i < 60;i ++){double mid = (L + R) / 2.0;if(check(mid)) L = mid;else R = mid;}check(L);vector<int> ans;for(int i = 1;i <= n;i ++){if(d[i] != -1) ans.push_back(i);}cout << ans.size() << endl;for(int i = 0;i < ans.size();i ++) cout << ans[i] << endl;}return 0;
}