本周的练习内容是最小生成树算法，所以今天这道题同样是用最小生成树的思想解决的，不同之处在于，这道题反其道而行之，求的最大生成树，看了网上的题解说本题用kruskal算法，降序排列即可，可是我还是比较偏爱prim算法，所以就还是用它来解决了，看一下题目：
http://poj.org/problem?id=2377
题意分析：Farmer John 雇佣Bessie来帮他假设一个网络，可是他是一个黑心的farmer，根本不打算付给Bessie工资，Bessie得知这个情况之后决定整他一下，把网络建成最贵的。（建设成最大生成树）。
思路分析：在基本的prim算法基础上，修改判断条件，每一次循环都找出mst数组中最大的那个元素，这样题目就解决了。
AC代码：
#include <iostream>
#include <string.h>
using namespace std;
#define inf 2000000
bool visit[1005];
int mst[1005];
int matrix[1005][1005];
void init(int n)
{memset(visit,0,sizeof(visit));memset(matrix,0,sizeof(matrix));
}
int prim(int matrix[1005][1005],int n)
{int ans=0;int sum=1;for(int i=1;i<=n;i++)mst[i] = matrix[1][i];visit[1] = 1;
// for(int i=1;i<=n;i++)
// cout<<mst[i]<<endl;for(int i=1;i<=n;i++){int index;int max=0;for(int j=1;j<=n;j++){// cout<<mst[j]<<endl;if(mst[j]>max&&visit[j]==0){max = mst[j];index = j;}} if(max==0)break;visit[index] = 1;sum++; // cout<<max<<endl;ans+=max;for(int j=1;j<=n;j++){if(!visit[j])mst[j] = mst[j]>matrix[index][j]?mst[j]:matrix[index][j];}} if(sum==n) return ans;else return -1;
}
int main()
{int n,m;int a,b,c;while(cin>>n>>m){init(n);for(int i=1;i<=m;i++){cin>>a>>b>>c;matrix[a][b] = matrix[b][a] = matrix[a][b]>c?matrix[a][b]:c;}
/* for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<matrix[i][j]<<" ";}cout<<endl;}*/cout<<prim(matrix,n)<<endl;}return 0;
}
好多次WA是因为忘了把调试时候的输出语句注释掉，所以还是要小心谨慎啊。
所有的成功都与坚持有关，继续努力，加油。