HDU 1102 Constructing Roads
题意：有V个结点，每两个结点间有一条边，以邻接矩阵的形式输入。已经存在的路径有E条，并且输入这些路径的两个结点（起始点）。问：在已经存在的边的基础上使所有点连通的最小路径是多少。思路：将已经存在的路径的起始点放在一棵树上，我们要考虑到存在的路径中有环，所以记录下已经存在的树枝的数量exist，然后按照kruskal的模板走就行了，只是边个个数变为了V-1-exist。My_Feeling:感jiao自己对kruskal好不熟悉QAQ，第一发给T了，看了一下复杂度不大啊。然后就比较之前写的kruskal，发现函数里没有Merge连接不在一棵树上的点QAQ，tcl……死循环了啊QAQ #include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <set> #include <stack> #include <list> #include <map> #define P(x) x>0?x:0 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef vector<int>:: iterator VITer; const int maxV=105; const int maxE=5100; int V,E; int cnt,exist; int root[maxV],high[maxV],size[maxV]; int Find(int x) { return root[x]==x ? x : root[x]=Find(root[x]); } int Same(int x,int y) { return Find(x)==Find(y); } void Merge(int x,int y) { x=Find(x); y=Find(y); if(high[x]<high[y]||size[x]<size[y]) { root[x]=y; size[y]+=size[x]; } else { root[y]=x; size[x]+=size[y]; if(high[x]==high[y]) high[x]++; } } struct node{ int u,v,w; node(int a=0,int b=0,int c=0):u(a),v(b),w(c){} friend bool operator < (node n1,node n2) { return n1.w<n2.w; } }ve[maxE]; void init() { cnt=0; exist=0; for(int i=1;i<=V;i++) { root[i]=i; high[i]=0; size[i]=1; } } int kruskal() { int ans=0,edge_num=0; sort(ve,ve+cnt); for(int i=0;i<cnt;i++) { if(!Same(ve[i].u,ve[i].v)) { Merge(ve[i].u,ve[i].v); ans+=ve[i].w; edge_num++; if(edge_num==V-1-exist) break; } } return ans; } int main() { while(~scanf("%d",&V)) { init(); for(int i=1;i<=V;i++) { for(int j=1;j<=V;j++) { int val; scanf("%d",&val); if(i<j) ve[cnt++]=node(i,j,val); } } scanf("%d",&E); for(int i=1;i<=E;i++) { int a,b; scanf("%d%d",&a,&b); if(!Same(a,b)) { Merge(a,b); exist++; } } printf("%d\n",kruskal()); } return 0; }