Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

实在不知道我是为什么WA了。。

Posted by ydong17 at 2020-03-31 16:43:27 on Problem 2349
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<climits>
#include<cstring>

using namespace std;
int N, S, P;

const int INF = INT_MAX;
const int maxp = 500 + 5;
double x[maxp];
double y[maxp];//坐标 有计算距离操作的话,最好采用double 
double w[maxp][maxp];//坐标从1开始,邻接矩阵
bool mstSet[maxp];
double Key[maxp];
int parent[maxp];

double dist(int x1, int y1, int x2, int y2) {
	double d = sqrt(pow((x1-x2),2)/1.00+pow((y1-y2),2)/1.00);
	return d;
}

int minKey(double Key[], bool mstSet[]) {
	int min_idx = 0, Min = INF;
	for (int u = 1; u <= P; u++) {
		if (!mstSet[u] && Key[u] < Min) {
			Min = Key[u];
			min_idx = u;
		}
	}
	return min_idx;
}

bool cmp(double x, double y) {
	if (x < y)return false;
	else return true;
}

int main() {
	freopen("data_try.txt", "r", stdin);
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d%d", &S, &P);
		
		//构造邻接矩阵
		for (int k = 1; k <= P; k++) {
			scanf("%lf%lf", &x[k], &y[k]);
			//和前面所有人算一次距离
			for (int j = 1; j <=k; j++) {
				if (j == k)w[j][k] = 0;
				else w[k][j]=w[j][k]=dist(x[j], y[j], x[k], y[k]);//邻接矩阵,权重计算完毕
			}
		}
		//prim算法
		memset(mstSet, false, sizeof(mstSet));
		for (int j = 1; j <= P; j++) {
			Key[j] = INF;
		}
		Key[1] = 0;//X集合里面,有了第1个点
		parent[1] = -1;

		double sum = 0;

		for (int i = 1; i <= P; i++) { 
			//要让mstSet包含一个点
			int u = minKey(Key, mstSet);
			mstSet[u] = true;
			sum += Key[u];

			for (int j = 1; j <= P; j++) {
				if (!mstSet[j] && w[i][j] && w[i][j] < Key[j]) {
					Key[j] = w[i][j], parent[j] = i;
				}
			}
		}

		//现在把最小生成树的所有边弄到el里面去
		vector<double> el;//edge length
		for (int i = 1; i <= P; i++) {
			if (mstSet[i]) {

				if (parent[i] != -1) {
					int j = parent[i];
					el.push_back(w[i][j]);
				}
			}
		}
		int num=el.size();
		sort(el.begin(), el.end(), cmp);
		printf("%.2f\n", el[S-1]);

	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator