글 읽기 - 1006 습격자 초라기 질문입니다.

chiller123 9년 전 1

1006번 원본 출처에 있는 TJU Online Judge에서는 Accept 판정을 받은 코드입니다.

두 곳에 투입시킬 부대를 Bipartite Matching를 사용해서 구했구요.

데이터가 문제가 있는 것인지, 아니면 제 코드에 실수가 있는것인지 잘 모르겠네요.

N==1인 경우만 직접 구하는 예외를 두었습니다.

#include <cstdio>
#include <vector>
using namespace std;

int T, N, W;
int area[2][10000];
vector<vector<int> > adj;
vector<int> bMatch;
vector<bool> visited;

bool dfs(int now){
	if (visited[now]) return false;
	visited[now] = true;
	for (int i = 0; i < adj[now].size(); i++){
		int next = adj[now][i];
		if (bMatch[next] == -1 || dfs(bMatch[next])){
			bMatch[next] = now;
			return true;
		}
	}
	return false;
}

int bipartiteMatch(){
	bMatch.assign(2 * N, -1);
	int sz = 0;
	for (int i = 0; i < 2 * N; i++){
		visited.assign(2 * N, false);
		if (dfs(i)) sz++;

	}
	return sz;
}

int main(){
	int t; scanf("%d", &t);
	while (t--){
		scanf("%d%d", &N, &W);
		if (N == 1){
			int a, b; scanf("%d%d", &a, &b);
			printf("%d\n", a + b <= W ? 1 : 2);
			continue;
		}
		int pos[3][2] = { { 0, -1 + N }, { 0, 1 }, { 1, 0 } };
		for (int i = 0; i < 2; i++){
			for (int j = 0; j < N; j++){
				scanf("%d", &area[i][j]);
			}
		}
		adj.clear(); adj.resize(2 * N);
		for (int i = 0; i < 2; i++){
			for (int j = 0; j < N; j++){
				for (int k = 0; k < 3; k++){
					int p1 = (i + pos[k][0]) % 2, p2 = (j + pos[k][1]) % N;
					if (area[i][j] + area[p1][p2] <= W)
						adj[i*N + j].push_back(p1*N + p2);
				}
			}
		}
		int twoMatch = bipartiteMatch();
		printf("%d\n", 2 * N - twoMatch + twoMatch / 2);
	}
	return 0;
}

baekjoon 9년 전 0

원래 문제랑 조금 다르지 않나요? 제 기억엔 그랬던거 같은데

chiller123 9년 전 0

인풋 형식만 다를뿐 같은 문제 아닌가요?

BOJ : test case 횟수

TJU : 0 0이 들어올 때 까지.

chiller123 9년 전 0

TJU의 Input은 허술한 면이 많았었나봅니다. 반례를 발견했네요.

작성한 알고리즘으로 풀기에는 무리가 있었나봅니다.

chiller123 9년 전 2

TJU는 짝수라는 전제조건이 있었네요 이런 -_-

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

문제

문제

출처

ICPC

1006 습격자 초라기 질문입니다.

chiller123 9년 전 1

baekjoon 9년 전 0

chiller123 9년 전 0

chiller123 9년 전 0

chiller123 9년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말