15562 : 네트워크

풀이

모든 정점에 대한 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-04-13 09:30

Read more posts by this author