[BOJ] 11111 두부장수 장홍준2

(2021년 1월 24일에 작성한 글입니다.)

 

11111번: 두부장수 장홍준 2

 

-price를 cost 값으로 넣고 MCMF를 돌린 후에

답은 -price를 출력하면 된다.

처음에는 source -> (i + j)가 짝수인 곳 -> 인접한 곳 -> sink

이런 방식으로 했는데 예제가 계속 36이 나왔다.

그래서 인터넷에 있는 코드 찾아보니까

모든 노드에서 sink로 capacity 1, cost 0인 간선을 만들어줘야 했다.

처음에는 (i + j)가 짝수인 곳에서 인접한 (i + j)가 홀수인 곳으로 간선이 연결되어 있으니까

(i + j)가 홀수인 곳에서만 sink로 연결해주면 되는 줄 알았다.

그런데 그렇지 않다!

모든 칸은 한 칸짜리 두부로 버려질 가능성이 있기 때문에

sink로 capacity 1, cost 0인 간선을 연결해줘야 한다.

한참 고민하다가 알게 된건데

진짜... 대박적이다​

역시

신기가 방기다

 

using Type = int;
struct Edge {
	int from, to;
	Type capacity, flow, cost;
	Edge* reverseEdge;

	Edge(int from_in, int to_in, Type capacity_in, Type cost_in) {
		from = from_in; to = to_in; capacity = capacity_in; cost = cost_in; flow = 0;
	}

	void AddFlow(Type newFlow) {
		flow += newFlow;
		reverseEdge->flow -= newFlow;
	}

	Type Residual() {
		return capacity - flow;
	}
};

struct MaxFlow {
	int V; //vertex 개수
	int source, sink;
	vector<vector<Edge*>> adj;
	vector<Type> dist;
	Type totalFlow = 0, totalCost = 0;

	MaxFlow(int v) {
		V = v; adj.resize(V + 5);
	}

	void AddEdge(int from, int to, Type capacity, Type cost, bool isDirected) {
		Edge* e1 = new Edge(from, to, capacity, cost);
		Edge* e2 = new Edge(to, from, isDirected ? 0 : capacity, isDirected ? -cost : cost);
		e1->reverseEdge = e2;
		e2->reverseEdge = e1;
		adj[from].push_back(e1);
		adj[to].push_back(e2);
	}

	bool GetPossibleFlow(vector<int>& prev, vector<Edge*>& backEdge) {
		prev.clear(); prev.resize(V + 5, -1);
		backEdge.clear(); backEdge.resize(V + 5, NULL);
		dist.clear(); dist.resize(V + 5, INT_MAX); //여기
		queue<int> que;
		vector<bool> inQue(V + 5, false);

		dist[source] = 0;
		que.push(source); inQue[source] = true;

		while (!que.empty()) {
			int cur = que.front();
			que.pop(); inQue[cur] = false;

			for (Edge* edge : adj[cur]) {
				int next = edge->to;
				if (edge->Residual() > 0 && dist[next] > dist[cur] + edge->cost) {
					dist[next] = dist[cur] + edge->cost;
					prev[next] = cur;
					backEdge[next] = edge;
					if (!inQue[next]) {
						que.push(next);
						inQue[next] = true;
					}
				}
			}
		}

		return prev[sink] != -1;
	}

	void MCMF() {
		vector<int> prev; vector<Edge*> backEdge;
		totalFlow = 0;

		while (GetPossibleFlow(prev, backEdge)) {
			Type newFlow = 2e9; //여기
			for (int cur = sink; cur != source; cur = prev[cur]) {
				newFlow = min(newFlow, backEdge[cur]->Residual());
			}
			for (int cur = sink; cur != source; cur = prev[cur]) {
				totalCost += newFlow * backEdge[cur]->cost;
				backEdge[cur]->AddFlow(newFlow);
			}
			totalFlow += newFlow;
		}
	}
};

int GetPrice(char, char);
int GetNumber(int, int);
int N, M;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int diry[4] = { -1, 1, 0, 0 }, dirx[4] = { 0, 0, -1, 1 };

	cin >> N >> M;
	vector<vector<char>> arr(N + 5, vector<char>(M + 5, 0));

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> arr[i][j];
		}
	}

	MaxFlow maxFlow(N * M + 5);
	maxFlow.source = 0; maxFlow.sink = N * M + 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if ((i + j) % 2 == 0) {
				maxFlow.AddEdge(maxFlow.source, GetNumber(i, j), 1, 0, true);
				for (int k = 0; k < 4; k++) {
					int ii = i + diry[k], jj = j + dirx[k];
					int price = GetPrice(arr[i][j], arr[ii][jj]);
					if (price != -1) {
						maxFlow.AddEdge(GetNumber(i, j), GetNumber(ii, jj), 1, -price, true);
					}
				}
			}
			maxFlow.AddEdge(GetNumber(i, j), maxFlow.sink, 1, 0, true);
		}
	}

	maxFlow.MCMF();
	cout << -maxFlow.totalCost << ENDL;

	return 0;
}

int GetPrice(char a, char b)
{
	if (a == 0 || b == 0) {
		return -1;
	}

	vector<vector<int>> price
	{ {10, 8, 7, 5, 0, 1},
	{8, 6, 4, 3, 0, 1},
	{7, 4, 3, 2, 0, 1},
	{5, 3, 2, 2, 0, 1},
	{},
	{1, 1, 1, 1, 0, 0} };

	return price[a - 'A'][b - 'A'];
}

int GetNumber(int y, int x)
{
	return (y - 1) * M + x;
}