글 읽기 - 1420) 최소 컷 조언 부탁드립니다.

opop20207 4년 전 0

최소 컷 풀이하는데 잘 안되네요.

13%에서 WA받습니다.

모든 index를 pair로 잡고 인접리스트 짰습니다.

상하좌우 돌면서 단방향 그래프 넣어주어서 다 돌면서 양방향 그래프 완성되도록 했습니다.

반례가 있을까요? 조언 부탁드립니다.

코드가 다소 난잡합니다만 양해 부탁드립니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
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(int x, int y, int N, int M) { return x >= 0 && x < N && y >= 0 && y < M; }
#define X first
#define Y second
#define pb push_back
const int SIZE = 110;
struct edge {
	pii to;
	int c, f;
	edge* dual;
	edge() : edge({0,0}, -1) {};
	edge(pii 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;
char map[SIZE][SIZE];
vector<edge*> adj[SIZE][SIZE];

int main() {
	scanf("%d %d", &N, &M);
	pii S, E;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf(" %1c", &map[i][j]);
			if (map[i][j] == 'K') S = { i,j };
			else if (map[i][j] == 'H') E = { i,j };
		}
	}
	for (int d = 0; d < 4; d++) {
		int x = S.X + dx[d];
		int y = S.Y + dy[d];
		if (cidx(x, y, N, M)) {
			if (map[x][y] == 'H') {
				printf("-1\n");
				return 0;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int d = 0; d < 4; d++) {
				int x = i + dx[d];
				int y = j + dy[d];
				if (cidx(x, y, N, M)) {
					if (map[x][y] != '#') {
						edge* e1 = new edge({ x,y }, 1);
						edge* e2 = new edge({ i,j }, 1);
						e1->dual = e2;
						e2->dual = e1;
						adj[i][j].pb(e1);
					}
				}
			}
		}
	}
	int total = 0;
	while (1) {
		pii prev[SIZE][SIZE];
		edge* path[SIZE][SIZE];
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				prev[i][j] = { -1,-1 };
			}
		}
		queue<pii> q;
		q.push(S);
		pii temp = { -1,-1 };
		while (!q.empty() && prev[E.X][E.Y] == temp) {
			pii curr = q.front();
			q.pop();
			for (auto e : adj[curr.X][curr.Y]) {
				pii next = e->to;
				if (e->spare() > 0 && prev[next.X][next.Y] == temp) {
					q.push(next);
					prev[next.X][next.Y] = curr;
					path[next.X][next.Y] = e;
					if (next == E)  break;
				}
			}
		}
		if (prev[E.X][E.Y] == temp) break;
		int flow = INF;
		for (pii i = E; i != S; i = prev[i.X][i.Y]) {
			flow = min(flow, path[i.X][i.Y]->spare());
		}
		for (pii i = E; i != S; i = prev[i.X][i.Y]) {
			path[i.X][i.Y]->addFlow(flow);
		}
		total += flow;
	}
	printf("%d\n", total);
}

exqt 4년 전 11

문제에서 요구하는 것은 칸(정점)을 막는것이고 컷은 간선을 막는 것을 의미합니다.

5 10
......#...
.....#....
..K.#..H..
..........
..#.......

opop20207 4년 전 0

덕분에 오류를 찾았습니다. 감사합니다.

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

문제

문제

출처

ICPC

1420) 최소 컷 조언 부탁드립니다.

opop20207 4년 전 0

exqt 4년 전 11

opop20207 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말