P2872 [USACO07DEC] Building Roads S
解题思路
- 这个是一个最小生成树,把在平面直角坐标系中的点定义为顶点,把两个点的距离定义为边
- 但这个题目并没有给出图中的边,也就是两个点的距离,因此我们要把这个图的边给补上,这个平面直角坐标系的点的每条边都是图上的边。
- 但因为题目给了必须要包含的边,那么我们需要处理这些边,那么怎么让这些边一定在最小生成树中就成为了一个问题,解决方法就是把它的边的权重赋值为0。
- 但这个题有浮点数的问题,以此把答案乘以一个大的数来解决,在最后输出答案的时候在除以那个大的数,以此来解决浮点数的精度问题
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 1001
typedef struct {
ll f;//从那个点
ll t;//到那个点
ll w;//边的权重
}p;
typedef p ELEMENT;
void quickSort(ELEMENT* a, int low, int high);
void swap(ELEMENT* a, int low, int high);//½»»»a[low]ºÍa[high]µÄÖµ
int* partition(ELEMENT* a, int low, int high, ELEMENT key);//°ÑaÖÐlowµ½highµÄÊý°´ÕÕkey·ÖÀ࣬СÓÚkeyµÄÔÚ×ó±ß£¬µÈÓÚkeyµÄÔÚÖм䣬´óÓÚkeyµÄÔÚÓÒ±ß
int n;//n个点
int m;//m条边
int f[N];//并查集
ll a[N][2];//存放点
p b[N * N];
int size;//数组b的大小
ll c[2];//用来读边
ll ans;//最后的答案,通过乘法来避免浮点数
int find(int x) {
if (x != f[x]) {
f[x] = find(f[x]);
}
return f[x];
}
bool isSameSet(int a, int b) {
return find(a) == find(b);
}
void unionSet(int a, int b) {
f[find(a)] = find(b);
}
ll d(ll x1, ll y1, ll x2, ll y2) {//计算两个点的距离
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) * 100000;//通过乘以100000,来避免浮点数,如果精度还不够就换一个更大的数
}
int main(int argc, char* argv[])
{
sc("%d%d", &n, &m);//读入点和边
//初始化并查集
for (int i = 1; i <= n; i++) {
f[i] = i;
}
//读入每个点的坐标
for (int i = 1; i <= n; i++) {
sc("%lld%lld", a[i], a[i] + 1);
}
//给每个两个点都给一条边
for (int i = 1; i < n; i++) {//因为是双向边,所以不用一直遍历同一个点,一共有Cn2条边
for (int j = i + 1; j <= n; j++) {
b[size].f = i;
b[size].t = j;
b[size].w = d(a[i][0], a[i][1], a[j][0], a[j][1]);
size++;
}
}
//把需要的边的权重赋值为0
for (int i = 0; i < m; i++) {
sc("%lld%lld", c, c + 1);
b[size].f = c[0];
b[size].t = c[1];
b[size].w = 0;
size++;
}
quickSort(b, 0, size - 1);//按照
int cnt = 0;
//最小生成树算法
for (int i = 0; i < size && cnt < n - 1; i++) {
if (!isSameSet(b[i].f, b[i].t)) {
ans += b[i].w;
unionSet(b[i].f, b[i].t);
cnt++;
}
}
//因为成了一个数,所以再除回去得到原本的答案
pr("%.2lf", ans / 100000.0);
return 0;
}
void quickSort(ELEMENT* a, int low, int high)
{
int* p = NULL;//´æ´¢µÈÓÚ»ù×¼ÖµµÄ×óÓұ߽ç
if (low >= high) {//Èç¹ûÖ»ÓÐÒ»¸öÖµ²»ÓÃÅÅÐò¾ÍÖ±½Ó½áÊøÅÅÐò
return;
}
p = partition(a, low, high, a[low + rand() % (high - low + 1)]);//pÖ¸ÏòµÈÓÚ»ù×¼ÖµÇø¼ä×óÓұ߽ç
quickSort(a, low, p[0] - 1);//Ö»ÅÅСÓÚ»ù×¼ÖµµÄ²¿·Ö
quickSort(a, p[1] + 1, high);//Ö»ÅÅ´óÓÚ»ù×¼ÖµµÄ²¿·Ö
free(p);//Êͷŵô¿ª±ÙµÄ¿Õ¼ä
}
void swap(ELEMENT* a, int low, int high)
{
ELEMENT t = { 0 };
t = a[low];
a[low] = a[high];
a[high] = t;
}
int* partition(ELEMENT* a, int low, int high, ELEMENT key)
{
int l = low;//´ú±íµÈÓÚkeyÇø¼äµÄ×ó±ß½ç,»òÕßÊÇСÓÚÇø¼äµÄÏÂÒ»¸öÊý
int r = high;//´ú±íµÈÓÚkeyÇø¼äµÄÓұ߽ç,»òÕßÊÇ´óÓÚÇø¼äµÄÏÂÒ»¸öÊý
int i = low;//´ÓÍ·¿ªÊ¼±éÀú
while (i <= r) {//ֻҪûÓе½´óÓÚÇø¼ä
if (a[i].w < key.w) {//ϱêiµÄÊýСÓÚ»ù×¼Öµ£¬·ÅÔÚ×ó±ß½çÀïÃæ
swap(a, l++, i++);//°Ñ×ó±ß½çµÄºóÒ»¸öÊýºÍϱêiµÄÖµ½»»»£¬È»ºó×óÇø¼äÀ©ÕÅ£¬È»ºóÈ¥¿´ÏÂÒ»¸öÊý
}
else if (a[i].w > key.w) {//ϱêiµÄÊý´óÓÚ»ù×¼Öµ£¬·ÅÔÚÓұ߽çÀïÃæ
swap(a, r--, i);//°ÑÓұ߽çµÄÇ°Ò»¸öÊýºÍϱêiµÄÖµ×ö½»»»£¬È»ºóÓÒÇø¼äÀ©ÕÅ£¬µ«i²»Äܶ¯£¬ÒòΪµ±Ç°iµÄÖµ»¹Ã»ÓзÃÎʹý
}
else {//ϱêiµÄÊýµÈÓÚ»ù×¼Öµ£¬·ÅÔÚ×óÓұ߽çÖ®¼ä
i++;//Ö±½Ó¼Ó1
}
}
int* p = (int*)malloc(sizeof(int) * 2);//´æ·ÅµÈÓÚÇø¼äµÄ×óÓұ߽ç
p[0] = l;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇl
p[1] = r;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇr
return p;//·µ»ØµÈÓÚkeyÇø¼äµÄ×óÓұ߽ç
}
P1991 无线通讯网
解题思路
- 这个题目需要我们把每个点到其他点的距离求出来,然后用最小生成树算法,和上面的题目边的构建是一样的
- 但这个题目的答案同样也要浮点数,因此我们用整数代替浮点数来进行转换,以此来避免精度问题
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 501
typedef struct {
ll f;
ll t;
ll w;
}po;
typedef po ELEMENT;
void quickSort(ELEMENT* a, int low, int high);
void swap(ELEMENT* a, int low, int high);//½»»»a[low]ºÍa[high]µÄÖµ
int* partition(ELEMENT* a, int low, int high, ELEMENT key);//°ÑaÖÐlowµ½highµÄÊý°´ÕÕkey·ÖÀ࣬СÓÚkeyµÄÔÚ×ó±ß£¬µÈÓÚkeyµÄÔÚÖм䣬´óÓÚkeyµÄÔÚÓÒ±ß
int s, p;//s是卫星电话的数量,p是边防哨所的数量
ll a[N][2];//存放每个边防哨所的数量
po b[N * N];//存放边
int size;//数组b的大小
int cnt;//选的边数
ll ans;//答案
int f[N];//并查集
int find(int x) {
if (x != f[x]) {
f[x] = find(f[x]);
}
return f[x];
}
bool isSameSet(int a, int b) {
return find(a) == find(b);
}
void unionSet(int a, int b) {
f[find(a)] = find(b);
}
//计算两点之间的距离
ll d(ll x1, ll x2, ll y1, ll y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) * 100000;//通过乘以一个数来避免浮点数问题
}
int main(int argc, char* argv[])
{
sc("%d%d", &s, &p);
//读入每个点的坐标
for (int i = 1; i <= p; i++) {
sc("%d%d", a[i], a[i] + 1);
}
for (int i = 1; i <= p; i++) {
f[i] = i;
}
//把每条边计算出来,因为是双向边,所以j = i + 1开始算,不然就会重复计算
for (int i = 1; i < p; i++) {
for (int j = i + 1; j <= p; j++) {
b[size].f = i;
b[size].t = j;
b[size].w = d(a[i][0], a[j][0], a[i][1], a[j][1]);
size++;
}
}
//按边的权重升序排序
quickSort(b, 0, size - 1);
//最小生成树算法,但要减去s + 1条边,因为s个卫星电话可以少一条边
for (int i = 0; i < size && cnt < p - 1 - s + 1; i++) {
if (!isSameSet(b[i].f, b[i].t)) {
if (b[i].w > ans) {
ans = b[i].w;
}
unionSet(b[i].t, b[i].f);
cnt++;
}
}
pr("%.2lf", ans / 100000.0);//因为之前乘了一个数所以再除以这个数得到原本的答案
return 0;
}
void quickSort(ELEMENT* a, int low, int high)
{
int* p = NULL;//´æ´¢µÈÓÚ»ù×¼ÖµµÄ×óÓұ߽ç
if (low >= high) {//Èç¹ûÖ»ÓÐÒ»¸öÖµ²»ÓÃÅÅÐò¾ÍÖ±½Ó½áÊøÅÅÐò
return;
}
p = partition(a, low, high, a[low + rand() % (high - low + 1)]);//pÖ¸ÏòµÈÓÚ»ù×¼ÖµÇø¼ä×óÓұ߽ç
quickSort(a, low, p[0] - 1);//Ö»ÅÅСÓÚ»ù×¼ÖµµÄ²¿·Ö
quickSort(a, p[1] + 1, high);//Ö»ÅÅ´óÓÚ»ù×¼ÖµµÄ²¿·Ö
free(p);//Êͷŵô¿ª±ÙµÄ¿Õ¼ä
}
void swap(ELEMENT* a, int low, int high)
{
ELEMENT t = { 0 };
t = a[low];
a[low] = a[high];
a[high] = t;
}
int* partition(ELEMENT* a, int low, int high, ELEMENT key)
{
int l = low;//´ú±íµÈÓÚkeyÇø¼äµÄ×ó±ß½ç,»òÕßÊÇСÓÚÇø¼äµÄÏÂÒ»¸öÊý
int r = high;//´ú±íµÈÓÚkeyÇø¼äµÄÓұ߽ç,»òÕßÊÇ´óÓÚÇø¼äµÄÏÂÒ»¸öÊý
int i = low;//´ÓÍ·¿ªÊ¼±éÀú
while (i <= r) {//ֻҪûÓе½´óÓÚÇø¼ä
if (a[i].w < key.w) {//ϱêiµÄÊýСÓÚ»ù×¼Öµ£¬·ÅÔÚ×ó±ß½çÀïÃæ
swap(a, l++, i++);//°Ñ×ó±ß½çµÄºóÒ»¸öÊýºÍϱêiµÄÖµ½»»»£¬È»ºó×óÇø¼äÀ©ÕÅ£¬È»ºóÈ¥¿´ÏÂÒ»¸öÊý
}
else if (a[i].w > key.w) {//ϱêiµÄÊý´óÓÚ»ù×¼Öµ£¬·ÅÔÚÓұ߽çÀïÃæ
swap(a, r--, i);//°ÑÓұ߽çµÄÇ°Ò»¸öÊýºÍϱêiµÄÖµ×ö½»»»£¬È»ºóÓÒÇø¼äÀ©ÕÅ£¬µ«i²»Äܶ¯£¬ÒòΪµ±Ç°iµÄÖµ»¹Ã»ÓзÃÎʹý
}
else {//ϱêiµÄÊýµÈÓÚ»ù×¼Öµ£¬·ÅÔÚ×óÓұ߽çÖ®¼ä
i++;//Ö±½Ó¼Ó1
}
}
int* p = (int*)malloc(sizeof(int) * 2);//´æ·ÅµÈÓÚÇø¼äµÄ×óÓұ߽ç
p[0] = l;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇl
p[1] = r;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇr
return p;//·µ»ØµÈÓÚkeyÇø¼äµÄ×óÓұ߽ç
}
标签:high,int,题解,ll,ELEMENT,2024,low,key From: https://www.cnblogs.com/lwj1239/p/18009241