글 읽기 - 축사 배정 문제 질문드립니다.

a_bcde 2년 전 0

단순 이분 매칭을 구현한 풀이입니다.

제가 잘 짠 것이라면 답은 맞게 나올텐데, 이 코드는 시간 초과가 나버립니다.

개인적으로는 시간 초과가 날 만한 부분은 보이지 않는데, 혹시 코드가 잘못된 부분을 지적해주시거나 시간을 잡아먹는 부분을 찾아주실 수 있나요?

감사합니다.

#pragma GCC optimize("Ofast")
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
class graph {
	class edge;
	class vertex {
	public:
		vector<edge*> edges;
		void add_edge(vertex *const v) {
			auto const p = edge::make_edge(this, v);
			edges.push_back(p.first);
			v->edges.push_back(p.second);
		}
		[[nodiscard]] bool matched() const {
			for(auto const e : edges) {
				if(e->matched()) return true;
			}
			return false;
		}
	};
	class edge {
		[[maybe_unused]] vertex *const u;
		vertex *const v;
		edge *reverse;
		bool match;
		edge(vertex *u, vertex *v) : u(u), v(v), reverse(nullptr), match(false) {}
	public:
		static pair<edge*, edge*> make_edge(vertex *const u, vertex *const v) {
			auto const forward = new edge(u, v);
			auto const backward = new edge(v, u);
			forward->reverse = backward;
			backward->reverse = forward;
			return { forward, backward };
		}
		[[nodiscard]] vertex *next() const { return v; }
		[[nodiscard]] bool matched() const { return match; }
		void flip() { match = reverse->match = !match; }
	};
	int const n, m;
	vertex *const vertices;
public:
	graph(int n, int m) : n(n), m(m), vertices(new vertex[n + m]) {}
	void add_edge(int u, int v) { vertices[u].add_edge(vertices + n + v); }
	[[nodiscard]] int find() const {
		auto const visited = new bool[n + m]();
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			//if(vertices[i].matched()) continue;
			for(auto e : vertices[i].edges) {
				if(!dfs(e, visited)) continue;
				cnt++;
				break;
			}
		}
		delete[] visited;
		return cnt;
	}
	[[nodiscard]] bool dfs(edge *const e, bool *const visited) const {
		auto const v = e->next();
		visited[v - vertices] = true;
		if(e->matched()) {
			for(auto const nexte : v->edges) {
				if(visited[nexte->next() - vertices]) continue;
				if(dfs(nexte, visited)) {
					e->flip();
					visited[v - vertices] = false;
					return true;
				}
			}
			visited[v - vertices] = false;
			return false;
		}
		else {
			for(auto const nexte : v->edges) {
				if(nexte->matched()) {
					if(!visited[nexte->next() - vertices] && dfs(nexte, visited)) {
						e->flip();
						visited[v - vertices] = false;
						return true;
					}
					visited[v - vertices] = false;
					return false;
				}
			}
			e->flip();
			visited[v - vertices] = false;
			return true;
		}
	}
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m;
	cin >> n >> m;
	graph g(n, m);
	while(n--) {
		int k, x;
		cin >> k;
		while(k--) {
			cin >> x;
			g.add_edge(n, x - 1);
		}
	}
	cout << g.find();
}

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

문제

문제

출처

ICPC

축사 배정 문제 질문드립니다.

a_bcde 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말