>

最短网络

- 编辑:金沙国际平台登录 -

最短网络

  • 题目

难点背景

农民John被选为他们镇的区长!他中间贰个公投承诺正是在镇上创设起网络,并连接到持有的农场。当然,他索要您的帮扶。

  John已经给他的农场配置了一条急迅的网络线路,他想把那条线路分享给另外农场。为了用小小的费用,他想铺设最短的光导纤维去老是全数的农场。

主题材料陈诉

John已经给他的农场布局了一条便捷的网络线路,他想把那条线路分享给任何农场。为了用非常小的开销,他想铺设最短的光导纤维去老是全体的农场。

您将赢得一份各农场里面三回九转开支的列表,你必需搜索能再而三全体农场并所用光导纤维最短的方案。每七个农场间的相距不会超过一千00

你将获取一份各农场里面连接费用的列表,你必得寻觅能延续全部农场并所用光导纤维最短的方案。每多少个农场间的偏离不会抢先一千00。

输入输出格式

输入格式:

第一行: 农场的个数,N(3<=N<=100)。

其次行..结尾: 后来的行富含了一个N*N的矩阵,表示每一个农场之内的偏离。理论上,他们是N行,每行由N个用空格分隔的数组成,实际上,他们限制在七十八个字符,由此,有个别行会紧接着另一些行。当然,对角线将会是0,因为不会有路经从第i个农场到它自个儿。

出口格式:

唯有叁个出口,个中蕴涵连接到各样农场的光导纤维的小不点儿长度。

  • 输入

输入输出样例

输入样例#1:

40 4 9 214 0 8 179 8 0 1621 17 16 0

出口样例#1:

28

  第一行: 农场的个数,N(3<=N<=100)。

说明

主题素材翻译来自NOCOW。

USACO Training Section 3.1

裸的kurskal,注意fa数组须求求开的够大!

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int MAXN=4001; 8 void read(int & n) 9 {10     char c='+';int x=0;11     while(c<'0'||c>'9')c=getchar();12     while(c>='0'&&c<='9')13     x=x*10+(c-48),c=getchar();14     n=x;15 }16 struct node17 {18     int u,v,w,nxt;19 }edge[MAXN*5];20 int head[MAXN];21 int num=1;22 void add_edge(int x,int y,int z)23 {24     edge[num].u=x;25     edge[num].v=y;26     edge[num].w=z;27     edge[num].nxt=head[x];28     head[x]=num++;29 }30 int fa[MAXN*6];31 int n;32 inline int comp(const node &a ,const node & b)33 {34     return a.w<b.w;35 }36 inline int find(int x)37 {38     if(fa[x]!=x)39     return fa[x]=find;40     return fa[x];41 }42 inline void unionn(int x,int y)43 {44     int fx=find;45     int fy=find;46     fa[fx]=fy;47 }48 inline void kruskal()49 {50     int tot=0;51     int ans=0;52     sort(edge+1,edge+num,comp);53     for(int i=1;i<=num-1;i++)54     {55         int now=edge[i].u;int will=edge[i].v;56         if!=find57         {58             unionn;59             tot++;60             ans+=edge[i].w;61         }62         if(tot==n-1)63         break;64     }65     printf("%d",ans);66 }67 int main()68 {69     //freopen("agrinet.in","r",stdin);70     //freopen("agrinet.out","w",stdout);71     read;72     for(int i=0;i<=n;i++)73         fa[i]=i;74     for(int i=1;i<=n;i++)75         for(int j=1;j<=n;j++)76         {77             int x;78             read;79             if(x!=0)80             add_edge;81         }82     kruskal();83     return 0;84 }

  第二行..结尾: 后来的行满含了三个N*N的矩阵,表示每一个农场时期的相距。理论上,他们是N行,每行由N个用空格分隔的数组成,实际上,他们限制在76个字符,由此,某个行会紧接着另一些行。当然,对角线将会是0,因为不会有路经从第i个农场到它本身。

  • 输出

  独有二个输出,在那之中包涵连接到每一种农场的光导纤维的小小长度。

  • 思路

  笔者是用并查集加上贪心过的那道题( 本来问题就不是很难 ),在那之中值得注意的地点是由于输入的矩阵是关于对角线对称的,所以只用读入八分之四就好了。

落到实处代码

 1 #include <cstdio> 2 #include <algorithm> 3  4 using namespace std; 5  6 const int maxn = 200002; 7  8 struct node { 9     int st, ed, v;10 };11 node a[maxn];12 13 int f[maxn];14 15 bool cmp ( node a, node b) {16     return a.v < b.v;17 }18 19 int find ( int k ) {20     if ( k == f[k] )    return k;21     else {22         f[k] = find;23         return f[k];24     }25 }26 27 int main () {28     int n, index = 0;29     scanf ( "%d", &n );30     for ( int i = 1; i <= n; i ++ ) {31         for ( int j = 1; j <= n; j ++ ) {32             int k;33             scanf ( "%d", &k );34             if ( j > i ) {35                 index ++;36                 a[index].st = i; a[index].ed = j; a[index].v = k; 37             }   38         }39     }40     for ( int i = 1; i <= n; i ++ )    f[i] = i;41     sort ( a + 1, a + index + 1, cmp );42     int ans = 0, p = 1;43     for ( int i = 1; i <= index; i ++ ) {44         if ( find( a[i].st ) != find( a[i].ed ) ) {45             ans += a[i].v;46             f[find( a[i].st )] = a[i].ed;47             p ++;48             if     break; 49         }50     }51     printf ( "%d", &ans );52     return 0;53 }

本文由编程发布,转载请注明来源:最短网络