学习最小割的时候，要用到prim的最大生成树思想，于是找了到最大生成树的题目，做的试试
分别用了kruskal和prim试了下
kruskal很好想，排序的时候反过来就可以了，即，边的权值从最大向最小排列即可，最后判断下是否连通了
而关于kruskal，我想了一下，按照原先的贪心思想，用两个集合A,B表示，A是已经连入的点，
B是未连入的点这样，可以假设A与B分别是全连通（因为最总会变成一个最小生成树），这样，
就只用每次找链接A与B间的最大权值，因为此时A，B已经是全连通了，就差一条边，只用取
最大。每次对A缩点，对每条边进行这样的贪心就可以得到最大生成树了
PS：注意prim的重边处理（我记得处理重边，却忘了是找两点重边中最大的边，做最小习惯了……）
code:
/*
kruskal
2011-8-14
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <queue>
#include <vector>
#include <stack>
#define nMax 1005
#define mMax 20005
using namespace std;
int father[nMax], rank[nMax];
int n, m;
struct Edge
{
int u, v, w;
}edge[mMax];
void makeset(int n)
{
for(int i=0; i<=n; i++)
{
father[i]=i;
rank[i]=0;
}
}
int findset(int x)
{
int r=x;
while(r!=father[r])
r=father[r];
int temp;
while(x!=r)
{
temp=father[x];
father[temp]=r;
x=temp;
}
return r;
}
void Union(int x, int y)
{
x=findset(x);
y=findset(y);
if(x==y) return ;
if(rank[x]>rank[y])
father[y]=x;
else
father[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
bool cmp(Edge a,Edge b)
{
return a.w>b.w;
}
int main()
{
int num, ans;
while(scanf("%d%d", &n, &m)!=EOF)
{
makeset(n);
for(int i=0; i<m; i++)
{
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
}
sort(edge, edge+m, cmp);
num=ans=0;
for(int i=0; i<m; i++)
{
int fx=findset(edge[i].u);
int fy=findset(edge[i].v);
if(fx!=fy)
{
ans+=edge[i].w;
num++;
Union(fx, fy);
}
if(num==n-1) break;
}
if(num!=n-1)
printf("-1\n");
else
printf("%d\n", ans);
}
return 0;
}
/*
prim
2011-8-15
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <queue>
#include <vector>
#include <stack>
#define nMax 1005
using namespace std;
bool used[nMax];
int dist[nMax], map[nMax][nMax];
int n, m;
void Prim()
{
int i, j;
int sum = 0;
memset(dist,0,sizeof(dist));
memset(used,0,sizeof(used));
//以v0为起点
for (i = 0; i < n; i++)
dist[i] = map[0][i];
used[0] = 1;
for (j = 1; j <= n - 1; j++)//重复n-1次
{
int index = -1;
int min_d = 0;//INT_MAX
for (i = 0; i < n; i++)
if (!used[i] && dist[i] > min_d)
{
min_d = dist[i];
index = i;
}
if (index != -1)
{
dist[index] = min_d;
used[index] = 1;
sum += min_d;
for (i = 0; i < n; i++)
if (!used[i] && map[index][i] > dist[i])
{
dist[i] = map[index][i];
}
}
}
for(i=0; i<n; i++) //判断全树是否形成
{
if(used[i]==0) break;
}
if(i==n) printf("%d\n",sum);
else printf("-1\n");
}
int main()
{
while(scanf("%d%d", &n, &m)!=EOF)
{
int x, y, z;
memset(map, 0, sizeof(map));
for(int i=0; i<m; i++)
{
scanf("%d%d%d", &x, &y, &z);
x--;
y--;
map[x][y]=max(z, map[x][y]);
map[y][x]=map[x][y];
}
Prim();
}
return 0;
}