P1525 关押罪犯【二分+二分图】

输入输出样例

输入 #1

思路

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

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

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

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

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

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

　　白嫖了一组数据

　　in.txt

　　2 1
　　1 2 28135

　　out.txt

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e5 + 7;
 47 
 48 int cnt,n,m;
 49 int head[maxn << 1], edge[maxn << 1], nxt[maxn << 1];
 50 int w[maxn << 1], color[maxn];
 51 
 52 void BuildGraph(int u, int v, int c) {
 53     cnt++;
 54     edge[cnt] = v;
 55     nxt[cnt] = head[u];
 56     w[cnt] = c;
 57     head[u] = cnt;
 58 }
 59 
 60 bool check(int x) {
 61     queue <int> q;
 62     memset(color, 0, sizeof(color));
 63     for ( int j = 1; j <= n; ++j ) {
 64         //dbg(j);
 65         if(color[j])
 66             continue;
 67         else {
 68             q.push(j);
 69             color[j] = 1;
 70             while(!q.empty()) {
 71                 int u = q.front();
 72                 q.pop();
 73                 //dbg(u);
 74                 for (int i = head[u]; i; i = nxt[i]) {
 75                     int v = edge[i];
 76                     if(w[i] >= x) {
 77                         if(!color[v]) {
 78                             color[v] = (color[u] == 1 ? 2 : 1);
 79                             q.push(v);
 80                         }
 81                         else if(color[v] == color[u]) {
 82                             return false;
 83                         }
 84                     }
 85                 }
 86             }
 87         }
 88     }
 89     return true;
 90 }
 91 
 92 int main()
 93 {
 94     read(n);
 95     read(m);
 96     int maxx = 0;
 97     for ( int i = 1; i <= m; ++i ) {
 98         int u, v, c;
 99         read(u);
100         read(v);
101         read(c);
102         BuildGraph(u,v,c);
103         BuildGraph(v,u,c);
104         maxx = max(maxx, c);
105     }
106 
107     int l = 0, r = maxx;
108     int mid = (l + r) >> 1;
109 
110     while(l <= r) {
111         mid = (l + r) >> 1;
112         //dbg(mid);
113         if(check(mid)) {
114             r = mid - 1;
115         }
116         else {
117             l = mid + 1;
118         }
119     }
120     if(l-1 < 0)
121         l = 1;
122     cout << l - 1 << endl;
123     return 0;
124 }

View Code

void dfs(int u, bool s) {
    visited[u] = true;
    side[u] = s;
    for(int v : edges[u]) {
        if(visited[v]) continue;
        dfs(v, !s);
    }
}

int main() {
    std::scanf("%d", &n);
    for(int i = 0; i < n - 1; ++i) {
        int u, v;
        std::scanf("%d%d", &u, &v);
        --u, --v;
        edges[u].push_back(v);
        edges[v].push_back(u);
        mat[u][v] = mat[v][u] = true;
    }

    dfs(0, false);

    int c1 = 0;
    for(int i = 0; i < n; ++i)
        c1 += side[i];
    if(c1 > n / 2)
        for(int i = 0; i < n; ++i)
            side[i] = !side[i];

    int cnt = 1;
    for(int i = 0; i < n; ++i) {
        if(!side[i]) continue;
        result[i] = MASK ^ (i64(1) << cnt) ^ 1;
        for(int v : edges[i])
            result[v] |= (i64(1) << cnt) | 1;
        ++cnt;
    }

    /*for(int i = 0; i < n - 1; ++i)
        for(int j = i + 1; j < n; ++j)
            if(mat[i][j] != ((result[i] | result[j]) == MASK))
                std::cout << "Error: " << i << ' ' << j << std::endl;*/

    for(int i = 0; i < n; ++i)
        std::cout << result[i] << std::endl;
}