洛谷 P1525 关押罪犯(二分 + 二分图判定)
程序员文章站
2022-07-05 18:32:12
...
思路:
脑子不是很清醒。。。
有两个*关这些犯人,然后如果两个有矛盾的范围关在同一个*就会产生影响,现在让你输出最大影响的最小值是是多少。
我们二分答案:最大影响值,也就是说大于这个最大值的犯人肯定会被关在两个不同的*,我们在大于的两个犯人之间连一条边,这两个犯人肯定会属于不同的两个*(点集),如果可行,那么肯定会形成一个二分图,所以我们用染色法判断是否为二分图从而判断方案是否可行。
struct Edge{
int next;
int to;
int dis;
}edge[N<<1];
int head[N<<1],tot;
inline void add(int from,int to,int dis){
edge[++tot].next = head[from];
edge[tot].to = to;
edge[tot].dis = dis;
head[from] = tot;
}
int color[N];
bool dfs(int x,int d){
bool r = 1;
for(int i = head[x];i;i = edge[i].next){
int y = edge[i].to;
int dis = edge[i].dis;
if(dis > d){
if(color[y] == 0) {color[y]=color[x]==1?2:1;r = dfs(y,d);if(r==0) return false;}
else if(color[y] == color[x]) return false;
}
}
return true;
}
bool ok(int m,int n){
memset(color,0,sizeof color);
rep(i,1,n){
if(!color[i]) {
color[i] = 1;
bool r = dfs(i,m);
if(r == 0) return false;
}
}
return true;
}
int main(){
int l(0),r(0);
int n = read(),m = read();
rep(i,1,m){
int u = read(),v = read(),d = read();
add(u,v,d);
add(v,u,d);
r = max(r,d);
}
while(l < r){
int mid = l + r >> 1;
if(ok(mid,n)) r = mid;
else l = mid + 1;
}
cout << r;
}