php网站开发教程网,各国网站域名,网站建设哪个比较好,it培训机构网站开发今天刷一下水题练手入门#xff0c;明天继续。 poj1861 Network#xff08;最小生成树#xff09;新手入门题。 题意#xff1a;输出连接方案中最长的单根网线长度#xff08;必须使这个值是所有方案中最小的#xff09;#xff0c;然后输出方案。 题解#xff1a;本题… 今天刷一下水题练手入门明天继续。 poj1861 Network最小生成树新手入门题。 题意输出连接方案中最长的单根网线长度必须使这个值是所有方案中最小的然后输出方案。 题解本题没有直接求生成树但如果连接n个集线器的方案多于n-1条边那么必存在回路因此去掉某些边剩下的边和所有顶点构成一个生成树。对于一个图的最小生成树来说它的最大边满足所有生成树的最大边里最小正和题意。 吐槽题目样例是错的。。。 1 #includecstdio2 #includecstring3 #includealgorithm4 using namespace std;5 const int N1001;6 struct edge{7 int u,v,w;8 }e[15001];9 int f[N],a[N],ai;
10 int n,m,ma;
11 int cmp(edge a,edge b){
12 return a.wb.w;
13 }
14 void init(){
15 for(int i1;in;i)
16 f[i]i;
17 }
18 int fin(int x){
19 if(x!f[x])f[x]fin(f[x]);
20 return f[x];
21 }
22 void Kruskal(){
23 maai0;
24 int u,v,i;
25 init();
26 for(i0;im;i){
27 ue[i].u;
28 ve[i].v;
29 if((ufin(u))!(vfin(v))){
30 f[u]v;
31 a[ai]i;
32 mamax(e[i].w,ma);
33 }
34 if(ain-1)break;
35 }
36 }
37 int main(){
38 int i,u,v,w;
39 scanf(%d%d,n,m);
40 for(i0;im;i){
41 scanf(%d%d%d,u,v,w);
42 e[i]edge{u,v,w};
43 }
44 sort(e,em,cmp);
45 Kruskal();
46 printf(%d\n%d\n,ma,ai);
47 for(i0;iai;i)
48 printf(%d %d\n,e[a[i]].u,e[a[i]].v);
49 return 0;
50 } View Code poj1251 Jungle Roads最小生成树水题。 1 #includecstdio2 #includecstring3 #includealgorithm4 using namespace std;5 const int N27;6 struct edge{7 int u,v,w;8 }e[75];9 int f[N];
10 int n,m,ans;
11 int cmp(edge a,edge b){
12 return a.wb.w;
13 }
14 void init(){
15 for(int i0;in;i)
16 f[i]i;
17 }
18 int fin(int x){
19 if(x!f[x])f[x]fin(f[x]);
20 return f[x];
21 }
22 void Kruskal(){
23 ans0;
24 int u,v,i;
25 init();
26 for(i0;im;i){
27 ue[i].u;
28 ve[i].v;
29 if((ufin(u))!(vfin(v))){
30 f[u]v;
31 anse[i].w;
32 }
33 }
34 }
35 int main(){
36 int i,j,w,k;
37 char u[3],v[3];
38 while(scanf(%d,n),n){
39 m0;
40 for(i0;in-1;i){
41 scanf(%s %d,u,k);
42 for(j0;jk;j){
43 scanf(%s %d,v,w);
44 e[m]{u[0]-A,v[0]-A,w};
45 }
46 }
47 sort(e,em,cmp);
48 Kruskal();
49 printf(%d\n,ans);
50 }
51 return 0;
52 } View Code poj1287 Networking最小生成树水题。 用prim要注意两个地点之间的线路可能多条即有重边。我这里练的是Kruskal题目没给边数但知道点数最多50则边数最多50*49/21225条有重边开大点数组就行因为数据弱随便开个1500都过了醉。。。 1 #includecstdio2 #includecstring3 #includealgorithm4 using namespace std;5 const int M1500;6 struct edge{7 int u,v,w;8 }e[M];9 int f[50];
10 int n,m,ans;
11 int cmp(edge a,edge b){
12 return a.wb.w;
13 }
14 void init(){
15 for(int i1;in;i)
16 f[i]i;
17 }
18 int fin(int x){
19 if(x!f[x])f[x]fin(f[x]);
20 return f[x];
21 }
22 void Kruskal(){
23 ans0;
24 int u,v,i;
25 init();
26 for(i0;im;i){
27 ue[i].u;
28 ve[i].v;
29 if((ufin(u))!(vfin(v))){
30 f[u]v;
31 anse[i].w;
32 }
33 }
34 }
35 int main(){
36 int i,u,v,w;
37 while(scanf(%d,n),n){
38 scanf(%d,m);
39 for(i0;im;i){
40 scanf(%d%d%d,u,v,w);
41 e[i]{u,v,w};
42 }
43 sort(e,em,cmp);
44 Kruskal();
45 printf(%d\n,ans);
46 }
47 return 0;
48 } View Code poj2031 Building a Space Station最小生成树题目看老久其实挺水…空间站存在一些球形单间如果单间之间接触重叠或用走廊连接则连通。给出单间坐标和半径求要使得所有单间相连通的走廊总长度的最小值。 1 #includecstdio2 #includecstring3 #includealgorithm4 #includecmath5 using namespace std;6 const int M5000;7 const int N100;8 struct edge{9 int u,v;
10 double w;
11 }e[M];
12 double a[N],b[N],c[N],r[N];
13 int f[N];
14 int n,m;
15 double ans;
16 int cmp(edge a,edge b){
17 return a.wb.w;
18 }
19 double dist(int i,int j){
20 return sqrt((a[i]-a[j])*(a[i]-a[j])(b[i]-b[j])*(b[i]-b[j])(c[i]-c[j])*(c[i]-c[j]))-r[i]-r[j];
21 }
22 void init(){
23 for(int i0;in;i) f[i]i;
24 }
25 int fin(int x){
26 if(x!f[x])f[x]fin(f[x]);
27 return f[x];
28 }
29 void Kruskal(){
30 ans0;
31 int u,v,i,cnt0;
32 init();
33 for(i0;cntn-1;i){
34 ue[i].u;
35 ve[i].v;
36 if((ufin(u))!(vfin(v))){
37 f[u]v;
38 anse[i].w;
39 cnt;
40 }
41 }
42 }
43 int main(){
44 int i,j;
45 double w;
46 while(scanf(%d,n),n){
47 for(i0;in;i){
48 scanf(%lf%lf%lf%lf,a[i],b[i],c[i],r[i]);
49 }
50 for(mi0;in-1;i){
51 for(ji1;jn;j){
52 wdist(i,j);
53 if(w0) w0;
54 e[m]{i,j,w};
55 }
56 }
57 sort(e,em,cmp);
58 Kruskal();
59 printf(%.3f\n,ans);
60 }
61 return 0;
62 } View Code poj2421 Constructing Roads最小生成树水题。有些点已经连边进行标记加边时将其边赋值为0即可。 1 #includecstdio2 #includecstring3 #includealgorithm4 using namespace std;5 const int M5000;6 const int N101;7 struct edge{8 int u,v,w;9 }e[M];
10 int f[N];
11 int g[N][N],vis[N][N];
12 int n,ans;
13 int cmp(edge a,edge b){
14 return a.wb.w;
15 }
16 void init(){
17 for(int i1;in;i) f[i]i;
18 }
19 int fin(int x){
20 if(x!f[x])f[x]fin(f[x]);
21 return f[x];
22 }
23 void Kruskal(){
24 ans0;
25 int u,v,i,cnt0;
26 init();
27 for(i0;cntn-1;i){
28 ue[i].u;
29 ve[i].v;
30 if((ufin(u))!(vfin(v))){
31 f[u]v;
32 anse[i].w;
33 cnt;
34 }
35 }
36 }
37 int main(){
38 int i,j,a,b,ei,m;
39 while(scanf(%d,n)1){
40 for(i1;in;i)
41 for(j1;jn;j)
42 scanf(%d,g[i][j]);
43 memset(vis,0,sizeof(vis));
44 scanf(%d,m);
45 while(m--){
46 scanf(%d%d,a,b);
47 vis[a][b]1;
48 }
49 ei0;
50 for(i1;in;i){
51 for(ji1;jn;j){
52 if(vis[i][j]) e[ei]{i,j,0};
53 else e[ei]{i,j,g[i][j]};
54 }
55 }
56 sort(e,eei,cmp);
57 Kruskal();
58 printf(%d\n,ans);
59 }
60 return 0;
61 } View Code 转载于:https://www.cnblogs.com/GraceSkyer/p/5774634.html
