最小生成树(prim和Kruskal操!!SB题)
2024-10-07 12:42:42
Arctic Network
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 30571 | Accepted: 9220 |
Description
The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.
Any two outposts with a satellite channel can communicate via the
satellite, regardless of their location. Otherwise, two outposts can
communicate by radio only if the distance between them does not exceed
D, which depends of the power of the transceivers. Higher power yields
higher D but costs more. Due to purchasing and maintenance
considerations, the transceivers at the outposts must be identical; that
is, the value of D is the same for every pair of outposts.
Any two outposts with a satellite channel can communicate via the
satellite, regardless of their location. Otherwise, two outposts can
communicate by radio only if the distance between them does not exceed
D, which depends of the power of the transceivers. Higher power yields
higher D but costs more. Due to purchasing and maintenance
considerations, the transceivers at the outposts must be identical; that
is, the value of D is the same for every pair of outposts.
Your job is to determine the minimum D required for the
transceivers. There must be at least one communication path (direct or
indirect) between every pair of outposts.
Input
The
first line of input contains N, the number of test cases. The first
line of each test case contains 1 <= S <= 100, the number of
satellite channels, and S < P <= 500, the number of outposts. P
lines follow, giving the (x,y) coordinates of each outpost in km
(coordinates are integers between 0 and 10,000).
first line of input contains N, the number of test cases. The first
line of each test case contains 1 <= S <= 100, the number of
satellite channels, and S < P <= 500, the number of outposts. P
lines follow, giving the (x,y) coordinates of each outpost in km
(coordinates are integers between 0 and 10,000).
Output
For
each case, output should consist of a single line giving the minimum D
required to connect the network. Output should be specified to 2 decimal
points.
each case, output should consist of a single line giving the minimum D
required to connect the network. Output should be specified to 2 decimal
points.
Sample Input
1
2 4
0 100
0 300
0 600
150 750
Sample Output
212.13
Source
这个sb题要注意几点:第一是memset对double类型ma初始化为INF时会出现问题。
第二点:最后输出不知道为什么这个sb题得输出非得时%.2f,%.2lf就一直wa。。。。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
#include <map>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f3f3f
#define mod 1024
using namespace std;
typedef long long ll ;
int s , n ;
double ma[][];
double dis[] ;
double d[];
int vis[] ;
int ans ;
struct node{
double x , y ;
}a[]; void prim()
{
for(int i = ; i <= n ; i++)
{
dis[i] = ma[][i];
}
vis[] = ;
for(int i = ; i < n ; i++)
{
double min = INF ;
int pos ;
for(int j = ; j <= n ; j++)
{
if(!vis[j] && dis[j] < min)
{
min = dis[j];
pos = j ;
}
}
vis[pos] = ;
d[ans++] = min ;
for(int j = ; j <= n ; j++)
{
if(!vis[j] && dis[j] > ma[pos][j])
{
dis[j] = ma[pos][j];
}
}
}
} bool cmp(double a , double b)
{
return a > b ;
} void init()
{
memset(vis , , sizeof(vis));
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= n ; j++)
{
ma[i][j] = INF;
}
}
ans = ;
} int main()
{
int t ;
scanf("%d" , &t);
while(t--)
{
scanf("%d%d" , &s , &n);
init();
for(int i = ; i <= n ; i++)
{
scanf("%lf%lf" , &a[i].x , &a[i].y);
}
for(int i = ; i <= n ; i++)
{
for(int j = i + ; j <= n ; j++)
{
double w ;
w = sqrt((a[i].y - a[j].y) * (a[i].y - a[j].y) + (a[i].x - a[j].x)*(a[i].x - a[j].x)) ;
ma[i][j] = ma[j][i] = min(ma[i][j] , w);//这里if判断大小时,注意方向不要搞错了
}
}
prim();
sort(d , d + n - , cmp);
printf("%.2f\n" , d[s-]);
} return ;
}
Kruskal
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int fa[] , ans , n , m , way ;
double ds[] ; struct Node
{
int from , to ;
int x ;
int y ;
double d;
}a[]; bool cmp(const Node &a , const Node &b)
{
return a.d < b.d ;
} int gcd(int x)
{
if(x == fa[x])
return x ;
else
return gcd(fa[x]);
} void unite(int x , int y)
{
x = gcd(x) ; y = gcd(y) ;
if(x > y) fa[x] = y ;
else fa[y] = x ;
} void init()
{
for(int i = ; i <= m ; i++)
fa[i] = i ;
ans = ;
way = ;
memset(ds , , sizeof(ds));
}
bool cmp1(double a , double b)
{
return a > b ;
} int main()
{
int t ;
cin >> t ;
while(t--)
{
cin >> n >> m ;
init();
for(int i = ; i <= m ; i++)
{
cin >> a[i].x >> a[i].y ;
}
for(int i = ; i <= m ; i++)
{
for(int j = i + ; j <= m ; j++)
{
a[way].from = i ;
a[way].to = j ;
a[way].d = sqrt(pow((double)(a[i].x - a[j].x) , ) + pow((double)(a[i].y - a[j].y) , ));
way++; }
}
sort(a , a + way , cmp) ;
for(int i = ; i < way ; i++)
{
if( ans == m - )
break ;
if(gcd(fa[a[i].from]) != gcd(fa[a[i].to]))
{
unite(a[i].from , a[i].to);
ds[ans] = a[i].d;
ans ++ ;
}
}
sort(ds , ds + ans , cmp1);
printf("%.2f\n" , ds[n-]); } return ;
}
最新文章
- cookie (储存在用户本地终端上的数据)
- iOS---runtime介绍
- 01 选择 Help >; Install New Software,在出现的对话框里,点击Add按钮,在对话框的name一栏输入“ADT”,点击Archive...选择离线的ADT文件,contact all update ....千万不要勾选点击Add按钮,在对话框的name一栏输入“ADT”,点击Archive...选择离线的ADT文件,contact all update ....千万不要勾
- Bots(逆元,递推)
- grep 与正则表达式
- SQL Server中查询结果拼接遇到的小问题
- C# list使用方法
- 【BZOJ 1070】[SCOI2007]修车
- [置顶] mmog游戏开发之业务篇
- php开发中的url地址传输加密解密函数
- 多余的Using Namespaces或引用会影响程序的执行效率么?(转)
- Eclipse闪退解决办法
- S - stl 的mapⅠ
- shell脚本进阶之循环判断
- 轻松学习 JavaScript——第 6 部分:JavaScript 箭头函数
- RFID电动自行车与共享单车之物联网比较
- .net core+Spring Cloud学习之路 一
- Maven学习 八 采用Maven搭建SSM环境
- 会议室预订系统(meeting room booking system)
- JavaScript 教程 之基础教程