这题的话，就是贪心，把最大的罪恶值的两个囚犯都不关在一个牢房里，反复的贪心，但是数据太大，不允许使用邻接表和邻接矩阵，用什么结构来保存呢？我觉得（也是网上的资料里的咯）使用动态分配是个方法，因为最多10000条边，根据实际情况来分配，这样不会有浪费的空间，也就不会导致空间爆掉了。
#include <stdlib.h>
int m, n;
struct list{
int a, b, v;
}list[100001];
struct link{
int b;
struct link next;
}head[20000];
int color[20000];
int nowco = 1;
int com(const void
a, const void b){
return ((struct list)b)->v – ((struct list)a)->v;
}
void add(int a, int b)
{
struct link
p = malloc(sizeof(struct link));
p->b = b;
p->next = head[a].next;
head[a].next = p;
}
int other_color(int c)
{
if(c & 1){
return c + 1;
}
return c – 1;
}
int min(int a, int b)
{
return a > b ? b : a;
}
void dfs(int a)
{
struct link i;
for(i = head[a].next; i != NULL; i = i->next){
if((color[i->b] – color[a] >= –1) && (color[i->b] – color[a] <= 1) &&
(min(color[i->b], color[a]) & 1)){
continue;
}
color[i->b] = other_color(color[a]);
dfs(i->b);
}
}
#define d(a) #a
int main(void)
{
int i, j;
struct link p;
int a, b;
freopen("prison"d(5)".in", "r", stdin);
scanf("%d%d", &n, &m);
for(i = 0; i < m; i++){
scanf("%d%d%d", &list[i].a, &list[i].b, &list[i].v);
list[i].a–, list[i].b–;
}
qsort(list, m, sizeof(struct list), com);
for(i = 0; i < m; i++){
a = list[i].a;
b = list[i].b;
add(a, b);
add(b, a);
if(color[a] == 0 || color[b] == 0){
color[a] = nowco++;
color[b] = nowco++;
continue;
}else if(color[a] == 0){
color[b] = other_color(color[a]);
continue;
}else if(color[b] == 0){
color[a] = other_color(color[b]);
continue;
}
if(color[a] == color[b]){
break;
}
dfs(b);
}
printf("%d\n", list[i].v);
getch();
return 0;
}