풀이
모든 정점에 대한 sum(max(outdegree - indegree, 0))이 답이다.
for (i = 1 ~ n) ans += max(out[i] - in[i], 0);
for (i = 1 ~ n) ans += d[i]; ans /= 2;
for (i = 1 ~ n) ans += max(d[i], 0);
등등 degree를 관리하는 방식에 따라 같은 식을 여러가지로 변형할 수 있겠다.
어떤 정점의 outdegree가 indegree보다 크다는 것은
해당 정점을 하나보다 많은 네트워크로 분리해서 나누어서 다음 노드로 나아가야 함을 의미한다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, i, u, v, r, d[1000001];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m; n++;
while (m--) cin >> u >> v, d[v]++, d[u]--;
while (n--) r += max(d[n], 0);
cout << r;
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이