Jungle Roads
套用Kruskal或Prim的模板即可。这里我用的时Kruskal。
代码如下:
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
|
#include <string> #include <algorithm> #include <cmath> #include <iostream> #define INF 0x3f3f3f3f #define mst(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef struct{ int from,to,cost; }edge; edge arr[100]; int pre[100]; int n; int cnt; bool (edge e1,edge e2) { return e1.cost<e2.cost; } void init() { for(int i=1;i<=n;i++) pre[i]=i; } int findr(int x) { if(x==pre[x]) return x; return pre[x]=findr(pre[x]); } int kruskal() { int rsl=0;int num=0; init(); for(int i=0;i<cnt;i++) { int fx=findr(arr[i].from); int fy=findr(arr[i].to); if(fx!=fy) { pre[fx]=fy; rsl+=arr[i].cost; } } return rsl; } int main() { while(cin>>n&&n) { cnt=0; for(int i=0;i<n-1;i++) { char ch,ch1; int k,aacm; cin>>ch>>k; getchar(); for(int j=1;j<=k;j++) { edge tmp; cin>>ch1>>aacm; getchar(); tmp.from=ch-'A'+1; tmp.to=ch1-'A'+1; tmp.cost=aacm; arr[cnt++]=tmp; } } sort(arr,arr+cnt,cmp); int ans=kruskal(); printf("%dn",ans); } return 0; }
|
近期评论