글 읽기 - 9576) 에드몬드 카프 알고리즘으로 풀 수 없는 문제인가요?

opop20207 4년 전 1

이분매칭으로도 풀어보고

에드몬드 카프로도 풀어보고싶어서 짜봤어요

그런데 시간초과가 나는데

O(VE^2)라 시간초과가 나는가요...

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };
const int ddx[8] = { -1,-1,-1,0,0,1,1,1 };
const int ddy[8] = { -1,0,1,-1,1,-1,0,1 };
const int INF = 0x7fff5037;
const ll INF_LL = 0x7fffffffffffffff;
bool cidx(ll x, ll y, ll N, ll M) { return x >= 0 && x < N && y >= 0 && y < M; }
#define X first
#define Y second
#define pb push_back
#define sz(a) ((int)(a.size()))
#define sf1(a) cin >> a
#define sf2(a,b) cin >> a >> b
#define sf3(a,b,c) cin >> a >> b >> c
#define sf4(a,b,c,d) cin >> a >> b >> c >> d
#define sf5(a,b,c,d,e) cin >> a >> b >> c >> d >> e
#define pf1(a) cout << (a) << ' '
#define pf2(a,b) cout << (a) << ' ' << (b) << ' '
#define pf3(a,b,c) cout << (a) << ' ' << (b) << ' ' << (c) << ' '
#define pf4(a,b,c,d) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' '
#define pf5(a,b,c,d,e) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << ' '
#define pfn0() cout << '\n'
#define pfn1(a) cout << (a) << '\n'
#define pfn2(a,b) cout << (a) << ' ' << (b) << '\n'
#define pfn3(a,b,c) cout << (a) << ' ' << (b) << ' ' << (c) << '\n'
#define pfn4(a,b,c,d) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << '\n'
#define pfn5(a,b,c,d,e) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << '\n'
#define pfv(v) for(auto const &t : v) pfn1(t)
const int SIZE = 1100*2;
struct edge {
	int to, c, f;
	edge* dual;
	edge():edge(-1,0){}
	edge(int to1, int c1) :to(to1), c(c1), f(0), dual(nullptr) {}
	int spare() {
		return c - f;
	}
	void addFlow(int f1) {
		f += f1;
		dual->f -= f1;
	}
};
int N, M, T;
vector<edge*> adj[SIZE];
int pre[SIZE];

void init() {
	for (int i = 0; i <= N*2+1; i++) {
		adj[i].clear();
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	sf1(T);
	while (T--) {
		sf2(N, M);
		int S = 0, E = 2 * N + 1;
		init();
		for (int i = 1; i <= N; i++) {
			edge* e1 = new edge(i, 1);
			edge* e2 = new edge(S, 0);
			e1->dual = e2;
			e2->dual = e1;
			adj[S].pb(e1);
			adj[i].pb(e2);
		}
		for (int i = 1; i <= M; i++) {
			int t1, t2;
			sf2(t1, t2);
			for (int j = t1; j <= t2; j++) {
				edge* e1 = new edge(j+N, 1);
				edge* e2 = new edge(i, 0);
				e1->dual = e2;
				e2->dual = e1;
				adj[i].pb(e1);
				adj[j+N].pb(e2);
			}
		}
		for (int i = 1 + N; i <= 2 * N; i++) {
			edge* e1 = new edge(E, 1);
			edge* e2 = new edge(i, 0);
			e1->dual = e2;
			e2->dual = e1;
			adj[i].pb(e1);
			adj[E].pb(e2);
		}
		int total = 0;
		while (1) {
			edge* path[SIZE] = { 0 };
			queue<int> q;
			fill(pre, pre + SIZE, -1);
			q.push(S);
			while (!q.empty() && pre[E] == -1) {
				int curr = q.front();
				q.pop();
				for (auto e : adj[curr]) {
					int next = e->to;
					if (e->spare() && pre[next] == -1) {
						q.push(next);
						pre[next] = curr;
						path[next] = e;
						if (next == E) break;
					}
				}
			}
			if (pre[E] == -1) break;
			int flow = INF;
			for (int i = E; i != S; i = pre[i]) {
				flow = min(flow, path[i]->spare());
			}
			for (int i = E; i != S; i = pre[i]) {
				path[i]->addFlow(flow);
			}
			total += flow;
		}
		pfn1(total);
	}
}

exqt 4년 전 1

우선 98번 줄에 항상 Size만큼 초기화 하고 있어서 조금 비효율적인거 같습니다

근데 수정해도 시간초과가 발생하네요...

찾아보니 에드몬드카프로 푸신 분도 계시긴 하는데 E가 최대 1000*1000이라 많이 빡빡한듯 합니다

opop20207 4년 전 0

감사합니다 더 생각해봐야겠네요

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

문제

문제

출처

ICPC

9576) 에드몬드 카프 알고리즘으로 풀 수 없는 문제인가요?

opop20207 4년 전 1

exqt 4년 전 1

opop20207 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말