B - Networking POJ - 1287

 1 #include <iostream> 2 #include <vector> 3 #include <map> 4 #include <string> 5 #include <queue> 6 #include <stack> 7 #include <algorithm> 8 #include <set> 9 10 #include <cstdio>11 #include <cstring>12 #include <cmath>13 #include <cstdlib>14 using namespace std;15 16 const int INF=0x3f3f3f3f;17 const int SIZE=100; ?///不是很懂要开多大 就开的大一点了18 19 int id[SIZE];20 int sz[SIZE];21 int m,n;22 23 struct node{24 ????int start;25 ????int end;26 ????int val;27 28 }edge[10000]; ??///emmmm29 void ?clear()30 {31 ????for(int i=0;i<=n;i++)32 ????{33 ????????id[i]=i;sz[i]=1;34 ????}35 }36 int find(int x)37 {38 ????if(x!=id[x]) ?id[x]=find(id[x]);39 ????return id[x];40 }41 42 void un(int p,int q)43 {44 ????p=find(p);45 ????q=find(q);46 ????if(p==q) return ;47 ????if(sz[p]<sz[q])48 ????????id[p]=find(q);49 ????else50 ????{51 ????????if(sz[p]==sz[q])52 ????????????sz[p]++;53 ????????id[q]=find(p);54 ????}55 }56 57 int kruskal()58 {59 ????int sum=0;60 ????for(int i=0;i<m;i++)61 ????{62 ????????if(find(edge[i].start)!=find(edge[i].end))63 ????????{64 ????????????un(edge[i].start,edge[i].end);65 ????????????sum+=edge[i].val;66 ????????}67 ????}68 ????return sum;69 70 }71 72 bool cmp(node a,node b)73 {74 ????return a.val<b.val;75 }76 int main()77 {78 ????while(cin>>n)79 ????{80 ????????if(n==0) break;81 ????????cin>>m;82 ????????clear();83 ????????int a,b,value;84 ????????for(int i=0;i<m;i++)85 ????????{86 ????????????cin>>a>>b>>value;87 ????????????edge[i].start=a;88 ????????????edge[i].end=b;89 ????????????edge[i].val=value;90 ????????}91 ????????sort(edge,edge+m,cmp);92 ????????cout<<kruskal()<<endl;93 ????}94 ????return 0;95 }

 1 #include <iostream> 2 #include <vector> 3 #include <map> 4 #include <string> 5 #include <queue> 6 #include <stack> 7 #include <set> 8 ?9 #include <cstdio>10 #include <cstring>11 #include <cmath>12 #include <cstdlib>13 using namespace std;14 15 const int INF=0x3f3f3f3f;16 const int SIZE=100;17 18 int dis[SIZE];19 int graph[SIZE][SIZE];20 int n,m;21 int vis[SIZE];22 23 int prim()24 {25 ????memset(vis,0,sizeof(vis));26 ????int index;27 ????int sum=0;28 ????for(int i=1;i<=n;i++) ?///起点是129 ????????dis[i]=graph[i][1];30 ????vis[1]=1;31 ????for(int i=2;i<=n;i++)32 ????{33 ????????int minn=INF;34 ????????for(int j=1;j<=n;j++)35 ????????????if(!vis[j]&&dis[j]<minn)36 ????????{37 ????????????minn=dis[j];index=j;38 ????????}39 ????????vis[index]=1;40 ????????sum+=minn;41 ????????for(int j=1;j<=n;j++)42 ????????????if(dis[j]>graph[j][index]&&!vis[j])43 ????????????????dis[j]=graph[j][index];44 ????}45 ????return sum;46 }47 int main()48 {49 ?????while(cin>>n)50 ????{51 ????????if(n==0) break;52 ????????cin>>m;53 ????????memset(graph,INF,sizeof(graph));54 ????????int a,b,value;55 ????????for(int i=0;i<m;i++)56 ????????{57 ????????????cin>>a>>b>>value;58 ????????????if(graph[a][b]>value) ??///注意重复就好59 ????????????????graph[a][b]=graph[b][a]=value;60 ????????}61 ????????cout<<prim()<<endl;62 ????}63 ????return 0;64 }