看到比值，就能想到01分数规划。
令
\(x = \frac{\sum{m_i}}{\sum{n_i}}\)，变一下：
\(\sum{m_i - n_i * x} = 0\)。但是建图我就是看题解的了。
我们把每一条边也看成一个点，从源点想这个点连一条边权为
\(1\)的边，然后对于这条边连接着的节点
\(u, v\)，分别向
\(u, v\)连一条容量为
\(INF\)的边。然后从原图的每一个点向汇点连一条容量为
\(x\)的边。
需要注意的是二分的精度应该是
\(\frac{1}{n ^ 2}\)，如果是自己设的
\(eps\)的话在某谷上会
\(WA\)。有一个大佬的博客讲了是怎么来的，然而我没怎么看懂……
#include #include #include #include #include #include #include #include #include #include using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define rg registertypedef long long ll;typedef double db;const db INF = 1e10;const db eps = 1e-8;const int maxn = 105;const int maxm = 1e3 + 5;const int maxe = 6505;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}int n, m, s, t;struct Node{ int x, y;}a[maxm];struct Edge{ int nxt, from, to; db cap, flow;}e[maxe];int head[maxn + maxm], ecnt = -1;void addEdge(int x, int y, db w){ e[++ecnt] = (Edge){head[x], x, y, w, 0}; head[x] = ecnt; e[++ecnt] = (Edge){head[y], y, x, 0, 0}; head[y] = ecnt;}int dis[maxn + maxm];bool bfs(){ Mem(dis, 0); dis[s] = 1; queue q; q.push(s); while(!q.empty()) { int now = q.front(); q.pop(); for(int i = head[now], v; i != -1; i = e[i].nxt) { v = e[i].to; if(!dis[v] && e[i].cap > e[i].flow + eps) { dis[v] = dis[now] + 1; q.push(v); } } } return dis[t];}int cur[maxn + maxm];db dfs(int now, db res){ if(now == t || res < eps) return res; db flow = 0, f; for(int& i = cur[now], v; i != -1; i = e[i].nxt) { v = e[i].to; if(dis[v] == dis[now] + 1 && (f = dfs(v, min(res, e[i].cap - e[i].flow))) > eps) { e[i].flow += f; e[i ^ 1].flow -= f; flow += f; res -= f; if(res < eps) break; } } return flow;}db maxflow(){ db flow = 0; while(bfs()) { memcpy(cur, head, sizeof(head)); flow += dfs(s, INF); } return flow;}bool judge(db x){ Mem(head, -1); ecnt = -1; for(int i = 1; i <= m; ++i) { addEdge(n + i, a[i].x, INF); addEdge(n + i, a[i].y, INF); } for(int i = 1; i <= n; ++i) addEdge(i, t, x); for(int i = 1; i <= m; ++i) addEdge(s, n + i, 1); return (db)m - maxflow() > eps;}int main(){ while(scanf("%d%d", &n, &m) != EOF) { s = 0; t = n + m + 1; for(int i = 1; i <= m; ++i) a[i].x = read(), a[i].y = read(); if(!m) {printf("1\n1\n\n"); continue;} db L = 0, R = m; db Eps = 1.00/ (db)n / (db)n; while(R - L > Eps) { db mid = (L + R) / 2; if(judge(mid)) L = mid; else R = mid; } judge(L); bfs(); int ans = 0; for(int i = 1; i <= n; ++i) if(dis[i]) ans++; write(ans), enter; for(int i = 1; i <= n; ++i) if(dis[i]) write(i), enter; enter; } return 0;}