Main » 2013 October 12 » [NOIP2011模拟赛_No.12]LJ与HDJ
6:13 AM [NOIP2011模拟赛_No.12]LJ与HDJ |
krustal最小生成树#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 100100 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int f[N],t[N],n,m; struct node{int x,y,E;}; int cmp(node a,node b){return a.E<b.E;} node e[N]; int getf(int x) { if (f[x]!=x) f[x]=getf(f[x]); return f[x]; } int main() { scanf("%d%d",&n,&m); int i; FOR(i,1,n) f[i]=i; int ans=2e9; FOR(i,1,n) {scanf("%d",&t[i]);ans=min(ans,t[i]);} FOR(i,1,m) { scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].E); e[i].E=2*e[i].E+t[e[i].x]+t[e[i].y]; } sort(e+1,e+1+m,cmp); FOR(i,1,m) { int fx=getf(e[i].x),fy=getf(e[i].y); if (fx==fy) continue; ans+=e[i].E; f[fx]=fy; } printf("%d\n",ans); } |
|
|
| Total comments: 0 | |