글 읽기 - 최대 유량 관련(주석 포함)

qwe1234567 3년 전 0

포드-풀커슨으로 했는데 자꾸 시간초과가 뜨네요... 시간 복잡도가 O(|f| * N) 이라 이 경우에 400^3 이여서 통과할줄 알았는데 어림도 없네요. Edmond-Karp 로 풀어야 하는건가요? 고수님들 도와주세요ㅠㅠㅠ

#include<bits/stdc++.h>
using namespace std;

map<int, int> G[500]; // e, w
vector<int> I[220];
int N, M;

vector<int> path;
bool vs[550] = { 0 };

int FindAug(int idx, int flow) {
	if (flow == 0) return 0;
	path.push_back(idx);
	vs[idx] = 1;
	if (idx == N + M + 1) {
		return flow;
	}
	for (auto i : G[idx]) {
		if (vs[i.first] || i.second == 0) continue;
		int t = FindAug(i.first, min({ flow, i.second }));
		if (t != 0) return t;
	}
	path.pop_back();
	vs[idx] = 0;
	return 0;
}

int main() {
	//get inp
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		int n, t;
		cin >> n;
		for (int j = 0; j < n; j++) {
			cin >> t;
			I[i].push_back(t);
		}
	}

	//construct directed graph, source: 0, sink: N + M + 1
	for (int i = 1; i <= N; i++) G[0][i] = 1;
	for (int i = 1; i <= N; i++) {
		for (auto j : I[i]) {
			G[i][j + N] = 1e9;
		}
	}
	for (int i = N + 1; i <= N + M; i++) G[i][N + M + 1] = 1;

	//Ford-Fulkerson
	int f = 0;
	while (1) {
		path.clear();
		for (int i = 0; i <= N + M + 1; i++) vs[i] = 0;
		int btn = FindAug(0, 1e9);
		f += btn;
		if (btn == 0) break;
		for (auto i = path.begin(); i + 1 < path.end(); i++) {
			G[*i][*(i + 1)] -= btn;
			if (G[*(i + 1)].count(*i) == 0)
				G[*(i + 1)][*i] = btn;
			else
				G[*(i + 1)][*i] += btn;
		}
	}

	//print oup
	cout << f << "\n";
	return 0;
}

dtc03012 3년 전 0

이거 이분매칭 문제에요 이분매칭 검색 !!

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

문제

문제

출처

ICPC

최대 유량 관련(주석 포함)

qwe1234567 3년 전 0

dtc03012 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말