MCMF 썸네일형 리스트형 BOJ)3073 집으로 가는 길 문제: icpc.me/3073 집과 아이를 1:1 매칭시켜 주어야 하는데 매칭은 항상 보장되고 이때의 아이들의 최소 이동거리를 출력하는 문제이다. 1:1 매칭이 항상 보장되기 때문에 MCMF로 모델링을 하여 소스->아이->간선->집->싱크로 모델링 해주면 된다. 이 때 각 간선들의 cost를 1로 설정해주면 된다. 다만 문제에 함정이 있는데 언제 고쳐질지는 모르겠지만 입력 N,M이 20~30으로 표기되어 있지만 100 넘게 들어오는거 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879.. 더보기 BOJ)7154 Job Postings 문제: icpc.me/7154 학생들이 원하는 일들과 일들의 개수 등이 주어질 때 학생들의 전체 만족도의 합의 최댓값을 구하는 문제이다. 학생들이 일을 선택하는 것을 학생과 일을 1:1로 매칭한다고 생각한다면 MCMF 문제로 만족도를 구할 수 있다. 모델링은 소스-> 일 -> 학생 -> 싱크로 구성해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#include #include #include #include .. 더보기 BOJ)8992 집기 게임 문제: icpc.me/8992 두 선분을 최대한 집으면서 점수를 최대한 많이 얻으려고 할 때 집을 수 있는 선분의 개수와 최대 점수를 구하는 문제이다. 우리는 두선분을 집는걸 우선시 해야하므로 두선분을 동시에 집는걸 capacity를 이용하여 모델링해주며 이 때 두선분을 집을 때 얻는 점수를 cost로 모델링해준 뒤 MCMF를 통하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102.. 더보기 BOJ)10937 두부 모판 자르기 문제: icpc.me/10937 두부를 1x2 혹은 2x1 모양으로 자르는데 자르는 두부에 써있는 알파벳에 따라 점수를 다르게 받는다고 한다. 이 때 최대 점수를 받도록 두부를 자르는 경우를 출력하는 문제이다. 우리는 두부판을 검은색과 흰색으로 이루어진 체스판으로 생각하면 항상 두부는 검은색 1개 흰색 1개로 매칭된다는걸 알 수 있다. 따라서 우리는 결국 이분 그래프에서의 최대 매칭을 구하면서 그 때의 최대비용을 구해야하는데 매칭이 안되는 경우도 있으니 이분 그래프중 소스에 매칭 되는 부분들을 전부 싱크로 1씩 capacity를 준다. 이후 모든 간선의 capacity를 1로 주고 점수에 맞게 cost를 준뒤 MCMF를 이용하여 maximum cost를 구해내면 된다. 1234567891011121314.. 더보기 BOJ)11410 칙칙폭폭 문제: icpc.me/11410 기차가 1->N까지 이동할 때 도시 i에서 j로 이동하는 사람의 수와 그때 기차요금이 주어질 때 기차에 동시에 최대 p명의 사람이 탈 수 있을 때 기차가 낼 수 있는 최대 수익을 출력하는 문제이다. i->i+1(i = 1~N)에 대하여 capcity를 INF, cost를 0으로 간선을 생성해주고 i 에서 j로 이동하는 경우에 이동하는 사람의 수를 capacity로 기차요금을 cost로 간선을 생성해 준 뒤 소스에서 ->1로 N에서 -> 싱크로 capacity p의 간선을 연결해 준 뒤 MCMF를 통하여 maximum cost를 구해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041.. 더보기 BOJ)9413 제주도 관광 문제: icpc.me/9413 시작 지점과 도착 지점 그리고 중간 경로상의 모든 정점들이 겹치지 않게 두 경로를 만들 때 가장 많은 정점을 순회하는 경우의 순회한 정점 수를 출력하는 문제이다. 우리는 정점을 분할 시킨 뒤 정점 사이의 capacity를 1로 주어서 정점이 중복 선택 안되게 가능하고 가장 많은 정점은 maximum cost를 구하면 되므로 MCMF를 이용하여 해결해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939.. 더보기 BOJ)2311 왕복 여행 문제:icpc.me/2311 N개의 나라들이 있을 때 1~N까지 도시를 왕복할 때의 최소비용을 구하는 문제이다. 단 이 때 한번 갔던 경로로는 다시 이동할 수 없다. 우리는 소스->1->N->싱크로 그래프를 모델링 해준 뒤 소스->1 N->싱크의 간선만 capacity를 2로 주고 나머지 간선의 capacity를 1로 준 뒤 MCMF를 이용하여 mincost를 구할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include #include #include #inclu.. 더보기 BOJ)1585 경찰 문제: icpc.me/1585 들어가는 시간과 나오는 시간들의 셋을 이분 매칭시켜 mincost와 maxcost를 구하는 문제이다. 소스-> 들어가는 시간 -> 나오는 시간 ->싱크로 모델링을 해준 뒤 MCMF를 이용하여 mincost와 maxcost를 구하면 된다. 이 때 비용은 들어가는 시간->나오는 시간 일 때 min((S-T)*(S-T),F)으로 정의된다. 주의 할점은 maximum flow가 n이 안될 때 -1을 출력하는데 한번만 출력해야한다. 필자의 경우 두번 출력하여 3번 틀렸다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364.. 더보기 BOJ)4716 풍선 문제: icpc.me/4716 모든 팀에게 풍선을 달아줄 때 풍선을 달기 위해 이동해야하는 최소 거리를 출력하는 문제이다. 그래프 모델링을 소스->방A,B -> N개의 팀-> 싱크 로 준 뒤 거리를 cost로 풍선을 capacity로 한 MCMF의 minimum cost를 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include #include #include #include #define INF 987654321using name.. 더보기 BOJ)11407 책 구매하기3 문제: icpc.me/11407 N명의 사람과 M개의 서점이 있을 때 각 사람들이 살 수 있는 책의 수와 각 서점이 파는 책의 개수 그리고 i번째 사람이 j번째 책을 살때의 비용과 살 수 있는 개수가 주어질 때 최대로 책을 사면서 비용을 최소로하는 경우의 살 수 있는 책의 개수와 비용을 출력하는 문제이다. 우리는 살 수 있는 책의 개수를 capacity로 비용을 cost로 그래프를 모델링 해준 뒤 MCMF를 실행시켜주면 원하는 답을 구할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677.. 더보기 이전 1 2 다음