记录编号	114538	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.120 s
提交时间	2014-07-31 15:13:27	内存使用	1.62 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct fights
{
  int f,t,l;
  bool operator <(const fights i) const
  {
    return l<i.l;
  }
};
//==============var declaration=================
int n;
int root[20100*2];
fights fight[100100];
char ch[20];
//==============function declaration============
void cross(int a,int b);
int findr(int x);
//==============main code=======================
int main()
{  
  freopen("prison1.in","r",stdin);
  freopen("prison1.out","w",stdout); 
  int n,q;
  scanf("%d%d",&n,&q);
  For(i,1,q)
    scanf("%d%d%d",&fight[i].f,&fight[i].t,&fight[i].l);
  sort(fight+1,fight+1+q);
  For(i,1,n*2)
    root[i]=i;
  for(int now=q;now>=1;now--)
  {
    if (findr(fight[now].f)==findr(fight[now].t))
    {
      printf("%d\n",fight[now].l);
      return 0;
    }
    cross(fight[now].f,fight[now].t+n);
    cross(fight[now].f+n,fight[now].t);
  }
  pritnf("0\n");
  return 0;
}
//================fuction code====================
void cross(int a,int b)
{
  root[findr(a)]=findr(b);
}
int findr(int x)
{
  return root[x]==x?x:root[x]=findr(root[x]);
}