Constructing Roads
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10358 Accepted Submission(s): 3854
Problem Description
There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.
We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.
We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.
Input
The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.
Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.
Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.
Output
You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.
Sample Input
3 0 990 692 990 0 179 692 179 0 1 1 2
Sample Output
179
Source
Recommend
Eddy
1, Prim:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=110; const int INF=0x3f3f3f3f; int n,ans; int map[maxn][maxn],dis[maxn],vis[maxn]; void Prim(){ int i; for(i=1;i<=n;i++){ dis[i]=map[1][i]; vis[i]=0; } dis[1]=0; vis[1]=1; int j,k,tmp; for(i=1;i<=n;i++){ tmp=INF; for(j=1;j<=n;j++) if(!vis[j] && tmp>dis[j]){ k=j; tmp=dis[j]; } if(tmp==INF) return ; ans+=dis[k]; vis[k]=1; for(j=1;j<=n;j++) if(!vis[j] && dis[j]>map[k][j]) dis[j]=map[k][j]; } } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&n)){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&map[i][j]); int q,u,v; scanf("%d",&q); while(q--){ scanf("%d%d",&u,&v); map[u][v]=map[v][u]=0; } ans=0; Prim(); printf("%d\n",ans); } return 0; }
2, Kruskal():
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=110; struct Edge{ int u,v; int w; }edge[maxn*100]; int n,ans,cnt; int father[maxn],rank[maxn]; void addedge(int cu,int cv,int cw){ edge[cnt].u=cu; edge[cnt].v=cv; edge[cnt].w=cw; cnt++; } void makeSet(){ for(int i=1;i<=n;i++){ father[i]=i; rank[i]=1; } } int findSet(int x){ if(x!=father[x]){ father[x]=findSet(father[x]); } return father[x]; } int cmp(Edge a,Edge b){ return a.w<b.w; } void Kruskal(){ sort(edge,edge+cnt,cmp); for(int i=0;i<cnt;i++){ int fx=findSet(edge[i].u); int fy=findSet(edge[i].v); if(fx==fy) continue; ans+=edge[i].w; if(rank[fx]>=rank[fy]){ father[fy]=fx; rank[fx]+=rank[fy]; }else{ father[fx]=fy; rank[fy]+=rank[fx]; } } } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&n)){ cnt=0; makeSet(); int w; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&w); addedge(i,j,w); } int q,u,v; scanf("%d",&q); while(q--){ scanf("%d%d",&u,&v); int fx=findSet(u); int fy=findSet(v); if(rank[fx]>=rank[fy]){ father[fy]=fx; rank[fx]+=rank[fy]; }else{ father[fx]=fy; rank[fy]+=rank[fx]; } } ans=0; Kruskal(); printf("%d\n",ans); } return 0; }
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
hdu 1166线段树代码
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
hdu 1166线段树
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
NULL 博文链接:https://128kj.iteye.com/blog/1734821