(luogu1525) 关押罪犯 (NOIp2010T3)

发表于 分类于 ， ，

题目描述:

略

思路:

二分答案 + 二分图判定

求最值首先考虑二分答案

每次二分冲突最大值，然后用大于此值的边建图，判断此图是否为二分图

若是，则说明这些边不会在答案中，最大值可能更小；若否， 则需要扩大最大值

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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;
}