生活随笔
收集整理的這篇文章主要介紹了
HUD - 4463 Outlets
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目鏈接
題意
N個商店最短修多長的路使得每個商店相連，其中apple和nike必須直接相連。
AC
#include <iostream>
#include <stdio.h>
#include <vector>
#include <map>
#include <string.h>
#define mem(a, b) memset(a, b, sizeof(a))
#define ll long long
#include <cmath>
#include <algorithm>
#define N 100005
#define P pair<int,int>
#define mk(a, b) make_pair(a, b)
int inf =
0x3f3f3f3f;
using namespace std;
struct ac{
double len;
int s, e;
}b[
3000];
struct point{
int x, y;
}a[
100];
int pre[
100];
void init() {
for(
int i =
0; i <
100; ++i) {pre[i] = i;}
}
int find(
int x) {
if (x != pre[x]) {
return pre[x] = find(pre[x]);}
return pre[x];
}
void join(
int x,
int y) {
if (x < y) pre[y] = x, find(y);
else pre[x] = y, find(x);
for (
int i =
0; i <
100; ++i) {find(i);}
}
int main(){
int nike, apple;
int n;
while (
scanf(
"%d", &n), n){
scanf(
"%d%d", &nike, &apple);
for (
int i =
0; i < n; ++i) {
scanf(
"%d%d", &a[i].x, &a[i].y);}init();
double ans =
0;
int now =
0;
for (
int i =
0; i < n; ++i) {
for (
int j = i +
1; j < n; ++j) {
double len =
sqrt((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y));b[now].s = i;b[now].e = j;b[now].len = len;
if (i == nike -
1 && j == apple -
1) {ans += b[now].len;join(i, j);}now++;}}sort(b, b + now, [&](
const ac &a,
const ac & b){
if ((a.len - b.len) >
1e-6) {
return 0;}
else {
return 1;}});
for (
int i =
0; i < now; ++i){
int s = b[i].s, e = b[i].e;
if (find(s) != find(e)) {join(find(s), find(e));ans += b[i].len;}}
printf(
"%.2lf\n", ans);}
return 0;
}
總結
以上是生活随笔為你收集整理的HUD - 4463 Outlets的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
