글 읽기 - 왜 틀린지 모르겠습니다

rhckdrnr123 4년 전 0

시간과 조각들을 매칭해서 이분매칭으로 했는데 어디가 틀린지 모르겠습니다 정말 많이 봐도 도저히 모르겠어요..

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int t, n, m;
vector<int> time[101];
int seed[101];
bool visit[101];
int cnt;
int endTime;
int ans;

bool dfs(int curTime) {
	if (visit[curTime]) return false;
	visit[curTime] = true;
	for (int i = 0; i < time[curTime].size(); i++) {
		int curSeed = time[curTime][i];
		if (seed[curSeed] == -1 || dfs(seed[curSeed])) {
			seed[curSeed] = curTime;
			return true;
		}
	}
	return false;
}

void init() {
	for (int i = 0; i < 101; i++) {
		seed[i] = -1;
		visit[i] = false;
		time[i].clear();
	}
	cnt = 0;
	ans = 0;
	endTime = 0;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> t;
	while (t--) {
		init();
		cin >> n >> m;
		for (int i = 0; i < m; i++) {
			int st, ed;
			cin >> st >> ed;
			endTime = max(endTime, ed);
			int seedcnt;
			cin >> seedcnt;
			for (int j = 0; j < seedcnt; j++) {
				int d;
				cin >> d;
				for (int k = st; k <= ed; k++) {
					bool al = false;
					for (int v = 0; v < time[k].size(); v++) {
						if (time[k][v] == d) al = true;
					}
					if (al) {
						continue;
					}
					else {
						time[k].push_back(d);
					}
				}
			}
		}

		for (int i = 0; i <= endTime; i++) {
			dfs(i);
			for (int j = 0; j <= endTime; j++) {
				visit[j] = false;
			}
		}
		bool flag = false;
		for (int i = 1; i <= n; i++) {
		//	cout << seed[i] << " ";
			if (seed[i] == -1) flag = true;
			ans = max(ans, seed[i]);
		}
		//cout << endl;
		if (flag) {
			cout << -1 << "\n";
		}
		else {
			cout << ans + 1 << "\n";
		}
	}

	return 0;
}

rhckdrnr123 4년 전 0

조각과 시간매칭을 조각을 다운받기 시작한 시간말고 전부 다운받은 시간으로 매칭하니까 맞았습니다.

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

문제

문제

출처

ICPC

왜 틀린지 모르겠습니다

rhckdrnr123 4년 전 0

rhckdrnr123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말