HDOJ1102解题报告【最小生成树】

题目地址：

　　http://acm.hdu.edu.cn/showproblem.php?pid=1102

题目概述：

　　给出一张图，已知图上点两两间的距离以及已有的边，现要在图上加边，使增加的所有边的距离总和最小并且增加边之后整张图连通。

大致思路：

　　果果的最小生成树啊！！n这么小，还保证除了自身以外与其他所有点都一定有给定的距离，所以直接上kruskal模板就好啦。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <vector>
 6 #include <ctime>
 7 #include <map>
 8 #include <stack>
 9 #include <queue>
10 #include <cstring>
11 #include <algorithm>
12 using namespace std;
13 
14 #define sacnf scanf
15 #define scnaf scanf
16 #define scanfi(x) scanf("%d",&x)
17 #define scanfd(x) scanf("%lf",&x)
18 #define scanfl(x) scanf("%lld",&x)
19 #define scanfc(x) scanf("%c",&x)
20 #define scanfs(x) scanf("%s",x)
21 #define maxn  110
22 #define maxm 10
23 #define inf 1061109567
24 #define Eps 0.00001
25 const double PI=acos(-1.0);
26 #define mod 1000000007
27 #define MAXNUM 10000
28 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
29 int Abs(int x) {return (x<0)?-x:x;}
30 typedef long long ll;
31 typedef unsigned int uint;
32 
33 struct node
34 {
35     int from,to,dist;
36     bool operator < (const node &a) const
37     {
38         return dist<a.dist;
39     }
40 } m[maxn*maxn];
41 
42 int p[maxn];
43 int G[maxn][maxn];
44 
45 int found(int x) {return (p[x]==x)?x:p[x]=found(p[x]);}
46 
47 int kruskal(int cnt)
48 {
49     int ans=0;
50     sort(m+1,m+1+cnt);
51     for(int i=1;i<=cnt;i++)
52     {
53         int x=found(m[i].from);
54         int y=found(m[i].to);
55         if(x!=y) p[x]=y,ans+=m[i].dist;
56     }
57     return ans;
58 }
59 
60 int main()
61 {
62     //freopen("data.in","r",stdin);
63     //freopen("data.out","w",stdout);
64     //clock_t st=clock();
65     int n;
66     while(~scanfi(n))
67     {
68         for(int i=1;i<=n;i++)
69         {
70             p[i]=i;
71             for(int j=1;j<=n;j++)
72             {
73                 scanfi(G[i][j]);
74             }
75         }
76         int q,x,y;scanfi(q);
77         while(q--)
78         {
79             scanf("%d%d",&x,&y);
80             if(x<y) swap(x,y);
81             G[x][y]=0;
82         }
83         int cnt=0;
84         for(int i=1;i<=n;i++)
85         {
86             for(int j=1;j<i;j++)
87             {
88                 m[++cnt]=(node){i,j,G[i][j]};
89             }
90         }
91         printf("%d
",kruskal(cnt));
92     }
93     //clock_t ed=clock();
94     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
95     return 0;
96 }

HDOJ1102解题报告【最小生成树】

相关推荐