Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。 当N为0时输入结束。
Output
每个测试用例的输出占一行，输出全省畅通需要的最低成本。
Sample Input
3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0
Sample Output
3 1 0
一开始超时，后来换了scanf过了。
思路：最小生成树，用Kruskal算法。（emm，其实完全可以不用堆，先用vector存起来，sort一下，然后扫一遍就行了，时间可能会快许多）
#include<iostream> #include<iomanip> //#include<bits/stdc++.h> #include<cstdio> #include<cmath> #include<string> #include<algorithm> #include<cstring> #include<vector> #include<sstream> #include<queue> #include<set> #define PI 3.14159265358979 #define LL long long using namespace std; int pre[110]; int w[110][110]; struct node{ int a,b,c; node(int x,int y,int z){ a=x;b=y;c=z; } bool operator <(node X)const { return c>X.c; } }; priority_queue<node> v; int Find(int x) { return pre[x]==x?x:pre[x]=Find(pre[x]); } void join(int x,int y) { int q,p; q=Find(x); p=Find(y); if(q!=p) { pre[q]=p; } } int main() { //freopen("input.txt","r",stdin); int f,n,m,t,dis,T,r; while(scanf("%d",&n)==1&&n) { for(int i=1;i<=101;++i) pre[i]=i; n=n*(n-1)/2; for(int i=1;i<=n;++i) { scanf("%d%d%d%d",&f,&t,&dis,&r); if(r==0) { v.push(node(f,t,dis)); continue; } join(f,t); } int sum=0; while(!v.empty()) { node temp=v.top();v.pop(); if(Find(pre[temp.a])!=Find(pre[temp.b])) { sum+=temp.c;join(temp.a,temp.b); } } printf("%d\n",sum); //for(int i=1;i<=n;++i) cout<<pre[i]<<" "; } }
