输入 #1 复制

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

思路

对于要求最大值最小的问题，不难想到二分。

在本题中，我们需要在 0 ~ 事件影响力的最大值 的范围内进行二分。

确定了边界之后，就应该着手于写check函数。

通过阅读题意可知，犯人之间有怨气值，相当于P3386之间的仰慕值，有两个监狱可以关押犯人，不在同一个监狱里的犯人不会干架。

不难由此想到二分图的作用，把犯人分割成两个集合即可。

对于此题来说，我们只要判定当前这个 mid 能不能使这张图被染色成一张 二分图 即可。

白嫖了一组数据

in.txt

2 1 　　1 2 28135

out.txt

0

CODE

#include
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0)

using namespace std;
typedef long long LL;

templateinline void read(T &res)
{
char c;T flag=;
while((c=getchar())<''||c>'')if(c=='-')flag=-;res=c-'';
while((c=getchar())>=''&&c<='')res=res*+c-'';res*=flag;
}

namespace _buff {
const size_t BUFF = << ;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
if (ib == ie) {
ib = ibuf;
ie = ibuf + fread(ibuf, , BUFF, stdin);
}
return ib == ie ? - : *ib++;
}
}

int qread() {
using namespace _buff;
int ret = ;
bool pos = true;
char c = getc();
for (; (c < '' || c > '') && c != '-'; c = getc()) {
assert(~c);
}
if (c == '-') {
pos = false;
c = getc();
}
for (; c >= '' && c <= ''; c = getc()) {
ret = (ret << ) + (ret << ) + (c ^ );
}
return pos ? ret : -ret;
}

const int maxn = 1e5 + ;

int cnt,n,m;
int head[maxn << ], edge[maxn << ], nxt[maxn << ];
int w[maxn << ], color[maxn];

void BuildGraph(int u, int v, int c) {
cnt++;
edge[cnt] = v;
nxt[cnt] = head[u];
w[cnt] = c;
head[u] = cnt;
}

bool check(int x) {
queue q;
memset(color, , sizeof(color));
for ( int j = ; j <= n; ++j ) { //dbg(j); if(color[j]) continue; else { q.push(j); color[j] = ; while(!q.empty()) { int u = q.front(); q.pop(); //dbg(u); for (int i = head[u]; i; i = nxt[i]) { int v = edge[i]; if(w[i] >= x) {
if(!color[v]) {
color[v] = (color[u] == ? : );
q.push(v);
}
else if(color[v] == color[u]) {
return false;
}
}
}
}
}
}
return true;
}

int main()
{
read(n);
read(m);
int maxx = ;
for ( int i = ; i <= m; ++i ) {
int u, v, c;
read(u);
read(v);
read(c);
BuildGraph(u,v,c);
BuildGraph(v,u,c);
maxx = max(maxx, c);
}

 int l = , r = maxx;  
 int mid = (l + r) >> ;

 while(l <= r) {  
     mid = (l + r) >> ;  
     //dbg(mid);  
     if(check(mid)) {  
         r = mid - ;  
     }  
     else {  
         l = mid + ;  
     }  
 }  
 if(l- < )  
     l = ;  
 cout << l -  << endl;  
 return ;  

}