poj 1251 poj 1258 hdu 1863 poj 1287 poj 2421 hdu 1233 最小生成树模板题

poj 1251 && hdu 1301

Sample Input

9 //n 结点数
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0
Sample Output

216
30

prim算法

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 const int INF=0x3f3f3f3f;
10 const int MAXN=110;
11 bool vis[MAXN];
12 int lowc[MAXN];
13 int n ;
14 int cost[MAXN][MAXN] ;
15 
16 int Prim()//点是0~n-1
17 {
18     int ans=0;
19     memset(vis,false,sizeof(vis));
20     vis[0]=true;
21     for(int i=1;i<n;i++)lowc[i]=cost[0][i];
22     for(int i=1;i<n;i++)
23     {
24         int minc=INF;
25         int p=-1;
26         for(int j=0;j<n;j++)
27             if(!vis[j]&&minc>lowc[j])
28             {
29                 minc=lowc[j];
30                 p=j;
31             }
32             if(minc==INF)return -1;//原图不连通
33             ans+=minc;
34             vis[p]=true;
35             for(int j=0;j<n;j++)
36                 if(!vis[j]&&lowc[j]>cost[p][j])
37                     lowc[j]=cost[p][j];
38     }
39     return ans;
40 }
41 
42 int main()
43 {
44 
45    // freopen("in.txt","r",stdin) ;
46     while(cin>>n)
47     {
48         if (n == 0)
49             break ;
50         char u , v;
51         int w , num ;
52         int i , j ;
53         for (i = 0 ; i < n ; i++)
54             for (j = 0 ; j < n ; j++)
55                cost[i][j] = INF ;
56         
57         for (i = 1 ; i < n ; i++)
58         {
59             cin>>u>>num ;
60             while (num--)
61             {
62                 cin>>v>>w ;
63                 cost[u -'A'][v - 'A'] = w ;
64                 cost[v - 'A'][u -'A'] = w ;
65             }
66         }
67         cout<<Prim()<<endl ;
68 
69     }
70     return 0 ;
71 }

View Code

Kruskal算法

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 int n ;
10 const int MAXN=110;//最大点数
11 const int MAXM=10000;//最大边数
12 int F[MAXN];//并查集使用
13 struct Edge
14 {
15     int u,v,w;
16 }edge[MAXM];//存储边的信息，包括起点/终点/权值
17 
18 int tol;//边数，加边前赋值为0
19 void addedge(int u,int v,int w)
20 {
21 
22     edge[tol].u=u;
23     edge[tol].v=v;
24     edge[tol++].w=w;
25 }
26 bool cmp(Edge a,Edge b)
27 {//排序函数，讲边按照权值从小到大排序
28     return a.w<b.w;
29 }
30 int find(int x)
31 {
32     if(F[x]==-1)return x;
33     else return F[x]=find(F[x]);
34 }
35 int Kruskal()//传入点数，返回最小生成树的权值，如果不连通返回-1
36 {
37     memset(F,-1,sizeof(F));
38     sort(edge,edge+tol,cmp);
39     int cnt=0;//计算加入的边数
40     int ans=0;
41     for(int i=0;i<tol;i++)
42     {
43         int u=edge[i].u;
44         int v=edge[i].v;
45         int w=edge[i].w;
46         int t1=find(u);
47         int t2=find(v);
48         if(t1!=t2)
49         {
50             ans+=w;
51             F[t1]=t2;
52             cnt++;
53         }
54         if(cnt==n-1)break;
55     }
56     if(cnt<n-1)return -1;//不连通
57     else return ans;
58 }
59 
60 int main()
61 {
62 
63    // freopen("in.txt","r",stdin) ;
64     while(cin>>n)
65     {
66         if (n == 0)
67             break ;
68         char u , v;
69         int w , num ;
70         int i , j ;
71         tol = 0 ;
72         for (i = 1 ; i < n ; i++)
73         {
74             cin>>u>>num ;
75             while (num--)
76             {
77                 cin>>v>>w ;
78                 addedge(u,v,w) ;
79             }
80         }
81         cout<<Kruskal()<<endl ;
82 
83     }
84     return 0 ;
85 }

View Code

poj 1258

Sample Input

4 //n
0 4 9 21 //邻接矩阵
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output

prim

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 const int INF=0x3f3f3f3f;
10 const int MAXN=110;
11 bool vis[MAXN];
12 int lowc[MAXN];
13 int n ;
14 int cost[MAXN][MAXN] ;
15 
16 int Prim()//点是0~n-1
17 {
18     int ans=0;
19     memset(vis,false,sizeof(vis));
20     vis[0]=true;
21     for(int i=1;i<n;i++)lowc[i]=cost[0][i];
22     for(int i=1;i<n;i++)
23     {
24         int minc=INF;
25         int p=-1;
26         for(int j=0;j<n;j++)
27             if(!vis[j]&&minc>lowc[j])
28             {
29                 minc=lowc[j];
30                 p=j;
31             }
32             if(minc==INF)return -1;//原图不连通
33             ans+=minc;
34             vis[p]=true;
35             for(int j=0;j<n;j++)
36                 if(!vis[j]&&lowc[j]>cost[p][j])
37                     lowc[j]=cost[p][j];
38     }
39     return ans;
40 }
41 
42 int main()
43 {
44 
45     //freopen("in.txt","r",stdin) ;
46     while(cin>>n)
47     {
48         int w ;
49         int i , j ;
50         for (i = 0 ; i < n ; i++)
51             for (j = 0 ; j < n ; j++)
52                {
53                    cin>>w ;
54                    if(w==0)
55                      cost[i][j] = INF ;
56                    else
57                      cost[i][j] = w ;
58                }
59         cout<<Prim()<<endl ;
60 
61     }
62     return 0 ;
63 }

View Code

hdu 1863

Sample Input
3 3 //边数结点数
1 2 1 //一条边两边结点的id 边的权值
1 3 2
2 3 4
1 3
2 3 2
0 100

Sample Output
3
? //不连通就输出这个

Kruskal

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 int n ;
10 const int MAXN=110;//最大点数
11 const int MAXM=10000;//最大边数
12 int F[MAXN];//并查集使用
13 struct Edge
14 {
15     int u,v,w;
16 }edge[MAXM];//存储边的信息，包括起点/终点/权值
17 
18 int tol;//边数，加边前赋值为0
19 void addedge(int u,int v,int w)
20 {
21 
22     edge[tol].u=u;
23     edge[tol].v=v;
24     edge[tol++].w=w;
25 }
26 bool cmp(Edge a,Edge b)
27 {//排序函数，讲边按照权值从小到大排序
28     return a.w<b.w;
29 }
30 int find(int x)
31 {
32     if(F[x]==-1)return x;
33     else return F[x]=find(F[x]);
34 }
35 int Kruskal()//传入点数，返回最小生成树的权值，如果不连通返回-1
36 {
37     memset(F,-1,sizeof(F));
38     sort(edge,edge+tol,cmp);
39     int cnt=0;//计算加入的边数
40     int ans=0;
41     for(int i=0;i<tol;i++)
42     {
43         int u=edge[i].u;
44         int v=edge[i].v;
45         int w=edge[i].w;
46         int t1=find(u);
47         int t2=find(v);
48         if(t1!=t2)
49         {
50             ans+=w;
51             F[t1]=t2;
52             cnt++;
53         }
54         if(cnt==n-1)break;
55     }
56     if(cnt<n-1)return -1;//不连通
57     else return ans;
58 }
59 
60 int main()
61 {
62 
63   //  freopen("in.txt","r",stdin) ;
64     int m ;
65     while(scanf("%d %d" , &m , &n) != EOF)
66     {
67         if (m == 0)
68             break ;
69         int i ;
70         int u , v , w ;
71         tol = 0 ;
72         while(m--)
73         {
74             scanf("%d %d %d" , &u , &v , &w) ;
75             addedge(u , v , w) ;
76         }
77         int k = Kruskal() ;
78         if (k == -1)
79             printf("?
") ;
80         else
81             printf("%d
" , k) ;
82 
83     }
84     return 0 ;
85 }

View Code

poj 1287

Sample Input
1 0

2 3 //结点边
1 2 37//u v w
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

Sample Output

0
17
16
26

Kruskal

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 int n ;
10 const int MAXN=110;//最大点数
11 const int MAXM=10000;//最大边数
12 int F[MAXN];//并查集使用
13 struct Edge
14 {
15     int u,v,w;
16 }edge[MAXM];//存储边的信息，包括起点/终点/权值
17 
18 int tol;//边数，加边前赋值为0
19 void addedge(int u,int v,int w)
20 {
21 
22     edge[tol].u=u;
23     edge[tol].v=v;
24     edge[tol++].w=w;
25 }
26 bool cmp(Edge a,Edge b)
27 {//排序函数，讲边按照权值从小到大排序
28     return a.w<b.w;
29 }
30 int find(int x)
31 {
32     if(F[x]==-1)return x;
33     else return F[x]=find(F[x]);
34 }
35 int Kruskal()//传入点数，返回最小生成树的权值，如果不连通返回-1
36 {
37     memset(F,-1,sizeof(F));
38     sort(edge,edge+tol,cmp);
39     int cnt=0;//计算加入的边数
40     int ans=0;
41     for(int i=0;i<tol;i++)
42     {
43         int u=edge[i].u;
44         int v=edge[i].v;
45         int w=edge[i].w;
46         int t1=find(u);
47         int t2=find(v);
48         if(t1!=t2)
49         {
50             ans+=w;
51             F[t1]=t2;
52             cnt++;
53         }
54         if(cnt==n-1)break;
55     }
56     if(cnt<n-1)return -1;//不连通
57     else return ans;
58 }
59 
60 int main()
61 {
62 
63     //freopen("in.txt","r",stdin) ;
64     int m ;
65     while(scanf("%d %d" , &n , &m) != EOF)
66     {
67         if (n == 0)
68             break ;
69         int i ;
70         int u , v , w ;
71         tol = 0 ;
72         if (n == 1 && m == 0)
73         {
74             printf("0
") ;
75             continue ;
76         }
77         while(m--)
78         {
79             scanf("%d %d %d" , &u , &v , &w) ;
80             addedge(u , v , w) ;
81         }
82         printf("%d
" , Kruskal()) ;
83 
84     }
85     return 0 ;
86 }

View Code

poj 2421

有的路已建建好了的路权值设为0

Sample Input

3 // n
0 990 692 //邻接矩阵
990 0 179
692 179 0
1 //m
1 2 // u v
Sample Output

179

prim

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 const int INF=0x3f3f3f3f;
10 const int MAXN=110;
11 bool vis[MAXN];
12 int lowc[MAXN];
13 int n ;
14 int cost[MAXN][MAXN] ;
15 
16 int Prim()//点是0~n-1
17 {
18     int ans=0;
19     memset(vis,false,sizeof(vis));
20     vis[0]=true;
21     for(int i=1;i<n;i++)lowc[i]=cost[0][i];
22     for(int i=1;i<n;i++)
23     {
24         int minc=INF;
25         int p=-1;
26         for(int j=0;j<n;j++)
27             if(!vis[j]&&minc>lowc[j])
28             {
29                 minc=lowc[j];
30                 p=j;
31             }
32             if(minc==INF)return -1;//原图不连通
33             ans+=minc;
34             vis[p]=true;
35             for(int j=0;j<n;j++)
36                 if(!vis[j]&&lowc[j]>cost[p][j])
37                     lowc[j]=cost[p][j];
38     }
39     return ans;
40 }
41 
42 int main()
43 {
44 
45    // freopen("in.txt","r",stdin) ;
46     while(cin>>n)
47     {
48         int w ;
49         int i , j ;
50         for (i = 0 ; i < n ; i++)
51             for (j = 0 ; j < n ; j++)
52                {
53                    cin>>w ;
54                    if(w==0)
55                      cost[i][j] = INF ;
56                    else
57                      cost[i][j] = w ;
58                }
59         int m ;
60         cin>>m ;
61         while(m--)
62         {
63             int x , y ;
64             cin>>x>>y ;
65             cost[x-1][y-1] = 0 ;
66             cost[y-1][x-1] = 0 ;
67         }
68         cout<<Prim()<<endl ;
69 
70     }
71     return 0 ;
72 }

View Code

hdu 1233

n*(n-1)/2条边
Sample Input
3 //n
1 2 1 //u v w
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

Sample Output
3
5

Kruskal

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 int n ;
10 const int MAXN=110;//最大点数
11 const int MAXM=60000;//最大边数
12 int F[MAXN];//并查集使用
13 struct Edge
14 {
15     int u,v,w;
16 }edge[MAXM];//存储边的信息，包括起点/终点/权值
17 
18 int tol;//边数，加边前赋值为0
19 void addedge(int u,int v,int w)
20 {
21 
22     edge[tol].u=u;
23     edge[tol].v=v;
24     edge[tol++].w=w;
25 }
26 bool cmp(Edge a,Edge b)
27 {//排序函数，讲边按照权值从小到大排序
28     return a.w<b.w;
29 }
30 int find(int x)
31 {
32     if(F[x]==-1)return x;
33     else return F[x]=find(F[x]);
34 }
35 int Kruskal()//传入点数，返回最小生成树的权值，如果不连通返回-1
36 {
37     memset(F,-1,sizeof(F));
38     sort(edge,edge+tol,cmp);
39     int cnt=0;//计算加入的边数
40     int ans=0;
41     for(int i=0;i<tol;i++)
42     {
43         int u=edge[i].u;
44         int v=edge[i].v;
45         int w=edge[i].w;
46         int t1=find(u);
47         int t2=find(v);
48         if(t1!=t2)
49         {
50             ans+=w;
51             F[t1]=t2;
52             cnt++;
53         }
54         if(cnt==n-1)break;
55     }
56     if(cnt<n-1)return -1;//不连通
57     else return ans;
58 }
59 
60 int main()
61 {
62 
63    // freopen("in.txt","r",stdin) ;
64     while(scanf("%d" , &n) != EOF)
65     {
66         if (n == 0)
67             break ;
68         int i ;
69         int u , v , w ;
70         tol = 0 ;
71 
72         for (i = 1 ; i <= (n-1)*n/2 ; i++)
73         {
74             scanf("%d %d %d" , &u , &v , &w) ;
75             addedge(u , v , w) ;
76         }
77         printf("%d
" , Kruskal()) ;
78 
79     }
80     return 0 ;
81 }

View Code