글 읽기 - 거리를 구해 매칭 하였습니다. 반례가 있을까요??

nakgee 4년 전 1

거리를 구해서 쥐가 갈 수 있는 곳을 구해준 후

매칭을 해주었는데 반례가 있는 것 같은데

논리의 문제나 예외케이스가 있으면 도와주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define N 110


int n, m;
double s, v;
vector<int> vec[N];
typedef pair<double, double> pdd;
vector<pdd> ar, br;
bool chk[N];
int hall[N];

double dis(double x1,double y1,double x2,double y2) {
	double y = y2 - y1;
	double x = x2 - x1;
	return x*x + y*y;
}


bool dfs(int now) {
	if (chk[now])return false;
	chk[now] = true;
	for (int go : vec[now]) {
		if (hall[go]== -1 || dfs(hall[go])) {
			hall[go] = now;
			return true;
		}
	}
	return false;
}
int main() {
	cin >> n >> m >> s >> v;

	for (int i = 1; i <= n; i++) {
		double x, y;
		cin >> x >> y;
		ar.push_back(pdd(x, y));
	}
	for (int j = 1; j <= m; j++) {
		double x, y;
		cin >> x >> y;
		br.push_back(pdd(x, y));
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			double d = dis(ar[i].first, ar[i].second, br[j].first, br[j].second);
			if ((v*s)*(v*s) >= d) {
				vec[i].push_back(j);
			}
		}
		hall[i] = -1;
	}

	int res = n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) chk[j] = false;
		res -= dfs(i);
	}
	cout << res;
	return 0;
}

nakgee 4년 전 0

그래프를 1번부터로 바꾸니까 맞았는데 왜 그런지 모르겠습니다

yjyj1027 3년 전 0

올려주신 코드로 보면 쥐의 인덱스를

40~49line 에서는 1~n 로,

51~65line에서는 0~n-1로 처리하신 것으로 보입니다.

nakgee 3년 전 0

그부분은 위에서는 i, j 를 사용하지 않고 벡터에만 입력 하는 것이라 문제가 없어보입니다..

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

문제

문제

출처

ICPC

거리를 구해 매칭 하였습니다. 반례가 있을까요??

nakgee 4년 전 1

nakgee 4년 전 0

yjyj1027 3년 전 0

nakgee 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말