本文共 2986 字，大约阅读时间需要 9 分钟。
题意：求连接所有村庄道路的最小费用。
分析：kruskal算法，直接求最小生成树。
注意：这题输入的时候是字母，所以要注意了。POJ如果用getchar()的话会wa。坑爹啊。还好我后来在ZOJ 上提交过了，在POJ discuss里发现说tle||re的注意了要用数组输入字母（呵呵，我的是WA），以后碰到这种还是直接用数组，省那么点空间干嘛。还有这题关键是建图，具体细则参看代码。这次代码有点乱。呵呵。见谅。
1 // I'm the Topcoder 2 //C 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 //C++ 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 using namespace std; 26 27 //*************************OUTPUT************************* 28 #ifdef WIN32 29 #define INT64 "%I64d" 30 #define UINT64 "%I64u" 31 #else 32 #define INT64 "%lld" 33 #define UINT64 "%llu" 34 #endif 35 36 //**************************CONSTANT*********************** 37 #define INF 0x3f3f3f3f 38 #define eps 1e-8 39 #define PI acos(-1.) 40 #define PI2 asin (1.); 41 typedef long long LL; 42 //typedef __int64 LL; //codeforces 43 typedef unsigned int ui; 44 typedef unsigned long long ui64; 45 #define MP make_pair 46 typedef vector VI; 47 typedef pair PII; 48 #define pb push_back 49 #define mp make_pair 50 51 //***************************SENTENCE************************ 52 #define CL(a,b) memset (a, b, sizeof (a)) 53 #define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b)) 54 #define sqr3(a,b,c) sqrt((double)(a)*(a) + (double)(b)*(b) + (double)(c)*(c)) 55 56 //****************************FUNCTION************************ 57 template double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); } 58 template inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; } 59 template inline T square(T va, T vb) { return va * va + vb * vb; } 60 61 // aply for the memory of the stack 62 //#pragma comment (linker, "/STACK:1024000000,1024000000") 63 //end 64 65 int n,m,mi; 66 #define maxn 1000+10 67 int pa[maxn]; 68 //dis[maxn][maxn]; 69 char str[maxn][maxn]; 70 int num=0; 71 int sumweight=0; 72 int cnt=0; 73 struct node{ 74 int u,v,w; 75 }edges[maxn]; 76 77 //初始化 78 void UFset(){ 79 for(int i=0;i =0;s=pa[s]); 88 while(s!=x){ 89 int tmp=pa[x]; 90 pa[x]=s; 91 x=tmp; 92 } 93 return s; 94 } 95 96 //合并 97 void Union(int R1,int R2){ 98 int r1=findset(R1),r2=findset(R2); 99 int tmp=pa[r1]+pa[r2];100 if(pa[r1]>pa[r2]){101 pa[r1]=r2;102 pa[r2]=tmp;103 }104 else {105 pa[r2]=r1;106 pa[r1]=tmp;107 }108 }109 110 111 int cmp(const void*a,const void*b){112 node aa=*(const node*)a;113 node bb=*(const node*)b;114 if(aa.w>bb.w) return 1;115 else return -1;116 }117 void Kruskal(){118 int u,v;119 UFset();120 num=0;121 for(int i=0;i =n-1) break;130 }131 }132 133 int main(){134 while(scanf("%d",&n)!=EOF){135 if(n==0) break;136 char ch[100],ch1[100];137 int d;138 mi=0;139 int u,v;140 cnt=0;141 sumweight=0;142 for(int i=0;i
转载于:https://www.cnblogs.com/lanjiangzhou/archive/2013/03/25/2980979.html
View Code