首页 > 代码库 > URAL(timus) 1272 Non-Yekaterinburg Subway(最小生成树)
URAL(timus) 1272 Non-Yekaterinburg Subway(最小生成树)
Non-Yekaterinburg Subway
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
A little town started to construct a subway. The peculiarity of the town is that it is located on small islands, some of them are connected with tunnels or bridges. The mayor is sure that the subway is to be under the ground, that’s why the project must use the less bridges the better. The only request for the subway is that the townsmen could get by metro (may be with changes) from every island to every island. Fortunately, we know that there is enough tunnels and bridges for it. It was decided to construct as less passages from island to island as possible to save money.
Your task given a town plan to determine the minimal possible number of bridges that is necessary to use in the subway construction.
Input
The first line contains three integers separated with a space: N (the number of islands, 1 ≤ N ≤ 10000), K (the number of tunnels, 0 ≤ K ≤ 12000) and M (the number of bridges, 0 ≤ M ≤ 12000). Then there are K lines; each line consists of two integers — the numbers of islands, connected with the corresponding tunnel. The last M lines define bridges in the same format.
Output
the minimal number of bridges necessary for the subway construction.
Sample
| input | output |
|---|---|
6 3 41 22 34 51 33 44 65 6 | 2 |
Problem Author: Magaz Asanov (prepared Igor Goldberg)
【分析】一个小镇由很多小岛组成，小岛之间原来有桥或者隧道。先要在某些小岛间建地铁，如果某两个小岛之间原来有隧道，就直接建。如果是桥，则不建，且要保证桥和地铁要使所有岛屿联通。可用最小生成树做，桥的话权值为1，隧道为0.一开始用二维数组存边，MLE，像这种点比较多的，就得用结构体了，这里用的Kruskal.
#include <iostream>#include <cstring>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <time.h>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#define inf 0x3f3f3f3f#define mod 10000typedef long long ll;using namespace std;const int N=10005;const int M=100005;struct Edg { int v,u; int w;} edg[M];bool cmp(Edg g,Edg h) { return g.w<h.w;}int n,m,maxn,cnt,k;int parent[N];int a[N];void init() { for(int i=0; i<n; i++)parent[i]=i;}void Build() { int u,v; while(k--){ scanf("%d%d",&u,&v); edg[++cnt].u=u; edg[cnt].v=v; edg[cnt].w=0; } while(m--){ scanf("%d%d",&u,&v); edg[++cnt].u=u; edg[cnt].v=v; edg[cnt].w=1; } sort(edg,edg+cnt+1,cmp);}int Find(int x) { if(parent[x] != x) parent[x] = Find(parent[x]); return parent[x];}void Union(int x,int y) { x = Find(x); y = Find(y); if(x == y) return; parent[y] = x;}void Kruskal() { int sum=0; int num=0; int u,v; for(int i=0; i<=cnt; i++) { u=edg[i].u; v=edg[i].v; if(Find(u)!=Find(v)) { sum+=edg[i].w; num++; Union(u,v); } if(num>=n-1) { printf("%d\n",sum); break; } }}int main() { scanf("%d%d%d",&n,&k,&m); if(m==0)printf("0\n"),exit(0); if(n==1)printf("0\n"),exit(0); cnt=-1; init(); Build(); Kruskal(); return 0;}
URAL(timus) 1272 Non-Yekaterinburg Subway(最小生成树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。