mincut 썸네일형 리스트형 BOJ)9169 나는 9999번 문제를 풀 수 있다 문제:icpc.me/9169 풀 수있다고 생각한 사람과 풀 수 없다고 생각한 사람의 생각이 주어지고 사람들의 친구 관계가 주어지는데 이 때 생각을 바꾸거나 친구사이에 투표한 결과가 서로 다른 관계의 수의 합의 최솟값을 구하는 문제이다. 우리는 풀 수 있다고 생각한 사람을 소스에 연결하고 풀 수 없다고 생각한 사람을 싱크에 연결 한 뒤 서로 다른 경우에 간선을 한 방향으로 같은 경우에 양방향으로 연결해줌으로서 그래프를 모델링 해준 뒤 cut의 개수를 구하면 어긋나는(생각이 다른) 경우의 개수이므로 min cut을 구해주면 된다. mincut은 Maxflow-Mincut Theorem에 의하여 maximum flow를 구해줌으로서 해결 된다. 123456789101112131415161718192021222.. 더보기 BOJ)5398 틀렸습니다 문제: icpc.me/5398 충돌되는 단어들에 대하여 가로단어와 세로단어로 이루어진 이분 그래프를 형성시켜준 뒤 mincut을 구해주어 모든단어-mincut을 구해주면 되는 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include using namespace std;int t, h, v, x, y;char a[2001][2001];int c[2001][2001];int check[1001];int backmatch[1001];vector vt;bool dfs(int her.. 더보기 이전 1 다음