글 읽기 - 단순한 왕복 문제가 아닌가요?

dsa2341 4년 전 0

2311번이랑 똑같이 생각해서 풀었습니다만 틀렸다고 나오는데 무엇이 문제인지 모르겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#define INF	987654321	
using namespace std;
vector<int>adj[2002];
int c[2002][2002], f[2002][2002], d[2002][2002];
int n, m;
void addEdge(int u, int v, int cap, int val) {
	adj[u].push_back(v);
	adj[v].push_back(u);
	c[u][v] = cap;
	d[u][v] = val;
	d[v][u] = -val;
}
int main() {
	cin >> n >> m;
	int S = 1, E = n * 2, total = 0;
	for (int i = 1; i <= n; ++i)
		addEdge(i * 2 - 1, i * 2, 2, 0);
	for (int i = 0; i < m; ++i) {
		int x, y, z;
		cin >> x >> y >> z;
		addEdge(x * 2, y * 2 - 1, 1, z);
		addEdge(y * 2, x * 2 - 1, 1, z);
	}
	while (1) {
		vector<int>prev(E + 1, -1);
		vector<int>dist(E + 1, INF);
		vector<bool>inq(E + 1, false);
		queue<int> q;
		q.push(S); dist[S] = 0; inq[S] = 1;
		while (!q.empty()) {
			int here = q.front(); q.pop();
			inq[here] = 0;
			for(int next : adj[here])
				if (c[here][next] - f[here][next] > 0 && dist[next] > dist[here] + d[here][next]) {
					dist[next] = dist[here] + d[here][next];
					prev[next] = here;
					if (!inq[next]) q.push(next), inq[next] = 1;
				}
		}
		if (prev[E] == -1) break;
		for (int p = E; p != S; p = prev[p]) {
			f[prev[p]][p]++;
			f[p][prev[p]]--;
			total += d[prev[p]][p];
		}
	}
	cout << total;
	return 0;
}

sait2000 4년 전 0

정점 쌍에 대해 간선이 최대 하나만 있다는 조건이 없는 것 같은데요.

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

문제

문제

출처

ICPC

단순한 왕복 문제가 아닌가요?

dsa2341 4년 전 0

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말