archives

https://www.acmicpc.net/problem/11375 기본적인 이분 매칭 #include #include #include #include using namespace std; const int MAX_N = 1001; const int MAX_M = 1001; int n, m; bool adj[MAX_N][MAX_M]; vector aMatch, bMatch; vector visited; bool dfs(int a) { if(visited[a]) return false; visited[a] = true; for(int b = 0; b < m; ++b) if(adj[a][b]) if(bMatch[b] == -1 || dfs(bMatch[b])) { aMatch[a] = b; bMatch[b]..

n개의 정점이 있을때, 두개씩 짝지어 주는 방법론. 각각의 연결된 정점은 끝점을 공유하지 않는다. 아래의 왼쪽 그림처럼 끝점을 공유하면 안되고, 오른쪽의 녹색 라인처럼 2개씩 짝지어져야함. ex)1. 아래와 같은 그래프가 있다. 파란 선은 도달 가능함을 의미한다. A부터 시작해서 하나씩 매칭해보자. A에서 2로 도달 가능하므로 이어준다.2. B에서 매칭을 시도하는데 B에서도 2로 가는게 가능하다. A에서 2 대신 5와 매칭이 가능하므로 A-5로 다시 매칭을 해주고 B는 2와 이어준다. 이런식으로 매칭을 시켰을때 가장 많은 쌍을 구하는걸 최대 매칭 문제라고 한다.

https://www.acmicpc.net/problem/6086 주의할점 : a에서 b까지 가는 경로가 여러개 있을수 있어 대역폭을 더해줘야 함. #include #include #include #include using namespace std; const int MAX_V = 500; int V = 52; int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V]; vector adj[MAX_V]; int networkFlow(int source, int sink) { //memset(flow, 0, sizeof(flow)); for(int i=0;i> E; //V는 정점의 갯수, E는 대역폭의 갯수 //memset(capacity, 0, sizeof(capacity)); ..

현실세계의 인터넷이라고 가정하자. 서버 s에서 집 컴퓨터 t까지 경로가 여러개 있고, 각각의 경로에는 보낼수 있는 최대한의 대역폭이 있다. 집 컴퓨터 t에서 자료를 다운로드받는다고 하면 s에서 보낼 수 있는 대역폭의 최대량은 얼마일까? (받는 쪽에서는 들어오는 만큼 다 받을수 있다고 가정한다.) 를 구하는 문제이다. 역시나 설명 잘된 블로그 : http://kks227.blog.me/220796029558 1. s에서 t로 최대한 보낼 수 있는 대역폭의 양은 얼마일까? 아주 잠깐 살펴보면 (D에서 T로 가는) 2 + (E에서 T로 가는) 5 인 7이 일단 보이는 최대값임을 알수 있다. 하지만 만약 E로 도달할수 있는 길이 C에서 E하나뿐이고, C->E 대역폭이 4라면 E->T 대역폭이 5라도 최대 대역폭..