题意简单:去掉最小生成树的某一条边并补上一条,求MaxVal
思路:贪心(借鉴Yamidie的思路。。。)
分别求出最小生成树和次最小生成树,再在这两棵树上求最小生成树
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn = 1015;
const int maxm = maxn*maxn;
const int inf1 = 0x3f3f3f3f;
const double inf2 = 9999999999;
struct Point {
double x,y;
}pnt[ maxn ];
struct Edge{
int u,v;
double val;
int id;
}edge[ maxn<<1 ];
int cnt_edge;
double mat[ maxn ][ maxn ];
double dis[ maxn ];
bool vis[ maxn ];
int pre[ maxn ];
double LenPrim1;
double LenPrim2;
int fa[ maxn ],rank[ maxn ];
int find( int x ){
if( x==fa[x] ) return x;
else return fa[ x ] = find( fa[x] );
}
void init( int n ){
for( int i=0;i<n;i++ ){
fa[ i ] = i;
rank[ i ] = 1;
}
return ;
}
double dist( int i,int j ){
return sqrt( (pnt[i].x-pnt[j].x)*(pnt[i].x-pnt[j].x)+(pnt[i].y-pnt[j].y)*(pnt[i].y-pnt[j].y) );
}
int cmp( Edge a,Edge b ){
return a.val<b.val;
}
void GetMap( int n ){
for( int i=0;i<n;i++ )
for( int j=0;j<n;j++ ){
mat[i][j] = dist( i,j );
//printf("mat[%d][%d]=%.3lf\n",i,j,mat[i][j]);
}
return ;
}
double prim( int n,int Belong ){
for( int i=0;i<n;i++ ){
dis[ i ] = mat[0][i];
vis[ i ] = false;
pre[ i ] = 0;
}
vis[0] = true;
//if( Belong==2 ){
// for( int i=0;i<n;i++ )for( int j=0;j<n;j++ )
//printf("mat[%d][%d]=%.3lf\n",i,j,mat[i][j]);
//}
double ans = 0;
for( int i=0;i<n;i++ ){
int id = -1;
double M = inf2;
for( int j=0;j<n;j++ ){
if( !vis[j] && M>dis[j] ){
M = dis[j];
id = j;
}
}
if( id==-1 ) break;
vis[ id ] = true;
ans += M;
edge[ cnt_edge ].u = pre[ id ];
edge[ cnt_edge ].v = id;
edge[ cnt_edge ].id = Belong;
edge[ cnt_edge ].val = mat[ id ][ pre[id] ];
//printf("u = %d,v = %d\n",edge[cnt_edge].u,edge[cnt_edge].v);
cnt_edge ++ ;
for( int j=0;j<n;j++ ){
if( !vis[j] && dis[j]>mat[id][j] ){
dis[j] = mat[id][j];
pre[ j ] = id;
}
}
}
return ans;
}
void Deal( int n ){
for( int i=0;i<cnt_edge;i++ ){
mat[ edge[i].u ][ edge[i].v ] = inf2;
mat[ edge[i].v ][ edge[i].u ] = inf2;
}
}
double Kruskal( int n,int id ){
double ans = 0;
init( n );
int cnt = 0;
for( int i=0;i<cnt_edge;i++ ){
if( i==id ) continue;
int fx = find( edge[i].u );
int fy = find( edge[i].v );
if( fx!=fy ){
if( rank[ fx ]<rank[ fy ] ){
rank[ fy ] += rank[ fx ];
fa[ fx ] = fy;
}
else {
rank[ fx ] += rank[ fy ];
fa[ fy ] = fx;
}
cnt ++ ;
ans += edge[i].val;
if( cnt==n-1 ) break;
}
}
return ans;
}
int main(){
int T;
scanf("%d",&T);
while( T-- ){
int n;
double k;
scanf("%d%lf",&n,&k);
for( int i=0;i<n;i++ )
scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
GetMap( n );
cnt_edge = 0;
LenPrim1 = prim( n,1 );
Deal( n );
LenPrim2 = prim( n,2 );
double ans = LenPrim1;
double temp_ans = 0;
sort( edge,edge+cnt_edge,cmp );
//printf("cnt_edge = %d\n",cnt_edge);
for( int i=0;i<cnt_edge;i++ ){
if( edge[i].id==1 && edge[i].u!=0 && edge[i].v!=0 ){
temp_ans = Kruskal( n,i );
if( temp_ans>ans )
ans = temp_ans;
}
}
printf("%.2lf\n",ans*k);
}
return 0;
}
分享到:
相关推荐
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
acm入门训练和日常训练 对于初学者以及acm爱好者有叫大帮助
hdu 1695 GCD(欧拉函数+容斥原理).docx
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
hdu1001解题报告
HDU的一题........HDU DP动态规
hdu 1574 passed sorce
acm hdu as easy as a+b
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
ACM HDU题目分类,我自己总结的大概只有十来个吧