hdu1102&hdu4081最小生成树,次小生成树

Posted by Cww97 on 2016-05-19

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/51449723
hdu1102
MST模板题
复习下kruskal,补一下之前偷懒没学的prim

赤裸裸的kruskal(lrj风格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=107;
int n,m,g[N][N];
struct Edge{
int x,y,w;
Edge():x(0),y(0),w(0){}
Edge(int _x,int _y,int _w):x(_x),y(_y),w(_w){}
bool operator < (const Edge &a)const{return w<a.w;}
}edges[N*N];
int home[N];//²¢²é¼¯
int Find(int x){return home[x]==x?x:home[x]=Find(home[x]);}

int kruskal(){
sort(edges+1,edges+m+1);
for (int i=1;i<=n;i++)home[i]=i;
int sum=0,cnt=0;
for (int i=1;i<=m;i++){
int x=Find(edges[i].x);
int y=Find(edges[i].y);
if (x==y)continue;
home[x]=y;
sum+=edges[i].w;
cnt++;
if (cnt==n-1)break;
}
return sum;
}

int main(){
for (;scanf("%d",&n)==1;){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
scanf("%d",&g[i][j]);
}
}
int x,y,q;
scanf("%d",&q);
for (;q--;){
scanf("%d%d",&x,&y);
g[x][y]=g[y][x]=0;
}
m=0;
for (int i=1;i<=n;i++){
for (int j=1;j<i;j++){
edges[++m]=Edge(i,j,g[i][j]);
}
}
printf("%d\n",kruskal());
}
return 0;
}

赤裸裸的prim
看了巫泽俊的板(《挑战》书里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=107;
int n,g[N][N];

int prim(){
int minw[N];//MinWeight
bool used[N];
memset(used,0,sizeof(used));
memset(minw,0x7f,sizeof(minw));
minw[1]=0;
int sum=0;
while (1){
int v=-1;
for (int i=1;i<=n;i++){
if (!used[i]&&(v==-1||minw[i]<minw[v]))v=i;
}
if (v==-1)break;
used[v]=1;
sum+=minw[v];
for (int i=0;i<=n;i++){
minw[i]=min(minw[i],g[v][i]);
}
}
return sum;
}

int main(){
for (;scanf("%d",&n)==1;){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
scanf("%d",&g[i][j]);
}
}
int x,y,q;
scanf("%d",&q);
for (;q--;){
scanf("%d%d",&x,&y);
g[x][y]=g[y][x]=0;
}
printf("%d\n",prim());
}
return 0;
}

为何我感觉还是kruskal简单呢,因为无脑贪心吗。。
补prim是为了这题
hdu4081
秦始皇啊,,,
这里有篇题解很详细的讲了次小生成树算法的证明和代码,
看完中文讲解,自己强行在上面的prim代码里面改,改的亲爹都不认识了,调了半天,过了样例,WA了,,,又对照题解里代码改,改的似乎亲爹认识了,,,依然WA,,,心累,玩个游戏叫找不同 = =终于A了,,,代码还是写的少了
废话了一大堆,上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1007;
int n;
double g[N][N],maxw[N][N];
bool used[N][N];
struct City{
int x,y,w;//w=population
City():x(0),y(0),w(0){}
City(int _x,int _y,int _w):x(_x),y(_y),w(_w){}
}citys[N];
double dist(City a,City b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double prim(){
int from[N];
bool vis[N];
double minw[N];
for(int i=1;i<=n;i++){
minw[i]=g[1][i];
from[i]=1;
}
memset(used,0,sizeof(used));
memset(maxw,0,sizeof(maxw));
memset(vis,0,sizeof(vis));
vis[1]=1;
minw[1]=0;
double sum=0;
while (1){
int v=-1;
for (int i=1;i<=n;i++)if (!vis[i]){
if (v==-1||minw[i]<minw[v])v=i;
}
if (v==-1)break;
//printf("from[%d]=%d\n",v,from[v]);
used[v][from[v]]=used[from[v]][v]=1;
vis[v]=1;
sum+=minw[v];
//printf("minw[%d]=%.8lf\n",v,minw[v]);
for (int i=1;i<=n;i++){
if (!vis[i]&&g[v][i]<minw[i]){
minw[i]=g[v][i];
from[i]=v;
}
if (vis[i]&&i!=v){
maxw[i][v]=maxw[v][i]=max(maxw[i][from[v]],minw[v]);
//printf(" maxw[%d][%d]=%.8lf\n",i,v,maxw[i][v]);
}
}
}
//for (int i=1;i<=n;i++)printf("from[%d]=%d\n",i,from[i]);
return sum;
}

int main(){
//freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
for (;T--;){
scanf("%d",&n);int x,y,z;
for (int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&z);
citys[i]=City(x,y,z);
}
for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)
g[i][j]=dist(citys[i],citys[j]);

double sum=prim(),ans=-1;
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++){
if (used[i][j])ans=max(ans,(citys[i].w+citys[j].w)/(sum-g[i][j]));
else ans=max(ans,(citys[i].w+citys[j].w)/(sum-maxw[i][j]));
}
}
printf("%.2lf\n",ans);
}
return 0;
}

大家晚安,
我的心愿是
!!世界和平!!