글 읽기 - 혹시 이문제 포드풀커슨으로는 AC 못받나요?

sgc109 6년 전 0

우선 시간복잡도로는 매우 큰수가나와서 쉽게 AC가 나오지않을거라는것을 감안하고 한번 제출해봤는데 TLE가 나와서

혹시 홉크로프트카프같이 더 빠른 알고리즘을써야 AC를받을수가있는건지 궁금합니다

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <string>
#include <set>
#include <cmath>
// #include <unordered_set>
// #include <map>
#define REP(i,a,b) for(int i = a; i < b;++i) 
#define FOR(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > piii;

const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 1000000;

int n;
int adj[MAX_N][2];
int aMatch[MAX_N];
int bMatch[MAX_N];
int visited[MAX_N];

bool dfs(int a){
	if(visited[a]) return false;
	visited[a] = 1;
	for(int b : adj[a]){
		if(bMatch[b]==-1 || dfs(bMatch[b])){
			bMatch[b] = a;
			aMatch[a] = b;
			return true;
		}
	}
	return false;
}
int bipartite() {
	int ret=0;
	memset(aMatch,-1,sizeof(aMatch));
	memset(bMatch,-1,sizeof(bMatch));
	FOR(a,n) {
		memset(visited,0,sizeof(visited));
		if(dfs(a)) ++ret;
	}
	return ret;
}

int main() {
	inp1(n);
	FOR(i,n){
		inp2(adj[i][0],adj[i][1]);
	}

	int maxMatch = bipartite();

	if(maxMatch != n) {
		printf("-1\n");
		return 0;
	}

	FOR(i,n){
		printf("%d\n",aMatch[i]);
	}

	return 0;
}