글 읽기 - 접근방법이 어디가 잘못되었는지 모르겠습니다.

haz102 8년 전 0

K 부터 H 까지 모든 길을 연결한 후 최대 유량으로 탐색했는데요,

접근방법이 어디가 잘못되었는지 잘 모르겠습니다.

고수님들 도움 부탁드려요 ㅜㅜ

// https://www.acmicpc.net/problem/3692
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Edge
{
public:
	int u;
	int v;
	int capacity;
	int flow;
	Edge* reverse;

	inline int Left()
	{
		return capacity - flow;
	};

	inline void Flow(int amount)
	{
		flow += amount;
		reverse->flow -= amount;
	}; 
};

#define INF 987654321

vector< vector<Edge*> > adj;

inline void addEdge(int u, int v, int capacity)
{
	Edge* uv = new Edge();
	Edge* vu = new Edge();

	uv->u = u;
	uv->v = v;
	uv->capacity = capacity;
	uv->flow = 0;
	uv->reverse = vu;

	vu->u = v;
	vu->v = u;
	vu->capacity = 0;
	vu->flow = 0;
	vu->reverse = uv;

	adj[u].push_back(uv);
	adj[v].push_back(vu);
}

int networkFlow(int source, int sink, int V)
{
	int totalFlow = 0;
	vector<Edge*> parent(V);

	while (true)
	{
		for (int i = 0; i < V; i++)
		{
			parent[i] = NULL;
		}

		parent[source] = NULL;

		queue<int> q;
		q.push(source);

		while (q.empty() == false && parent[sink] == NULL)
		{
			int u = q.front(); q.pop();

			for (int i = 0; i < adj[u].size(); i++)
			{
				Edge* edge = adj[u][i];
				if (edge->Left() > 0 && parent[edge->v] == NULL)
				{
					parent[edge->v] = edge;
					q.push(edge->v);
				}
			}
		}

		if (parent[sink] == NULL)
		{
			break;
		}

		int amount = INF;
		Edge* p = parent[sink];
		while (p != NULL)
		{
			if (amount > p->Left())
			{
				amount = p->Left();
			}

			if (p->u == source)
			{
				break;
			}

			p = parent[p->u];
		}

		p = parent[sink];
		while (p != NULL)
		{
			p->Flow(amount);

			if (p->u == source)
			{
				break;
			}

			p = parent[p->u];
		}

		totalFlow += amount;
	}

	return totalFlow;
}

int N;
int M;

inline int XY(int x, int y)
{
	return y * M + x + 1;
}

inline int BXY(int x, int y)
{
	return N * M + XY(x, y);
}

int map[103][103];
inline int abs2(int v)
{
	return v < 0 ? -v : v;
}

void process()
{
	scanf("%d%d", &N, &M);

	int source = 0;
	int sink = 0;
	int V = N * M * 2 + 3;

	adj.clear();
	adj.resize(V);

	char buffer[103];
	int KX;
	int KY;
	int HX;
	int HY;

	for (int y = 0; y < N; y++)
	{
		scanf("%s", buffer);

		for (int x = 0; x < M; x++)
		{
			map[y][x] = buffer[x];

			if (buffer[x] == 'K')
			{
				KX = x;
				KY = y;

				source = XY(x, y);
			}
			else if (buffer[x] == 'H')
			{
				HX = x;
				HY = y;
				sink = XY(x, y);
			}

			addEdge(XY(x, y), BXY(x, y), INF);
		}
	}

	if (abs2(KX - HX) + abs2(KY - HY) <= 1)
	{
		printf("-1\n");
		return;
	}

	const int dir[4][2] = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
	int k = 0;

	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			if (map[y][x] == '.' || map[y][x] == 'K')
			{
				for (int i = 0; i < 4; i++)
				{
					int tx = x + dir[i][0];
					int ty = y + dir[i][1];

					if (tx >= 0 && tx < M && ty >= 0 && ty < N && (map[ty][tx] == '.' || map[ty][tx] == 'H'))
					{
						k++;
						addEdge(BXY(x, y), XY(tx, ty), 1);
					}
				}
			}
		}
	}

	int ret = networkFlow(source, sink, V);
	printf("%d\n", ret);
}

int main(void)
{
	process();
	return 0;
}

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

문제

문제

출처

ICPC

접근방법이 어디가 잘못되었는지 모르겠습니다.

haz102 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말