글 읽기 - 다른 예시 좀 알려주세요..ㅠㅠ

angela0102 6년 전 0

채점시, 31%까지 되다가 틀렸다고 나옵니다.

SPFA로 구현했습니다.

//왕복여행 2311
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct MCMF {
	struct Edge {
		int to, capacity, cost;
		Edge *rev;
		Edge(int to, int capacity, int cost) :to(to), capacity(capacity), cost(cost) {}
	};
	int n, source, sink;
	vector<vector<Edge *>> graph;
	vector<bool> check;
	vector<int> distance;
	vector<pair<int, int>> from;
	int inf = 10000000;
	MCMF(int n, int source, int sink) :n(n), source(source), sink(sink) {
		graph.resize(n);
		check.resize(n);
		distance.resize(n);
		from.resize(n, make_pair(-1, -1));
	};
	void add_edge(int u, int v, int cap, int cost) {
		Edge *ori = new Edge(v, cap, cost);
		Edge *rev = new Edge(u, 0, -cost);
		ori->rev = rev;
		rev->rev = ori;
		graph[u].push_back(ori);
		graph[v].push_back(rev);
	}
	void add_edge_from_source(int v, int cap, int cost) {
		add_edge(source, v, cap, cost);
	}
	void add_edge_to_sink(int u, int cap, int cost) {
		add_edge(u, sink, cap, cost);
	}
	bool spfa(int &total_flow, int &total_cost) {
		fill(check.begin(), check.end(), false);
		fill(distance.begin(), distance.end(), inf);
		fill(from.begin(), from.end(), make_pair(-1, -1));
		queue<int> q;
		q.push(source);
		distance[source] = 0;
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			check[x] = false;
			for (int i = 0; i < graph[x].size(); i++) {
				auto e = graph[x][i];
				int y = e->to;
				if (e->capacity > 0 && distance[y] > distance[x] + e->cost) {
					distance[y] = distance[x] + e->cost;
					from[y] = make_pair(x, i);
					if (!check[y]) {
						check[y] = true;
						q.push(y);
					}
				}
			}
		}
		if (distance[sink] == inf)
			return false;
		int x = sink;
		int c = graph[from[x].first][from[x].second]->capacity;
		while (from[x].first != -1) {
			if (c > graph[from[x].first][from[x].second]->capacity)
				c = graph[from[x].first][from[x].second]->capacity;
			x = from[x].first;
		}
		x = sink;
		while (from[x].first != -1) {
			Edge *e = graph[from[x].first][from[x].second];
			e->capacity -= c;
			e->rev->capacity += c;
			x = from[x].first;
		}
		total_flow += c;
		total_cost += c * distance[sink];
		return true;
	}
	pair<int, int> flow() {
		int total_flow = 0;
		int total_cost = 0;
		while (spfa(total_flow, total_cost));
		return make_pair(total_flow, total_cost);
	}
};
int main() {
	int n, m; //scanf("%d %d", &n, &m); 
	cin >> n >> m;
	MCMF mcmf(n + 2, 0, n + 1);
	for (int i = 0; i < m; i++) {
		int x, y, z; //scanf("%d %d %d", &x, &y, &z);
		cin >> x >> y >> z;
		mcmf.add_edge(x, y, 1, z);
		mcmf.add_edge(y, x, 1, z);
	}
	mcmf.add_edge_from_source(1, 2, 0);
	mcmf.add_edge_to_sink(n, 2, 0);
	//printf("%d\n", mcmf.flow().second);
	cout << mcmf.flow().second << '\n';
	return 0;
}

gaelim 6년 전 0

inf 값이 충분히 크지 않았습니다.

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

문제

문제

출처

ICPC

다른 예시 좀 알려주세요..ㅠㅠ

angela0102 6년 전 0

gaelim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말