poj 1789 kruscal 물 문제

1908 단어 C++ACM
계속 물 문제...
제목:http://poj.org/problem?id=1789
차 를 결점 으로 보고 차 사이 의 거 리 를 가중치 로 보 는 것 은 하나의 그림 이다.그리고 최소 생 성 나 무 를 구한다.
물 문 제 는 맞 는데 문 제 를 보 는 데 시간 이 오래 걸 려 서 현장에서 이런 문 제 를 만나면 얼마나 아 플 지 모 르 겠 어 요.
이 문제 의 시한 은 2000 ms 이지 만 kruscal+sort 로 wa 를 썼 습 니 다.qsort 로 바 꾸 면 과감하게 시간 을 초 과 했 습 니 다.인터넷 의 문 제 를 뒤 져 보 니 const void*로 인 자 를 입력 해 야 빠 를 것 같 습 니 다.
수정 하고 또 와 를 발 견 했 습 니 다.그리고 gdb 를 한 번 조정 한 결과 출력 을 잊 어 버 렸 습 니 다.............................................어이 없어...
어,나중에 sort 1200+ms,qsort 600+ms...
코드 붙 이기(qsort):
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2001;
//poj1789


struct Edge{
	int x, y, v;
};
struct Edge e[maxn*maxn];
int f[maxn];

void init(int n) {
	for (int i = 0; i < n; i++)
		f[i] = i;
}

int find(int x) {
	if (f[x] != x)
		return f[x] = find(f[x]);
	return x;
}

int chcmp(const char* a, const char * b) {
	int cnt = 0;
	for (int i = 0; i < 7; i++)
		if (a[i] != b[i])
			cnt++;
	return cnt;
}

int cmp(const void * a, const void * b){
	return (*(struct Edge *)a).v - (*(struct Edge *)b).v;
}

int main() {
	int n;
	int i, j, cnt, shortest, select;
	char str[maxn][7], tmp[7];
//	freopen ("in", "r", stdin);
	while (scanf("%d", &n) && n) {
		init(n);
		gets(str[0]);
		for (i = 0; i < n; i++)
			gets(str[i]);
		cnt = 0;
		for (i = 0; i < n; i++)
			for (j = i + 1; j < n; j++) {
				e[cnt].x = i;
				e[cnt].y = j;
				e[cnt].v = chcmp(str[i], str[j]);
				cnt++;
			}
		qsort(e, cnt, sizeof(e[0]), cmp);
		shortest = 0;
		select = 0;
		for (i = 0; i < cnt; i++) {
			int a, b;
			a = find(e[i].x);
			b = find(e[i].y);
			if (a != b){
				f[a] = b;
				shortest += e[i].v;
				if (++select == n - 1)
					break;
			}
		}
		printf("The highest possible quality is 1/%d.
", shortest); } return 0; }

prim

좋은 웹페이지 즐겨찾기