现有若干危险品需要放置在A,B两个仓库。当两种特定的危险品放置在相同地点时即可能产生危险。我们用危险系数αi,j表示危险品i,j放置在一起的危险程度。一些危险品即使放置在一起也不会产生任何危险，此时αi,j=0，还有一些危险品即使单独放置也会产生危险，此时αi,i>0。定义两个仓库整体的危险系数为max(maxi,j∈Aαi,j,maxi,j∈Bαi,j)，即放置在一起的所有危险品两两组合的危险系数的最大值。现在对于一组给定的危险系数，需要设计方案使得整体危险系数最小。
输入共m+1行。 第一行两个整数n和m表示共有n种危险品，危险品之间的危险组合（危险系数非零的物品组合）共m种。接下来的m行，每行三个整数i,j,αij表示(i,j)为危险组合（i,j可能相等），其危险系数为αi,j>0。
数据规模 0<n≤100,000 0<m≤1,000,000
输出共一行，包含一个整数，表示整体危险系数的最小值。
3 3
1 2 4
2 3 3
1 3 2
2
/*
将1,3放在A仓库，2放在B仓库
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 1e6;
int n, m;
int e ;
int res;
bool NonFlag[N + 1];
int UpPoint[N + 1];
struct Couple
{
int i;
int j;
int w;
} dcoup[M + 1];
struct Point
{
int set;
bool Flag;
} Point[N + 1];
int Compare(const Couple &x, const Couple &y)
{
return x.w < y.w;
}
bool noFlag(int s)
{
if (s != UpPoint[s])
NonFlag[s] ^= noFlag(UpPoint[s]);
return NonFlag[s];
}
bool pola(int x)
{
return (noFlag(Point[x].set) ^ Point[x].Flag);
}
int find(int s)
{
if (s != UpPoint[s])
{
UpPoint[s] = find(UpPoint[s]);
NonFlag[s] ^= NonFlag[UpPoint[s]];
}
return UpPoint[s];
}
int Set(int x)
{
return find(Point[x].set);
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> dcoup[e].i >> dcoup[e].j >> dcoup[e].w;
if (dcoup[e].i != dcoup[e].j)
e++;
else if (dcoup[e].w > res)
res = dcoup[e].w;
}
sort(dcoup, dcoup + e, Compare);
for (int i = 0; i <= n; i++)
UpPoint[i] = i;
int sets = 0;
for (e = e-1; e >= 0; e--)
{
if (Point[dcoup[e].i].set == 0)
{
if (Point[dcoup[e].j].set == 0)
{
sets++;
Point[dcoup[e].i].set = sets;
Point[dcoup[e].i].Flag = dcoup[e].i < dcoup[e].j;
Point[dcoup[e].j].set = sets;
Point[dcoup[e].j].Flag = dcoup[e].i >= dcoup[e].j;
}
else
{
Point[dcoup[e].i].Flag = !pola(dcoup[e].j);
Point[dcoup[e].i].set = Set(dcoup[e].j);
}
}
else
{
if (Point[dcoup[e].j].set == 0)
{
Point[dcoup[e].j].Flag = !pola(dcoup[e].i);
Point[dcoup[e].j].set = Set(dcoup[e].i);
}
else
{
int i_flag = pola(dcoup[e].i);
int j_flag = pola(dcoup[e].j);
int is = Set(dcoup[e].i);
int js = Set(dcoup[e].j);
if (js == is)
{
if (i_flag == j_flag)
break;
}
else
{
if (i_flag == j_flag)
{
if (is < js)
{
NonFlag[js] ^= 1;
UpPoint[js] = is;
}
else
{
NonFlag[is] ^= 1;
UpPoint[is] = js;
}
}
else
{
if (is < js)
UpPoint[js] = is;
else
UpPoint[is] = js;
}
}
}
}
}
if(dcoup[e].w > res)
cout <<dcoup[e].w;
else
cout<<res;
return 0;
}
