(luogu1525)关押罪犯(NOIp2010T3) 发表于 2017-11-08 | 分类于 solution , 图论 , 二分图 题目描述:略 思路:二分答案+二分图判定 求最值首先考虑二分答案 每次二分冲突最大值, 然后用大于此值的边建图, 判断此图是否为二分图 若是, 则说明这些边不会在答案中, 最大值可能更小; 若否, 则需要扩大最大值 代码:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <iostream>#include <cstdio>#include <cstring>#include <cctype>#include <algorithm>using namespace std;const int Mn(20005);const int Mm(200005);int qrd() //快读{ int x(0); char c(getchar()); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } return x;}struct edge{ int e,v,nt;}E[Mm];int v[Mn]; //边表int cnt(0);void adde(int s,int e,int d) //加边{ E[++cnt].e=e, E[cnt].v=d; E[cnt].nt=v[s]; v[s] = cnt;}int isv[Mn]; //判断是否被染色, 0表示未染色, 1/-1为两种颜色bool chk(int x,int d,int col) //判定函数{ isv[x]=col; for(int e(v[x]);e;e=E[e].nt) if(E[e].v>d) //只计算边权大于二分值的边 { if(!isv[E[e].e]) { if(!chk(E[e].e,d,-col)) return false; } else if(isv[E[e].e]==isv[x]) return false; } return true;}int main(){ int n,m; cin >> n >> m; int mxz(0); while(m--) { int x(qrd()),y(qrd()),z(qrd()); adde(x,y,z); adde(y,x,z); mxz = max(mxz,z); } int l(0),r(mxz); while(l<=r) //二分答案 { int mid((l+r)>>1); memset(isv,0,sizeof isv); int isc(true); for(int i(1);i<=n;++i) //判定是否为二分图 if(!isv[i] && !chk(i,mid,1)) { isc=false; break; } if(isc) r=mid-1; else l=mid+1; } cout << l; return 0;}