글 읽기 - 네트워크 플로우 방식으로 잘 모르겠습니다.

(追記) (追記ここまで)

네트워크 플로우 방식으로 잘 모르겠습니다.

11378번 - 열혈강호 4

powerlsj7 1년 전 0

이분매칭으로는 여차저차해서 풀었는데...

똑같이

용량을 1로 전부해놓고

최대유량을 구한뒤

용량을 k만큼 늘려서 최대 유량을 구하는 방식을 떠올렸는데...

이 방법을 어떻게 구현해야할 지 모르겠습니다. ..

시작 노드를 0 끝 노드를 2001로 두고

간선을 다 연결해주었습니다.

1,2,3,4,5 면 다음 연결되는 노드는 1001,1002, ...

이분매칭은 그냥 탐색 함수를 k만큼 더 돌리면 되니까 간단했는데

유량 개념은 공간을 다시 늘려줘야 되니까 잘 모르겠네요. 내일되면 뭔가 떠오를지는 모르겠는데..

풀이는 아직 안봤습니다.

도와주십쇼!!

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n, m,k;
vector<int> arr[2002];
int flow[2002][2002];
int capacity[2002][2002];
int visit[2002];
int GetFlow(int s,int e,bool second)
{
	int result = 0;
	queue<int> q;
	while (true)
	{
		q.push(s);
		fill(visit, visit + 2002, -1);
			int minFlow = 1000;
		while (!q.empty())
		{
		int current	=q.front();
			q.pop();
			for (int i = 0; i < (int)arr[current].size(); i++)
			{
				int next = arr[current][i];
				if (capacity[current][next] - flow[current][next] > 0 && visit[next]==-1)
				{
					visit[next] = current;
					if (next == e)
					{
						if (second)
						{
						k--;
						}
						break;
					}
					q.push(next);
				}
			}
		}
		if (visit[e] == -1)
		{
			break;
		}
		for (int i = e; i != s; i = visit[i])
		{
			minFlow = min(minFlow, capacity[visit[i]][i]-flow[visit[i]][i]);
		}
		for (int i = e; i != s; i = visit[i])
		{
			flow[visit[i]][i] += minFlow;
			flow[i][visit[i]] -= minFlow;
		}
		result += minFlow;
	}
	return result;
}
int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m>>k;
	int a, b;
	for (int i = 1; i <= n; i++)
	{
		cin >> a;
		arr[0].push_back(i);
		capacity[0][i] = 1;
		for (int j = 0; j < a; j++)
		{
			cin >> b;
		arr[i].push_back(b+1000);
		arr[b+1000].push_back(i);
		arr[b + 1000].push_back(2001);
		capacity[b + 1000][2001] = 1+k;
		capacity[i][b+1000] = 1;
		}
	}
	int answer= GetFlow(0, 2001,false);
	//각 사람마다 최소 1개의 일을 할 수 있게 최대 유량 구한뒤
	// 일을 더 할 수 있도록 유량을 늘려줌
	for (int i = 0; i <= 2001; i++)
	{
		fill(capacity[i], capacity[i] + 2002, k-1);
	}
	answer += GetFlow(0, 2001,true);
	cout << answer;
	return 0;
}

tjgus1668 1년 전 1

안녕하세요.

저는 이 문제를 풀진 않았지만, 문제를 읽어보고 나니 열혈강호 3과 비슷한 느낌의 풀이가 떠오릅니다.

우선 소스 -> 각 직원 간선의 용량은 작성자님 생각처럼 1이 되어야 합니다. 그러면 k만큼의 유량을 이후에 어떻게 흘릴 수 있느냐가 문젠데..

소스와 각 직원 사이를 연결하는 특별한 노드가 하나 더 있다면 어떨까요? 이 노드와 연결된 간선의 용량을 무엇으로 정할지, 이 노드가 있음으로써 생기는 영향이 무엇일지 생각해보면 좋을 것 같습니다.

powerlsj7 1년 전 1

헉, 이런 생각은 못해봤는데.. 좀 고민해보니 풀 수 있을지도 모르겠습니다. 힌트 감사드립니다!!

powerlsj7 1년 전 1

풀었습니다. 유량의 공간을 처음 사람쪽에만 늘려주면 되고 k만큼만 탐색이 되도록하면 되는 문제였군요..

계속 해메였던 것이 유량을 일에도 늘리고 모두 늘려서 그랬습니다. ᅲ

역시 알고리즘을 제대로 파악했으면 쉽게 풀었겠지만... 덕분에 네트워크 플로우가 좀 이해갔고, 풀이도 안보고 풀었습니다. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

네트워크 플로우 방식으로 잘 모르겠습니다.

powerlsj7 1년 전 0

tjgus1668 1년 전 1

powerlsj7 1년 전 1

powerlsj7 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말