Gravatar
烟雨
积分:984
提交:243 / 356
百题嘻嘻

Gravatar
WHZ0325
积分:1233
提交:347 / 532
第一次写最小生成树!

Gravatar
NemoAre
积分:96
提交:69 / 230
脑抽了使用邻接表算....果然密集图还是邻接矩阵快

Gravatar
水墨青花
积分:212
提交:100 / 316
与457题一样,用Prim读入邻接矩阵

Gravatar
VacaTionGOD
积分:301
提交:144 / 265
都好快的说。。

Gravatar
stone
积分:1533
提交:406 / 764
100个点,最多5050条边,傻B呵呵的开了5000 ,,RE了一次。。。。

Gravatar
一個人的雨
积分:2070
提交:546 / 1090
水啊水

Gravatar
超级傲娇的AC酱
积分:646
提交:244 / 660
研究了一下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酱
积分:646
提交:244 / 660
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算法就是用到了这条定理来完成的。其实它和迪杰斯特拉很像。对于邻接表储存的稀疏图,加上二叉堆后可大大提高算法的速度。
当然,用斐波那契堆优化可达到极为拔群的效果。