题意
给出n个人，和m对有冲突的人。要裁掉一些人，使得冲突率最高，冲突率为存在的冲突数/人数。
思路
题意可以转化为，求出一些边，使得|E|/|V|最大，这种分数规划叫做最大密度子图。
对于每个边，依赖于点，可以转化为最大权闭合子图来求解。
最大密度子图: max(|E|/|V|)
分数规划
k = |E|/|V|
h(g) = E - V * g
边依赖于点
转化为最大权闭合图
二分点权即g
h(g)为递减函数
当h(g) < 0,不合法,要减小g
当h(g) > 0,说明存在更优解,要增大g
当h(g) = 0,得到最优解
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int N = 1111;
const double eps = 1e-8;
const double inf = 1000000000;
const int INF = 0x3f3f3f3f;
struct Edge {
int u, v, nxt; double cap;
} edge[N*8];
int head[N], tot, dis[N], vis[N], gap[N], pre[N], cur[N], S, T, n, m;
pii p[N];
vector<int> ans;
/*
最大密度子图: max(|E|/|V|)
分数规划
k = |E|/|V|
h(g) = E - V * g
边依赖于点
转化为最大权闭合图
二分点权即g
h(g)为递减函数
当h(g) < 0,不合法,要减小g
当h(g) > 0,说明存在更优解,要增大g
当h(g) = 0,得到最优解
*/
void Add(int u, int v, double cap) {
edge[tot] = (Edge) { u, v, head[u], cap }; head[u] = tot++;
edge[tot] = (Edge) { v, u, head[v], 0 }; head[v] = tot++;
}
void BFS(int T) {
queue<int> que;
memset(dis, INF, sizeof(dis));
memset(gap, 0, sizeof(gap));
dis[T] = 0; gap[0]++; que.push(T);
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(dis[v] == INF) {
dis[v] = dis[u] + 1;
gap[dis[v]]++;
que.push(v);
}
}
}
}
double ISAP(int S, int T, int n) {
BFS(T);
memcpy(cur, head, sizeof(cur));
int u = pre[S] = S, index, i;
double flow, ans = 0;
while(dis[S] < n) {
if(u == T) {
flow = inf; index = u;
for(u = S; u != T; u = edge[cur[u]].v)
if(flow > edge[cur[u]].cap) flow = edge[cur[u]].cap, index = u;
for(u = S; u != T; u = edge[cur[u]].v)
edge[cur[u]].cap -= flow, edge[cur[u]^1].cap += flow;
ans += flow; u = index;
}
for(i = cur[u]; ~i; i = edge[i].nxt)
if(dis[edge[i].v] == dis[u] - 1 && edge[i].cap > 0) break;
if(~i) {
cur[u] = i; pre[edge[i].v] = u; u = edge[i].v;
} else {
int md = n + 1;
if(--gap[dis[u]] == 0) break;
for(i = head[u]; ~i; i = edge[i].nxt)
if(dis[edge[i].v] < md && edge[i].cap > 0)
md = dis[edge[i].v], cur[u] = i;
gap[dis[u] = md + 1]++;
u = pre[u];
}
}
return ans;
}
void Build(double g) {
memset(head, -1, sizeof(head)); tot = 0;
for(int i = 1; i <= n; i++) Add(i, T, g);
for(int i = 1; i <= m; i++) {
Add(S, i + n, 1);
Add(i + n, p[i].first, inf);
Add(i + n, p[i].second, inf);
}
}
void DFS(int u) {
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(edge[i].cap > 0 && !vis[v]) {
vis[v] = 1; DFS(v);
if(1 <= v && v <= n) ans.push_back(v);
}
}
}
int main() {
while(~scanf("%d%d", &n, &m)) {
for(int i = 1; i <= m; i++) scanf("%d%d", &p[i].first, &p[i].second);
if(m == 0) { puts("1
1"); continue; }
S = 0, T = n + m + 1;
double l = 0.0, r = m;
while(r - l >= 1.0 / n / n) { // 不同解之间误差的精度不超过1/(n*n)
double mid = (l + r) / 2;
Build(mid);
double now = 1.0 * m - ISAP(S, T, T + 1); // 转化为最大权闭合图
if(now < eps) r = mid; // h(g)为单调递减函数,如果h(g)<0,那么g要减小,当h(g)为0得到最优解
else l = mid;
}
Build(l);
ISAP(S, T, T + 1);
ans.clear();
vis[S] = 1;
memset(vis, 0, sizeof(vis));
DFS(S);
sort(ans.begin(), ans.end());
printf("%d
", ans.size());
for(int i = 0; i < ans.size(); i++)
printf("%d
", ans[i]);
}
return 0;
}
/*
5 6
1 5
5 4
4 2
2 5
1 2
3 1
4 0
---
4
1
2
4
5
1
1
*/