[Algorithm] cpp 백준 3611번: 팀의 난이도

문제

링크: https://www.acmicpc.net/problem/3611
요약: 같은 팀이 되었을 때 서로 일을 못 하는 사람들의 쌍이 주어질 때, 팀의 난이도(내부 불화 간선 수/팀원 수)를 최대화하는 팀을 찾아 구성원을 출력.
제한: n ≤ 100, m ≤ 1000, 같은 쌍 중복 없음.

입력/출력

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
입력
n m
a1 b1
a2 b2
...

출력
k
v1
v2
...
vk

예시

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
입력
5 6
1 5
5 4
4 2
2 5
1 2
3 1

출력(가능한 해 중 하나)
4
1
2
4
5

접근 개요

이 문제는 최대 밀도 부분 그래프(densest subgraph) 문제와 동치입니다. 목표는 S ⊆ V에 대해 |E(S)|/|S|를 최대화하는 S를 구하는 것.
표준 기법: 파라메트릭 탐색. 어떤 실수 r에 대해 f(r) = max_S (|E(S)| - r·|S|)를 계산하고, f(r) ≥ 0인 최대 r = r를 찾으면, r가 최대 밀도입니다.
f(r)은 s-t 최소 절단(= 최대 유량)으로 계산할 수 있으며, r에 대해 단조성이 있어 이분 탐색로 r*를 구합니다. 절단의 s-도달 집합이 곧 최적 팀 후보가 됩니다.

Mermaid로 보는 네트워크 구성

graph LR
  S((source)) --> Ei[edge nodes (m개)]
  Ei --> Vj[vertex nodes (n개)]
  Vj --> T((sink))

구체적 간선

S → e_i: 용량 1
e_i → u, e_i → v: 용량 INF (간선 i = (u, v))
각 정점 v: v → T 용량 r

이때 최소절단 값은 m - max_S (|E(S)| - r·|S|)와 대응하여, f(r) = m - mincut(S,T)로 환원됩니다.

알고리즘 설계

r의 범위를 [0, m]로 두고 이분 탐색(고정 70~80회)합니다.
각 r마다 위 네트워크를 만들고 Dinic으로 최대유량 = 최소절단을 구합니다.
f(r) = m - mincut. f(r) > 0이면 더 큰 r를 탐색(가능성 있음), 아니면 줄입니다.
r* 근방에서 s-도달 정점 집합을 읽어 최적 팀을 복원합니다. 동률이면 아무 집합이나 허용.

정당성(요지)

최대밀도부분그래프의 고전적 파라메트릭 환원입니다. f(r) = max_S (|E(S)| - r|S|)의 부호는 r ≤ |E(S)|/|S|인 S의 존재 여부와 동치이므로, r* = sup{r | f(r) ≥ 0} = max_S |E(S)|/|S|입니다. 네트워크 구성은 가중 정점 컷으로 f(r)을 정확히 계산합니다.

복잡도

이분 탐색 횟수: O(log(1/ε)) ≈ 80.
한 번의 유량: 정점 O(n+m), 간선 O(m+n+m) 수준. n ≤ 100, m ≤ 1000이므로 충분히 빠릅니다.
총합 대략: O(80 · maxflow(V,E)). 실측상 수 밀리초 내.

구현 (C++)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Dinic {
	struct Edge {
		int to, rev;
		double cap;
	};
	int N;
	vector<vector<Edge>> graph;
	vector<int> level, work;
	const double EPS = 1e-9;

	explicit Dinic(int n) : N(n), graph(n), level(n), work(n) {}

	void addEdge(int u, int v, double c) {
		Edge a{v, (int)graph[v].size(), c};
		Edge b{u, (int)graph[u].size(), 0.0};
		graph[u].push_back(a);
		graph[v].push_back(b);
	}

	bool bfs(int s, int t) {
		fill(level.begin(), level.end(), -1);
		queue<int> q;
		level[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (const auto &e : graph[u]) {
				if (level[e.to] < 0 && e.cap > EPS) {
					level[e.to] = level[u] + 1;
					q.push(e.to);
				}
			}
		}
		return level[t] >= 0;
	}

	double dfs(int u, int t, double f) {
		if (u == t) return f;
		for (int &i = work[u]; i < (int)graph[u].size(); i++) {
			Edge &e = graph[u][i];
			if (e.cap > EPS && level[e.to] == level[u] + 1) {
				double ret = dfs(e.to, t, min(f, e.cap));
				if (ret > EPS) {
					e.cap -= ret;
					graph[e.to][e.rev].cap += ret;
					return ret;
				}
			}
		}
		return 0.0;
	}

	double maxflow(int s, int t) {
		double flow = 0.0;
		while (bfs(s, t)) {
			fill(work.begin(), work.end(), 0);
			while (true) {
				double pushed = dfs(s, t, 1e100);
				if (pushed <= EPS) break;
				flow += pushed;
			}
		}
		return flow;
	}

	// After running maxflow, get vertices reachable from s in residual graph
	vector<int> mincut_reachable_from_source(int s) {
		const double EPS2 = 1e-9;
		vector<int> vis(N, 0);
		queue<int> q;
		vis[s] = 1;
		q.push(s);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (const auto &e : graph[u]) {
				if (!vis[e.to] && e.cap > EPS2) {
					vis[e.to] = 1;
					q.push(e.to);
				}
			}
		}
		return vis;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	if (!(cin >> n >> m)) return 0;
	vector<pair<int,int>> edges;
	edges.reserve(m);
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		--a; --b;
		edges.emplace_back(a, b);
	}

	// Trivial case: no edges -> any single person is optimal (ratio 0)
	if (m == 0) {
		cout << 1 << "\n" << 1 << "\n";
		return 0;
	}

	auto build_and_flow = [&](double r, bool want_set, vector<int> &out_set)->double {
		// Node indexing:
		// 0..n-1: vertex nodes
		// n..n+m-1: edge nodes
		// s = n + m, t = n + m + 1
		int S = n + m;
		int T = n + m + 1;
		int tot = n + m + 2;
		const double INF = 1e100;

		Dinic din(tot);

		// s -> edge-node (capacity 1)
		for (int i = 0; i < m; i++) {
			int eNode = n + i;
			din.addEdge(S, eNode, 1.0);
		}

		// edge-node -> endpoint vertex (INF)
		for (int i = 0; i < m; i++) {
			int u = edges[i].first;
			int v = edges[i].second;
			int eNode = n + i;
			din.addEdge(eNode, u, INF);
			din.addEdge(eNode, v, INF);
		}

		// vertex -> t (capacity r)
		for (int v = 0; v < n; v++) {
			din.addEdge(v, T, r);
		}

		double f = din.maxflow(S, T);

		if (want_set) {
			auto vis = din.mincut_reachable_from_source(S);
			vector<int> pick;
			for (int v = 0; v < n; v++) if (vis[v]) pick.push_back(v + 1); // 1-indexed
			if (pick.empty()) {
				// As a fallback to guarantee non-empty output
				pick.push_back(1);
			}
			sort(pick.begin(), pick.end());
			out_set = move(pick);
		}
		return f;
	};

	// Binary search r*: largest r with delta = m - maxflow > 0 holds for r < r*, and delta == 0 for r >= r*.
	double lo = 0.0, hi = (double)m; // ratio is in [0, m]
	for (int it = 0; it < 80; it++) {
		double mid = (lo + hi) * 0.5;
		vector<int> dummy;
		double flow = build_and_flow(mid, false, dummy);
		double delta = (double)m - flow; // max_{S} (|E(S)| - r|S|)
		if (delta > 1e-9) lo = mid; else hi = mid;
	}
	double r_star = lo;

	// Retrieve the set: bias slightly below r* to avoid tie picking the empty set
	vector<int> answerSet;
	build_and_flow(max(0.0, r_star - 1e-7), true, answerSet);

	cout << (int)answerSet.size() << "\n";
	for (int v : answerSet) cout << v << "\n";
	return 0;
}