[二分答案/二分图]图1-2018级算法C5-B题解

发表于 | 分类于 | 热度: 度

题目链接

这道题如果硬求 $\rm max$$(S_A,S_B)$ 将会变得很复杂，分析题面可知，权值大于答案的边都被割掉后该图便会有两个以上的连通分量，反过来，如果割掉所有权值小于等于答案的边，该图将变成一个二分图；如果扩大 $\rm max$$(S_A,S_B)$，仍然可以满足题意，但如果缩小 $\rm max$$(S_A,S_B)$，割掉所有权值小于等于答案的边，该图仍然不是一个二分图。所以答案具有单调性，可以考虑利用二分答案枚举出所有答案，验证割掉所有权值小于等于答案的边后，该图能不能仍然是一个二分图，同时取满足该条件的最小答案为最终答案。判断二分图的时间复杂度为 $O(M+N)$，二分的时间复杂度为$O(logc)$，总时间复杂度为 $O((M+N)log c)$

代码如下：

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = (20000 << 1) + 5;
const int M = (100000 << 1) + 5;

struct Edge {
    int from, to, weight, nowWeight, nex;

    Edge() {}
    Edge(int _from, int _to, int _weight, int _nowWeight, int _nex) : from(_from), to(_to), weight(_weight), nowWeight(_nowWeight), nex(_nex) {} // Edge 的构造函数

    void edge_init() { nowWeight = weight; } // 还原 Edge 到未被割的状态
    void change(int S) { nowWeight = weight <= S ? INF : S; } // 如果权值小于等于 S，权值设为 INF，视为被割
};

vector<Edge> edges;
int head[N], cnt;
int len[M], color[N];

void addEdge(int, int, int);
void init(int);
bool dfs(int, int);
bool judge(int, int);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, a, b, c;
    cin >> n >> m;

    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        addEdge(a, b, c);
        addEdge(b, a, c);
        len[i] = c;
    }
    sort(len + 1, len + 1 + m); // 对所有边的权值排序，构成答案区间

    int l = 1, r = m, mid;

    while (l <= r) {
        init(m);
        mid = (l + r) >> 1;
        bool flag = judge(len[mid], n);
        if (!flag)
            l = mid + 1;
        else
            r = mid - 1;
    }

    cout << len[l] << endl;

    return 0;
}


void addEdge(int a, int b, int c) {
    edges.push_back(Edge(a, b, c, 0, head[a]));
    head[a] = cnt;
    cnt++;
}

void init(int m) {
    for (int i = 0; i < cnt; i++)
        edges[i].edge_init();
    memset(color, 0, sizeof(color));
} // 每次判断答案正确性时的初始化

bool dfs(int node, int c) {
    color[node] = c;
    for (int i = head[node]; i != -1; i = edges[i].nex) {
        int v = edges[i].to;

        if (edges[i].nowWeight != INF) {
            if (color[v] == c)
                return false;
            if (!color[v] && !dfs(v, -c))
                return false;
        }
    }

    return true;
} // dfs 染色判断二分图

bool judge(int S, int n) {
    for (int i = 0; i < cnt; i++)
        edges[i].change(S);

    for (int i = 1; i <= n; i++)
        if (!color[i])
            if (!dfs(i, 1))
                return false;

    return true;
} // 判断是否为二分图