글 읽기 - 범죄파티 틀리는 이유를 모르겠습니다

highalps 7년 전 0

dfs만 활용하는 이분매칭 알고리즘을 memset 없이 최적화 해서 돌렸는데

시간 초과도 아니고 계속 틀리는 이유를 모르겠네요.

도움이 필요합니당...

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long

int n, w, cnt = 1;
struct  dot {
	int v, c;
	dot() {}
	dot(int v, int c) :v(v), c(c) {}
};
vector <int> chk;
vector <int> back;
vector <vector <dot> >vec;
bool bip(int v, int k)
{
	for (int i = 0; i < vec[v].size(); i++)
	{
		int u = vec[v][i].v;
		int c = vec[v][i].c;
		if (c > k)continue;
		if (chk[u] == cnt)continue;
		chk[u] = cnt;
		if (back[u] < w + 1 || bip(back[u] - (w / n)*n, k)) {
			back[u] = v + w;
			return true;
		}
	}
	return false;
}
int main()
{
	scanf("%d", &n);
	vec = vector<vector <dot> >(n + 1);
	back = vector<int>(2 * n + 1, -1);
	chk = vector<int>(2 * n + 1, -1);
	for (int i = 1, a, b; i <= n; i++) {
		for (int j = 0; j < 2; j++) {
			scanf("%d %d", &a, &b);
			vec[i].emplace_back(a, b);
		}
	}
	int l = 0, r = 1000000;
	while (l <= r) {
		int t = 0;
		int mid = (l + r) / 2;
		for (int i = 1; i <= n; i++) {
			if (bip(i, mid))t++;
		}
		if (t == n)r = mid - 1;
		else l = mid + 1;
		cnt++;
		w += n;
	} // l
	printf("%d\n", l > 1000000 ? -1 : l);
}

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

문제

문제

출처

ICPC

범죄파티 틀리는 이유를 모르겠습니다

highalps 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말