글 읽기 - 1348번 주차장 문제 질문드립니다.

victory277 7년 전 0

bfs로 각 자동차('C')에 대해 주차공간('P')을 탐색해,

(1의 용량)과 (자동차에서 주차공간까지의 거리)를 가지는 간선으로 이분그래프를 만들어 주었고

bound를 던져줘서 bound보다 작거나 같은 거리(dis)를 가지는 간선으로만 진행하도록 해서

구한 유량을 자동차 개수와 비교하는 이분탐색으로 출력값을 결정했습니다.

혹시 틀린 예가 있다면 알려주시면 감사하겠습니다.

#include <iostream>
using namespace std;

#define MAXV 210
#define INF 0xfffffff
#define Min(a,b) (a<b)?a:b

char cmap[51][51];
int N, M;
int C, P;
int map[51][51];
int sp[101][2];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int Maxv = 0;

struct Point {
	int x, y, c;
};

Point q[2500];
bool gr[MAXV][MAXV];
int cap[MAXV][MAXV];
int res[MAXV][MAXV];
int dis[MAXV][MAXV];
int level[MAXV];
int iter[MAXV];
int que[MAXV * 2];

void add_Edge(int from, int to, int d) {
	gr[from][to] = 1;
	dis[from][to] = d;
}

void bfs_Flow(int st, int end, int bound) {
	for (int i = 0; i <= end; i++) {
		level[i] = -1;
	}

	int fr = -1, re = -1;

	que[++re] = st;
	level[st] = 0;

	while (fr != re) {
		int v = que[++fr];

		for (int i = 0; i <= end; i++) {
			if (gr[v][i] && (cap[v][i] - res[v][i]) > 0 && level[i] < 0 && dis[v][i] <= bound) {
				level[i] = level[v] + 1;
				que[++re] = i;
			}
		}
	}
}

int dfs_Flow(int v, int end, int f) {
	if (v == end) return f;

	for (int &i = iter[v]; i <= end; i++) {
		if (cap[v][i] - res[v][i] > 0 && level[i] > level[v]) {
			int d = dfs_Flow(i, end, Min(cap[v][i] - res[v][i], f));

			if (d > 0) {
				res[v][i] += d;
				return d;
			}
		}
	}

	return 0;
}

int Max_Flow(int st, int end, int bound) {
	for (int i = 0; i <= end; i++) {
		for (int j = 0; j <= end; j++) {
			cap[i][j] = gr[i][j];
			res[i][j] = 0;
		}
	}

	int flow = 0;

	while (1) {
		bfs_Flow(st, end, bound);
		if (level[end] < 0) return flow;

		for (int i = 0; i <= end; i++) {
			iter[i] = 0;
		}
		int f;

		while ((f = dfs_Flow(st, end, INF)) > 0) {
			flow += f;
		}
	}
}

int BinarySearch() {
	int low = 0, high = 101 * 2;
	int mid = Maxv;
	int car;
	int last = Maxv;

	int st = 0, end = C + P + 1;

	//cout << low << " " << high << " " << mid << endl;

	while (low <= high) {
		mid = (low + high) / 2;

		car = Max_Flow(st, end, mid);

		/*
		cout << endl;
		for (int i = 0; i <= end; i++) {
			for (int j = 0; j <= end; j++) {
				cout << res[i][j] << " ";
			}
			cout << endl;
		}
		*/
		//cout << mid << " " << car << endl;

		if (car == C) {
			high = mid - 1;
			last = mid;
		}
		else {
			low = mid + 1;
		}

		//cout << low << " " << high << " " << mid << endl;
	}

	return last;
}

bool inRange(int x, int y) {
	if (x < 0 || x >= M || y < 0 || y >= N) return false;
	return true;
}

bool bfs_Graph(int sx, int sy) {
	bool check[51][51] = { 0, };

	int fr = -1, re = -1;
	int tx, ty;
	Point now;

	int cnt = 0;

	q[++re] = { sx, sy, 0 };
	check[sy][sx] = true;

	while (fr != re) {
		now = q[++fr];

		for (int i = 0; i < 4; i++) {
			tx = now.x + dx[i];
			ty = now.y + dy[i];

			if (inRange(tx, ty) && !check[ty][tx]) {
				if (map[ty][tx] >= 0) {
					if (map[ty][tx] > C && map[ty][tx] <= C + P) {
						cnt++;
						add_Edge(map[sy][sx], map[ty][tx], now.c + 1);
						if (now.c + 1 > Maxv) Maxv = now.c + 1;
					}

					q[++re] = { tx, ty, now.c + 1 };
					check[ty][tx] = true;
				}
			}
		}
	}

	if (cnt == 0) return false;

	return true;
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> cmap[i][j];

			if (cmap[i][j] == 'C') {
				C++;
				map[i][j] = C;
				sp[C][0] = j;
				sp[C][1] = i;
			}
			else if (cmap[i][j] == 'X') {
				map[i][j] = -1;
			}
		}
		cin.ignore();
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (cmap[i][j] == 'P') {
				P++;
				map[i][j] = C + P;
			}
		}
	}

	if (C > P) {
		cout << -1;
		return 0;
	}

	int st = 0, end = C + P + 1;
		
	for (int i = 1; i <= C; i++) {
		add_Edge(st, i, 0);
		if (!bfs_Graph(sp[i][0], sp[i][1])) {
			cout << -1;
			return 0;
		}
	}
	for (int i = C + 1; i <= C + P; i++) {
		add_Edge(i, end, 0);
	}

	cout << BinarySearch();

	getchar();
	getchar();

	return 0;
}

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

문제

문제

출처

ICPC

1348번 주차장 문제 질문드립니다.

victory277 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말