글 읽기 - 안녕하세요. SCC를 이용한 방법 질문드립니다.

minjun13795 4년 전 0

상어의 능력치가 같을 때, 싸이클이 형성된다는 점을 이용해 SCC로 하나의 상어로 만들어주고 이분 매칭을 통해 구하였는데

WA를 받았습니다. ㅜㅜ 반례를 도저히 찾지 못하겠어서 질문 올립니다.

고수님들 한 수 부탁드립니다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <list>
#include <stack>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#define INF 98765432111
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<pl, pl> pll;
ll N;
vector<ll> adj[50];
ll a[50][3];
ll scc[50];
ll discovered[50];
ll Scnt, Vcnt;
stack<ll> st;
ll tajan(ll here)
{
	ll ret = discovered[here] = Vcnt++;

	st.push(here);
	for (auto there : adj[here])
	{
		if (discovered[there] == -1)
			ret = min(ret, tajan(there));
		else if (scc[there] == -1)
			ret = min(ret, discovered[there]);
	}

	if (discovered[here] == ret)
	{
		while (true)
		{
			ll temp = st.top(); st.pop();
			scc[temp] = Scnt;
			if (temp == here) break;
		}
		Scnt++;
	}

	return ret;
}
vector<ll> trans_adj[50];
bool c[50];
ll d[50];
bool dfs(ll x)
{
	for (auto y : trans_adj[x])
	{
		if (c[y]) continue;
		c[y] = true;
		if (d[y] == -1 || dfs(d[y]))
		{
			d[y] = x;
			return true;
		}
	}
	return false;
}
int main()
{
	memset(scc, -1, sizeof(scc));
	memset(discovered, -1, sizeof(discovered));
	scanf("%lld", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%lld %lld %lld", &a[i][0], &a[i][1], &a[i][2]);
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (i == j || a[i][0] < a[j][0] || a[i][1] < a[j][1] || a[i][2] < a[j][2]) continue;
			adj[i].push_back(j);
		}
	}

	for (int i = 0; i < N; i++)
		if (scc[i] == -1) tajan(i);

	for (int i = 0; i < N; i++)
	{
		for (auto j : adj[i])
			if (scc[i] != scc[j])
				trans_adj[i].push_back(j);
	}
	ll answer = 0;
	memset(d, -1, sizeof(d));
	for (int i = 0; i < Scnt; i++)
	{
		memset(c, false, sizeof(c));
		if (dfs(i)) answer++;
	}
	for (int i = 0; i < Scnt; i++)
	{
		memset(c, false, sizeof(c));
		if (dfs(i)) answer++;
	}
	printf("%lld", Scnt - answer);

	return 0;
}

chw0501 4년 전 1

1 1 1

2 2 2

correct ans: 1

2번이 1번을 잡아먹고 4번이 2,3번을 잡아먹습니다.

minjun13795 4년 전 1

감사합니다 97번째 줄이 틀렸었네요. 고쳐도 통과를 못하길래 제 코드의 반례를 하나 더 찾았습니다.

5
5 5 5
5 5 5
4 3 3
3 4 3
3 3 4

ans: 1

SCC로 풀기는 했는데 SCC가 출제의도는 아닌거 같군요...

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

문제

문제

출처

ICPC

안녕하세요. SCC를 이용한 방법 질문드립니다.

minjun13795 4년 전 0

chw0501 4년 전 1

minjun13795 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말