글 읽기 - 궁금한 내용이 있습니다.(MCMF)

kkw564 6년 전 0

이 문제에서 능력치를 입력받게 되는데요

능력치가 0이어도 cost가 0인 엣지를 생성시켜주면 mcmf에서 반례가 될 상황이 어떤경우가 있는건가요?

아래 3가지 경우를 들어두었습니다.

행여나 전체 코드가 필요하다면 말씀해주시면 다시올리겠습니다.

// AC

		for (int i = 1; i <= 11; i++)
		{
			for (int j = 23; j <= 23 + 10; j++)
			{
				int cost;
				scanf("%d", &cost);

				if (cost == 0)
					continue;
				else
					addEdge(i + POSITION, j, -cost, 1);
			}
		}

// AC
		for (int i = 1; i <= 11; i++)
		{
			for (int j = 23; j <= 23 + 10; j++)
			{
				int cost;
				scanf("%d", &cost);

				if (cost == 0)
					addEdge(i + POSITION, j, 0, 0);
				else
					addEdge(i + POSITION, j, -cost, 1);
			}
		}

// WA
		for (int i = 1; i <= 11; i++)
		{
			for (int j = 23; j <= 23 + 10; j++)
			{
				int cost;
				scanf("%d", &cost);

				addEdge(i + POSITION, j, -cost, 1);
			}
		}

ntopia 6년 전 1

min cost max flow 를 찾는다면

cost 가 0인 간선에도 유량이 흐르도록 하는 flow 를 찾을텐데요 (max flow 를 찾으니까)

문제 조건에 능력치가 0이면 배정을 아예 하면 안된다고 했으니, 결국 이러면 오답이 나오는거죠.

kkw564 6년 전 0

하지만 어떠한 경우에도 cost가 음수인 값은 주어지지 않으니 능력치가 0~100사이면

0이 항상 최댓값을 가지기때문에 0을 포함한 포지션 결과값은 절대 나올 수 없지 않나요?

제 생각의 어느 부분에 착오가 있는지 알려주시면 감사하겠습니다.

ntopia 6년 전 1

무슨 말인지 잘 모르겠네용...

mcmf 가 구하는게 가능한 max flow 들 중에서 cost가 최소인 것 이잖아요?

그러니까 cost가 0인 간선으로도 유량이 흐르게 될텐데, 이게 문제가 되는거 아닌가요?

kkw564 6년 전 0

아 무슨말인지이해했습니다 감사합니다!!

ntopia 6년 전 1

보충 설명을 드리자면

어떤 선수가 cost가 0인 포지션으로 배정되어버리는 바람에

다른 선수가 원래 배정되어야할 곳에 배정되지 못하고 다른 곳으로 배정되는데

하필이면 그게 전체 cost의 합을 더 작게 만들어버리는 경우가 존재하는 것 같네요

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

문제

문제

출처

ICPC

궁금한 내용이 있습니다.(MCMF)

kkw564 6년 전 0

ntopia 6년 전 1

kkw564 6년 전 0

ntopia 6년 전 1

kkw564 6년 전 0

ntopia 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말