글 읽기 - 이분매칭으로 불가능한가요??

seonh4996 4년 전 1

dsu로 풀려다가 이분매칭으로 풀어봤는데요 ... 시간초과가 나네요..

이분매칭 시간복잡도가 이 문제에서는 O(NL) 맞나요?

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

vector<int> v[600002];
bool visit[600002];
int degree[600002];

bool dfs(int here){
	if(visit[here])return false;
	visit[here] = 1;
	
	for(auto next : v[here]){
		if(degree[next] == -1 || dfs(degree[next])){
			degree[next] = here;
			return true;
		}
	}
	
	return false;
}

int main(){
	cin.tie(0);
	ios_base :: sync_with_stdio(0);
	
	int N, L;
	cin >> N >> L;
	
	for(int i = 0; i < N; i++){
		int a, b;
		cin >> a >> b;
		v[i].push_back(a+N);
		v[i].push_back(b+N);
	}
	
	
	fill(degree, degree+600001, -1);
	for(int i = 0; i < N; i++){
		fill(visit, visit+600001, 0);
		
		if(dfs(i)){
			cout << "LADICA" << '\n';
		}
		else{ cout << "SMECE" << '\n';}
	
	}
}

seonh4996 4년 전 0

이분매칭으로는 절대 못푸는 문제였네요..

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

문제

문제

출처

ICPC

이분매칭으로 불가능한가요??

seonh4996 4년 전 1

seonh4996 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말