글 읽기 - 1671 질문입니다

chatterboy 8년 전 0

살아남는 상어의 최소값 = 전체 상어의 수 - 먹히는 상어의 최대값 이라 하고

먹히는 상어의 최대값을 유량문제로 풀었습니다.

source -> 2번...N+1번 까지는 각 상어가 먹을 수 있는 양을 간선으로 표현했습니다. (capacity=2)

2번...N+1번 -> N+2번...2N+1번 까지는 상어 A가 상어 B를 먹을 수 있다면 간선을 그어주는 방식을 사용했습니다. (capacity=1)

N+2번...2N+1번 -> 1번 까지는 상어가 먹힌 여부를 간선으로 표현했습니다. (capacity=1)

무엇을 잘못했나요ㅠ?

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1e9
#define MAXN 2222
int N, sz[MAXN], v[MAXN], it[MAXN];
int capacity[MAXN][MAXN], flow[MAXN][MAXN];
int admondsKarp(int src, int sink) {
	int ret = 0;
	while (1) {
		vector<int> parent(N, -1);
		queue<int> q;
		parent[src] = src;
		q.push(src);
		while (parent[sink] == -1 && !q.empty()) {
			int u = q.front();
			q.pop();
			for (int v = 0; v < N; v++)
				if (capacity[u][v] - flow[u][v] > 0 && parent[v] == -1) {
					parent[v] = u;
					q.push(v);
				}
		}
		if (parent[sink] == -1) break;
		int mins = INF;
		for (int u = sink; u != src; u = parent[u])
			mins = min(mins, capacity[parent[u]][u] - flow[parent[u]][u]);
		ret += mins;
		for (int u = sink; u != src; u = parent[u]) {
			flow[parent[u]][u] += mins;
			flow[u][parent[u]] -= mins;
		}
	}
	return ret;
}
int main() {
	scanf("%d", &N);
	for (int i=0; i<N; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		sz[i]=a, v[i]=b, it[i]=c;
	}
	// make graph
	for (int j=2; j<=N+1; ++j) capacity[0][j] = 2;
	for (int i=N+2; i<=2*N+1; ++i) capacity[i][1] = 1;
	for (int i=1; i<=N; ++i)
		for (int j=1; j<=N; ++j)
			if (i!=j && sz[i]>=sz[j] && v[i]>=v[j] && it[i]>=it[j]) { // 상어 i가 상어 j를 먹을 수 있다면
				capacity[i+1][j+N+1] = 1;
			}
	int tot = N;
	N = 2*N+2;
	printf("%d", tot-admondsKarp(0, 1));
}

nisroeld99 7년 전 1

빼먹으신 조건이

3가지 조건이 모두 같은 상어들의 경우에는

서로 잡아먹어버리므로

1명의 상어만 잡아먹을 수있게끔 처리해줘야합니다

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

문제

문제

출처

ICPC

1671 질문입니다

chatterboy 8년 전 0

nisroeld99 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말