题目名称 831. [USACO 3.1] 最短网络
输入输出 agrinet.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarsywgz 于2012-07-03加入
开放分组 全部用户
提交状态
分类标签
USACO 最小生成树
分享题解
通过:295, 提交:415, 通过率:71.08%
GravatarLGLJ 100 0.000 s 0.00 MiB C++
Gravatarcool 100 0.000 s 0.00 MiB C++
Gravatarsyzhaoss 100 0.000 s 0.00 MiB C++
Gravatar魔笛 100 0.000 s 0.00 MiB C++
Gravatarユッキー 100 0.000 s 0.00 MiB C++
Gravatarnichengyan 100 0.000 s 0.00 MiB C++
Gravatarムラサメ 100 0.000 s 0.00 MiB C++
Gravatarlihaoze 100 0.000 s 0.00 MiB C++
Gravatar瑆の時間~無盡輪迴·林蔭 100 0.000 s 0.00 MiB C++
Gravatarmxr2022 100 0.000 s 0.00 MiB C++
本题关联比赛
暑期小训练题
关于 最短网络 的近10条评论(全部评论)
百题嘻嘻
Gravatar烟雨
2017-10-12 11:38 9楼
第一次写最小生成树!
GravatarWHZ0325
2017-10-11 22:02 8楼
脑抽了使用邻接表算....果然密集图还是邻接矩阵快
GravatarNemoAre
2016-11-03 10:17 7楼
与457题一样,用Prim读入邻接矩阵
Gravatar水墨青花
2016-02-18 15:05 6楼
都好快的说。。
GravatarVacaTionGOD
2015-09-29 13:46 5楼
100个点,最多5050条边,傻B呵呵的开了5000 ,,RE了一次。。。。
Gravatarstone
2015-08-13 20:23 4楼
水啊水
Gravatar一個人的雨
2015-04-08 16:51 3楼
研究了一下Kruskal。
用了一种效率很低的【不相交集合】处理的方法处理的。但是竟然还是那么快,堪比二叉堆+Prim,这。。。
下面给上效率较高[路径压缩]的并查集的Kruskal的写法。[可用按秩合并或路径压缩的启发式策略来优化]

/*
/*
DESIGNED BY CH
KRUSKAL+UFS
ON 2013/12/5 23:06
*/
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fi("agrinet.in");
ofstream fo("agrinet.out");
const int INF=0xffffff;
const int Len=100+10;
int A[Len][Len],F[Len],n;
vector<pair<int,pair<int,int> > >E;
void init();
void Kruskal();
void Uion(int,int);
int Find(int);
int main()
{
init();
Kruskal();
return 0;
}
void init(){int i,j;
fi>>n;
for(i=0;i<n;i++)for(j=0;j<n;j++)fi>>A[i][j];
for(i=0;i<n;i++)A[i][i]=INF,F[i]=i;
for(i=0;i<n;i++)for(j=0;j<i;j++)E.push_back(make_pair(A[i][j],make_pair(i,j)));
}
void Kruskal()
{
int Ans=0,sum=0,pos_S,pos_E;
sort(E.begin(),E.end());
while(sum<E.size())
{
pos_S=E[sum].second.first;pos_E=E[sum].second.second;
if(Find(pos_S)!=Find(pos_E)){
Ans+=A[pos_S][pos_E];
Uion(pos_S,pos_E);
}
sum++;
}
fo<<Ans;
}
void Uion(int x,int y){
F[Find(x)]=Find(y);
}
int Find(int x){
return F[x]==x?x:F[x]=Find(F[x]);
}
Gravatar超级傲娇的AC酱
2013-12-05 23:11 2楼
MST。介绍一下Prim吧。
根据题意,也不难理解什么是MST。
首先,MST具备以下2条重要的性质:
1.最优子结构;W(T)=W((u,v))+W(T1)+W(T2);(T1,T2为两棵子树,而(u,v)为连接这两棵树的边,即你切断的那条边)
2.重叠子结构;(最终均可化简至有限的相同的基本问题)
看似可以DP,但是,对于MST,不难发现还具备这条性质(其实是一个简单的定理):
若将图G(V,E)化成2个部分,A和G-A,则若存在边(u,v)∈E使得A与G-A联通,则E(Min)∈MST.
这条定理告诉我们MST具备“局部最优解同时也是全局最优解“的属性;
而具备该属性则说明存在某种贪心策略可以生成MST。
Prim算法就是用到了这条定理来完成的。其实它和迪杰斯特拉很像。对于邻接表储存的稀疏图,加上二叉堆后可大大提高算法的速度。
当然,用斐波那契堆优化可达到极为拔群的效果。
Gravatar超级傲娇的AC酱
2013-12-04 13:58 1楼

831. [USACO 3.1] 最短网络

★★   输入文件:agrinet.in   输出文件:agrinet.out   简单对比
时间限制:1 s   内存限制:128 MiB

题目描述

农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的场。当然,他需要你的帮助。

约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了用最小的消费,他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。

每两个农场间的距离不会超过100000。

输入格式

第一行:农场的个数,$N(3\leq N\leq 100)$。

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

输出格式

只有一个输出,其中包含连接到每个农场的光纤的最小长度。

输入样例

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

输出样例

28