NOIP 2010 关押罪犯 解题报告

两种方法，一种是并查集，另一种是排序+二分+二分图判定

并查集的方法是最简单的，不论是空间还是时间，都是最优的，但是不太好想到

 

排序+二分+二分图判定，比较容易在第一思路想到，但是实现就不如并查集那么简单，而且我动态建立图，然后超时最后一个点……

 

并查集做法：

总共只有两个集合，想一下这样的逻辑关系，a不和b在一起，a不和c在一起，那么b和c一定在一起

 

有什么想法吗？没错，我们可以对每个罪犯设置一个集合，每个罪犯的补集设置一个集合，通过不断维护着相互间的制约关系来进行判断，这时我们就可以用并查集来做到这一点

 

因为题目要求是最大的冲突，所以先将冲突值排序，从大到小依次解决，什么时候遇到了冲突，说明最大的冲突值就是他，这个贪心方法就不用证明的了吧，很显然的

程序代码如下：

 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

const int M = 100000;
const int N = 20000;

struct EDGE {
        int a;
        int b;
        int v;
} edge[M];

int f[N * 2];

bool Compare(const EDGE &a, const EDGE &b)
{
        return a.v < b.v;
}

int Find(int x)
{
        if (f[x] == x) {
                return f[x];
        } else {
                return f[x] = Find(f[x]);
        }
}

int main()
{
        int n, m;

        ios::sync_with_stdio(false);

        cin >> n;
        cin >> m;
        for (int i = 0; i < m; i++) {
                cin >> edge[i].a;
                cin >> edge[i].b;
                cin >> edge[i].v;
        }

        for (int i = 0; i < n * 2; i++) {
                f[i] = i;
        }

        sort(edge, edge + m, Compare);

        for (int i = m - 1; i >= 0; i--) {
                int x = Find(edge[i].a);
                int y = Find(edge[i].b);

                if (x == y) {
                        cout << edge[i].v << endl;

                        return 0;
                }

                int xx = Find(edge[i].a + n);
                int yy = Find(edge[i].b + n);

                f[x] = yy;
                f[y] = xx;
        }

        cout << "0" << endl;

        return 0;
}

排序+二分+二分图判定做法：

首先，我承认自己这个方法没有AC，因为我动态建图，开销比较大，最后一个点超时，比并查集慢得多……

 

说一下大体思路吧，因为是求最大值最小的问题，所以可以采用二分的方法来查找最优值，当然，前提是将冲突值排序。

 

在二分的时候，选定一个[left_border,right_border]范围内的中间冲突值，然后将所有大于等于该冲突的两个罪犯之间连一条边，代表他们不能在一起

 

建图建好后，然后用BFS进行二分图判定，具体见下面代码中的BinaryGraphJudge()，这里需要注意一下，由于建好后的图可能不连通，所以需要额外加一个visited_vertex变量来记录已经扩展了多少个点，如果在还没有扩展完的情况下队列里面就已经空了，那么就再选取一个没有被扩展过的点加入队列，继续进行BFS，直到visited_vertex == n就可以退出了

 

我感觉这里的二分是一个挑战，至少对我来说，可能大牛们对此已经不屑了，但是我感觉边界问题很难处理，详情可以看一下《编程珠玑》里的第四章——编写正确的程序

 

在下面这个程序里，在进行二分的时候，我能够保证的就是[right_border, m]里的所有冲突值都是可以避免的，[0, left_border)里的冲突值都是不能避免的（注意区间的开闭），最后，当left_border == right_border时，我可以确定left_border - 1就是我所需要的那个满足要求的冲突值最大的罪犯的编号

 

这里说一下people[0]的问题，输入的数据全部存储在people[1] ~ people[m]中，而这个people[0]就是可能的无解情况，虽然这个题里的数据没有0的情况，但我觉得应该考虑一下，所以，将people[0]的冲突值设为0，这样，当将题目中的关系全部满足后，仍然是个二分图的话，那么结果将是left_border == right_border == 1（不考虑语法问题…），所以将返回0，最后输出的也就是0

 

程序代码如下：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>

const int kMaxN = 20000 + 1;
const int kMaxM = 100000 + 1;
const int kInf = 0x7FFFFFFF;

typedef struct graph *Graph;
typedef struct node *Link;
typedef struct edge Edge;
struct graph {
        int V;
        int E;
        Link *adj;
};
struct node {
        int v;
        int len;
        Link next;
};
struct edge {
        int v;
        int w;
        int len;
};

struct prison {
        int v;
        int w;
        int len;
} people[kMaxM];

int n, m;

inline Graph GraphBuild(int v) {
        Graph t = (Graph)malloc(sizeof *t);

        t->V = v;
        t->E = 0;
        t->adj = (Link *)malloc((v + 1) * sizeof(Link));
        for (int i = 0; i <= v; i++) {
                t->adj[i] = NULL;
        }

        return t;
}

inline void GraphReset(Graph& G) {
        G->E = 0;
        for (int i = 0; i <= G->V; i++) {
                G->adj[i] = NULL;
        }
}

inline Link NewEdge(int v, int len, Link next) {
        Link t = (Link)malloc(sizeof *t);

        t->v = v;
        t->len = len;
        t->next = next;

        return t;
}

inline Edge EdgeNew(int v, int w, int len) {
        Edge e;

        e.v = v;
        e.w = w;
        e.len = len;

        return e;
}

inline void GraphInsert(Graph &G, Edge e) {
        int v = e.v;
        int w = e.w;
        int len = e.len;

        G->adj[v] = NewEdge(w, len, G->adj[v]);
        G->adj[w] = NewEdge(v, len, G->adj[w]);
        G->E++;
}

inline bool BinaryGraphJudge(Graph &G) {
        std::queue<int> q;
        bool visited[kMaxN];
        int vertex_color[kMaxN];
        int visited_vertex = 0;

        memset(visited, false, sizeof(visited));
        memset(vertex_color, -1, sizeof(vertex_color));

        q.push(1);
        vertex_color[1] = 1;
        while (visited_vertex < G->V) {
                if (q.empty()) {
                        for (int i = 1; i <= G->V; i++) {
                                if (!visited[i]) {
                                        q.push(i);
                                        break;
                                }
                        }
                }

                while (!q.empty()) {
                        int now;
                        Link t;

                        now = q.front();
                        q.pop();
                        visited[now] = true;
                        visited_vertex++;
                        for (t = G->adj[now]; t != NULL; t = t->next) {
                                if (vertex_color[t->v] == -1 || vertex_color[t->v] == 3 - vertex_color[now]) {
                                        vertex_color[t->v] = 3 - vertex_color[now];
                                } else {
                                        return false;
                                }

                                if (!visited[t->v]) {
                                        q.push(t->v);
                                }
                        }
                }
        }

        return true;
}

inline void AddGraph(Graph &G, int mid_border) {
        GraphReset(G);

        for (int i = mid_border; i <= m; i++) {
                GraphInsert(G, EdgeNew(people[i].v, people[i].w, people[i].len));
        }
}

inline int BinarySearch(Graph &G, int left_border, int right_border) {
        int mid_border;

        while (left_border < right_border) {
                mid_border = (left_border + right_border) / 2;

                AddGraph(G, mid_border);

                if (BinaryGraphJudge(G)) {
                        right_border = mid_border;
                } else {
                        left_border = mid_border + 1;
                }
        }

        return left_border - 1;
}

bool compare(const prison &a, const prison &b) {
        return a.len < b.len;
}

int main()
{
        int v, w, len;
        int ans;
        Graph G;

        std::ios::sync_with_stdio(false);
        std::cin >> n;
        std::cin >> m;

        G = GraphBuild(n);

        people[0].v = -1;
        people[0].w = -1;
        people[0].len = 0;
        for (int i = 1; i <= m; i++) {
                std::cin >> v >> w >> n;
                people[i].v = v;
                people[i].w = w;
                people[i].len = len;
        }

        std::sort(people, people + 1 + m, compare);

        ans = BinarySearch(G, 0, m);
        std::cout << people[ans].len << std::endl;

        return 0;
}