글 읽기 - 이 조건은 왜 틀린지 봐주실 수 있나요?

dsa2341 4년 전 0

3능력치가 모두 같을 때 서로 잡아 먹는 것을 막기 위해서 주석 처리한 부분처럼 하면 틀리는데 이유를 알 수 있을까요?

주석처리한 부분은 서로 i, j 를 바꿨을때 이미 간선이 그어져 있는 경우를 표현한 것입니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int capacity[102][102], flow[102][102];
struct shark {
	int a, b, c;
};
vector<shark>adj;
int main() {
	int n, S, E, ans = 0;
	cin >> n;
	S = 0, E = 2 * n + 1;
	for (int i = 0; i < n; ++i) {
		shark sk;
		cin >> sk.a >> sk.b >> sk.c;
		adj.push_back(sk);
		capacity[S][i + 1] = 2;
	}
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			if (i == j) continue;
			if ((adj[i].a >= adj[j].a) && (adj[i].b >= adj[j].b) && (adj[i].c >= adj[j].c)) {
				if ((adj[i].a == adj[j].a) && (adj[i].b == adj[j].b) && (adj[i].c == adj[j].c)) {
					if (i<j) { // 	if (capacity[j + 1][i + n + 1] == 0) {
						capacity[i + 1][n + j + 1] = 1;
						capacity[n + j + 1][E] = 1;
					}
				}
				else {
					capacity[i + 1][n + j + 1] = 1;
					capacity[n + j + 1][E] = 1;
				}
			}
		}
	while (1) {
		queue<int> q;
		q.push(S);
		vector<int>parent(E + 1, -1);
		parent[S] = S;
		while (!q.empty() && parent[E] == -1) {
			int here = q.front();
			q.pop();
			for (int i = S; i <= E; ++i)
				if (capacity[here][i] - flow[here][i] > 0 && parent[i] == -1) {
					q.push(i);
					parent[i] = here;
				}
		}
		if (parent[E] == -1) break;
		++ans;
		for (int p = E; p != S; p = parent[p]) {
			flow[parent[p]][p]++;
			flow[p][parent[p]]--;
		}
	}
	cout << n - ans;
	return 0;
}

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

문제

문제

출처

ICPC

이 조건은 왜 틀린지 봐주실 수 있나요?

dsa2341 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말