애드몬드 카프
-
기본적으로 한 노선의 capacity를 1로 잡으면 된다.(어차피 한번 경로를 잡았을 때 해당 경로의 유량은 1일수밖에 없으므로) 또한, 이러한 성질은 하나의 경로를 잡았을 때 무조건 최대유량이 1이 될 수 밖에 없는 특성을 가지고 있다. 다만, 이 문제에서 독특한 지점은 K명의 직원은 2개의 일을 할 수 있다는 것인데 source에서 capacity가 K인 간선을 추가적으로 만들고, 해당하는 노드에서 모든 직원에게 capacity가 1인 간선을 만들어주면 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define INF 987654321; using namespace std; int capacity[..
[백준 11377번] [네트워크 플로우] 열혈강호 3기본적으로 한 노선의 capacity를 1로 잡으면 된다.(어차피 한번 경로를 잡았을 때 해당 경로의 유량은 1일수밖에 없으므로) 또한, 이러한 성질은 하나의 경로를 잡았을 때 무조건 최대유량이 1이 될 수 밖에 없는 특성을 가지고 있다. 다만, 이 문제에서 독특한 지점은 K명의 직원은 2개의 일을 할 수 있다는 것인데 source에서 capacity가 K인 간선을 추가적으로 만들고, 해당하는 노드에서 모든 직원에게 capacity가 1인 간선을 만들어주면 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define INF 987654321; using namespace std; int capacity[..
2021.02.14 -
전형적인 네트워크 플로우 문제이다. 다만.. 조건을 꼼꼼하게 읽지 않아서 대문자와 소문자가 구분되는지를 놓쳤고, 그로 인해 단순하게 대문자 A ~ Z까지의 최대 유량을 구하는 문제인줄 알았다. 또한 추가적으로 이 문제에서 교훈이 있는데, 단순 그래프가 아닐 경우에는 capacity를 계산할 때 += 처리를 해주어야 한다는 것이다. 이 지점만 주의해주면 된다. 코드 자체는 종만북에 있는 에드몬드 카프 알고리즘 코드를 차용하였다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define INF 987654321; using namespace std; typedef long long ll; int ARR_NUM;..
[백준 6086번] [네트워크 플로우] 최대 유량전형적인 네트워크 플로우 문제이다. 다만.. 조건을 꼼꼼하게 읽지 않아서 대문자와 소문자가 구분되는지를 놓쳤고, 그로 인해 단순하게 대문자 A ~ Z까지의 최대 유량을 구하는 문제인줄 알았다. 또한 추가적으로 이 문제에서 교훈이 있는데, 단순 그래프가 아닐 경우에는 capacity를 계산할 때 += 처리를 해주어야 한다는 것이다. 이 지점만 주의해주면 된다. 코드 자체는 종만북에 있는 에드몬드 카프 알고리즘 코드를 차용하였다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define INF 987654321; using namespace std; typedef long long ll; int ARR_NUM;..
2021.02.12