UVA1389 Hard Life
orz_z
·
·
题解
求出原图的一个子图 G'=\{V',E'\}，最大化 \frac{E'}{V'}。
#### std
最大密度子图。
按照套路，考虑二分 $g \leq \frac{E'}{V'}$。
则有 $E'-mid\times V' \ge 0$。
即可看作，在原图上找一个最大权闭合子图，其所有边的权为 $1$，所有点的权为 $g$。
但是这个涉及到了边权，不太好搞。
想到由于选了一条边，就相当于选了这条边对应的两个点。
那么把边看成一个点，上面那个问题可以转化为如下模型（根据最大权闭合子图的性质）：
* $s$ 向每一条原图的边（把边看作点）连流量为 $1$ 的边。
* 每一条原图的边向其对应的原图上的两个点连流量为 $\operatorname{inf}$ 的边（其可看作选了原图的一条边，就得选其对应的两个点）。
* 每一个原图的上点向 $t$ 连流量为 $g$ 的边。
那么上述模型见图跑网络流即可。
记最大流为 $as$，那么最后求出的最大权闭合子图的权值为 $m-as$。
判断 $m-as$ 是否 $\ge 0$，然后继续二分即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
typedef double tp;
const int _ = 2e4 + 10;
const double eps = 1e-7, inf = 1e7;
int n, m, s, t, lv[_], cur[_];
int tot = 1, head[_], to[_ << 1], nxt[_ << 1];
tp w[_ << 1];
inline void add(int u, int v, tp dis)
{
to[++tot] = v;
nxt[tot] = head[u];
w[tot] = dis;
head[u] = tot;
}
inline void Add(int u, int v, tp dis)
{
add(u, v, dis);
add(v, u, 0);
}
inline bool bfs()
{
memset(lv, 0, sizeof lv);
lv[s] = 1;
memcpy(cur, head, sizeof(head));
queue<int> q;
q.push(s);
while (!q.empty())
{
int p = q.front();
q.pop();
for (int eg = head[p]; eg; eg = nxt[eg])
{
int v = to[eg];
tp vol = w[eg];
if (vol > eps && lv[v] == 0)
{
lv[v] = lv[p] + 1, q.push(v);
if(v == t) return 1;
}
}
}
return 0;
}
tp dfs(int p = s, tp flow = inf)
{
if (p == t)
return flow;
tp rmn = flow;
for (int eg = cur[p]; eg && rmn > eps; eg = nxt[eg])
{
cur[p] = eg;
int v = to[eg];
tp vol = w[eg];
if (vol > eps && lv[v] == lv[p] + 1)
{
tp c = dfs(v, min(vol, rmn));
if(c < eps) lv[v] = 0;
rmn -= c;
w[eg] -= c;
w[eg ^ 1] += c;
}
}
return flow - rmn;
}
inline tp dinic()
{
tp ans = 0;
while (bfs())
ans += dfs();
return ans;
}
int Ans, fr[_], too[_];
bool check(tp mid)
{
tot = 1;
memset(head, 0, sizeof head);
for (int i = 1; i <= m; ++i)
Add(s, i + n, 1);
for (int i = 1; i <= n; ++i)
Add(i, t, mid);
for (int i = 1; i <= m; ++i)
{
Add(i + n, fr[i], inf);
Add(i + n, too[i], inf);
}
return (tp)(m * 1.0 - dinic()) > eps;
}
bool vis[_];
void FA(int u)
{
vis[u] = 1;
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if (!vis[v] && w[i])
FA(v);
}
}
signed main()
{
int x, y;
s = 0, t = _ - 1;
while (~scanf("%d%d", &n, &m))
{
Ans = 0;
if (!m)
{
printf("%d\n%d\n\n", 1, 1);
continue;
}
for (int i = 1; i <= m; ++i)
fr[i] = read(), too[i] = read();
tp l = 0, r = m, mid;
while (r - l > eps)
{
mid = (l + r) / 2.0;
if (check(mid))
l = mid;
else
r = mid;
}
check(l);
memset(vis, 0, sizeof vis);
FA(s);
for (int i = 1; i <= n; ++i)
if (vis[i])
Ans++;
write(Ans), putchar('\n');
for (int i = 1; i <= n; ++i)
if (vis[i])
write(i), putchar('\n');
putchar('\n');
}
return 0;
}
```