*对prim算法、Kruskal算法不是很理解的请移步
http://blog.csdn.net/sm9sun/article/details/53256232 //并查集
http://blog.csdn.net/sm9sun/article/details/53257264 //Kruskal
http://blog.csdn.net/sm9sun/article/details/53258204 //prim
题目链接：
http://lx.lanqiao.cn/problem.page?gpid=T16
题目描述：
Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。
输入格式
第1行包含两个整数N和P。
接下来N行，每行包含一个整数Ci。
接下来P行，每行包含三个整数Sj, Ej和Lj。
输出格式
输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。
样例输入
5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
样例输出
176
数据规模与约定
5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。
首先这道题我们先用prim写一下
#include<stdio.h>#define inf 0xFFFFFFFint tk[10010]; //谈话时间 int z[10010]; //记录该牛的状态 int prim[10001][10001];int fmin(int a,int b){ return a<b?a:b;}int main(){int i,j,k,n,p;int s,e,l;int tm;while(~scanf("%d%d",&n,&p)){ tm=inf; for(i=1;i<=n;i++) //输入谈话时间及奶牛状态初始 { scanf("%d",&tk[i]); tm=fmin(tm,tk[i]); z[i]=0;}for(i=1;i<=n;i++) //所有的点初始 for(j=1;j<=n;j++)prim[i][j]=inf; for(i=1;i<=p;i++) //插入边 { scanf("%d%d%d",&s,&e,&l); prim[s][e]=prim[e][s]=l*2+tk[s]+tk[e];}z[1]=1;int sum=0;for(i=1;i<n;i++) //prim { int min=inf; int jj;for(j=1;j<=n;j++)if(!z[j]&&prim[1][j]<min){min=prim[1][j];jj=j;}sum+=min;z[jj]=1;for(k=1;k<=n;k++)prim[1][k]=fmin(prim[jj][k],prim[1][k]);}/* for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%d ",dp[i][j]); printf("\n"); } */ printf("%d\n",sum+tm);}return 0;}结果显而易见的
题目要求内存上限是256M，而我们的int[10000][10000]
那么显然，prim是不行的。那么我们再来用Kruskal试一下~
#include<stdio.h>#include<algorithm>using namespace std;#define inf 0xFFFFFFFint point[111111];int pre[111111];int n,p,sum;int fmin(int a,int b){ return a<b?a:b;}struct node{int x,y,w;} e[111111];int cmp(node a,node b){return a.w<b.w;}int find(int x){if(pre[x]==x)return x;int t = find(pre[x]);pre[x] = t;return t;}int main(){int i,j,tm = inf;scanf("%d%d",&n,&p);for(i = 1; i<=n; i++){scanf("%d",&point[i]);tm = fmin(tm,point[i]);pre[i] = i;}for(i = 1; i<=p; i++){scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);e[i].w = 2*e[i].w+point[e[i].x]+point[e[i].y];}sort(e+1,e+p+1,cmp);sum = 0;for(i = 1;i<=p;i++){int fx = find(e[i].x);int fy = find(e[i].y);if(fx!=fy){sum+=e[i].w;pre[fx] = fy;}}printf("%d\n",sum+tm);return 0;}
结果：
成功(*^__^*)
当然，如果就这么愉快的结束了，那么人生岂不是没有乐趣了~
256M的内存嘛，仅仅用了3M很浪费有木有~~~
所以……嘿嘿，我将两种算法稍微融合一下，也就是prim基础上，舍弃一些无用的点
即：prim[a][b]原来是a与b的权值，当ab没有边的时候，这些内存就不需要记录了
那么就将prim变成三维数组，我们假设
//prin_233[i][j][0]代表第i个牧场可连接的第j条路到达的牧场地点
//prin_233[i][j][1]代表其权值
然后……
#include<stdio.h>#define inf 0xFFFFFFFint tk[10010];int z[10010];int prin_233[10001][3333][2]; //233333333333笑尿 int Side[10010]; //i点拥有的边数 int o[10001]; //optimum，最终的最优解，可以认为是prim的第一行（列） int fmin(int a,int b){ return a<b?a:b;}//prin_233[i][j][0]代表第i个牧场可连接的第j条路到达的牧场地点//prin_233[i][j][1]代表其权值 int main(){int i,j,k,n,p;int s,e,l;int tm;while(~scanf("%d%d",&n,&p)){ tm=inf; for(i=1;i<=n;i++) { scanf("%d",&tk[i]); tm=fmin(tm,tk[i]); Side[i]=z[i]=0; o[i]=inf;} for(i=1;i<=p;i++) { scanf("%d%d%d",&s,&e,&l); prin_233[s][Side[s]][0]=e; prin_233[s][Side[s]][1]=l*2+tk[s]+tk[e]; Side[s]++; prin_233[e][Side[e]][0]=s; prin_233[e][Side[e]][1]=l*2+tk[s]+tk[e]; Side[e]++;}z[1]=1;int sum=0;for(i=0;i<Side[1];i++)o[prin_233[1][i][0]]=prin_233[1][i][1];for(i=1;i<n;i++){ int min=inf; int jj;for(j=1;j<=n;j++)if(!z[j]&&o[j]<min){min=o[j];jj=j;}sum+=min;z[jj]=1;for(k=0;k<Side[jj];k++)o[prin_233[jj][k][0]]=fmin(o[prin_233[jj][k][0]],prin_233[jj][k][1]);}printf("%d\n",sum+tm);}return 0;}
我们提交一下试一试
~~成功！！
再看一看Kruskal的跑分
哈哈，第四组数据完爆你Kruskal有木有！！！！就是这么6，
然而并没有神马卵用- - ....