Chaos Slover 补档计划 - 弦图

2015.11.19 08:42 Thu| 5 visits oi_2016| ChaosSlover补档计划| Text

BZOJ1242 Zju1015 Fishing Net弦图判定

判定弦图的模板题,思路就是先按照完美消除序列的求法求出一个序列,然后检查求出的序列是否是完美消除序列。按照 CDQ 的说法,这是 O(n+m) 的算法,然而具体在实现上有难度啊……还要挂链什么的。

由于 M 一般情况下都会很大,那么大概用堆优化求也没什么大不了的吧……就像最短路一样……相信我,不会有人去卡 N*logN 的!

检验:设 {vi+1,…,vn} 中所有与vi相邻的点依次为 vj1, …, vjk。只需判断 vj1 是否与 vj2, …, vjk 相邻即可。然而这里好像也可以挂链……当然,网上的代码都用 set 存边或者用邻接矩阵判断。用邻接矩阵的时间复杂度确实是 O(n+m)。

挂链的话,就是从前往后遍历完美消除序列,对于点 vi,将 v2j, ..., vjk 都挂到 vi 上。然后遍历到 i 时,需要判断在 i 下面挂的东西都和它相连。这个可以扫两遍边表啊,在扫一遍链啊,就解决了。然而我并不准备去写。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 1005
#define M 2000005

int n, m, head[N], d[N], vis[N], p[N];
vector<int> v;
set<pair<int, int> > s;
priority_queue<pair<int, int> > q;

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void search(int s)
{
    q.push(make_pair(0, s));
    while (!q.empty())
    {
        int x = q.top().second, y = q.top().first; q.pop();
        if (d[x] != y) continue;
        vis[x] = true; v.push_back(x);
        for (int i = head[x]; i; i = edge[i].next)
            if (!vis[edge[i].to])
                q.push(make_pair(++d[edge[i].to], edge[i].to));
    }
}

bool check()
{
    for (int i = 1; i <= n; ++i)
    {
        int x = -1;
        for (int j = head[v[i]]; j; j = edge[j].next)
            if (p[edge[j].to] > p[v[i]])
                if (x == -1 || p[edge[j].to] < p[x])
                    x = edge[j].to;
        if (x == -1) continue;
        for (int j = head[v[i]]; j; j = edge[j].next)
            if (p[edge[j].to] > p[v[i]])
                if (edge[j].to != x
                    && s.find(make_pair(edge[j].to, x)) == s.end())
                    return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;
    for (int x, y, i = 1; i <= m; ++i)
    {
        scanf("%d%d", &x, &y);
        if (s.find(make_pair(x, y)) == s.end())
            add(x, y), add(y, x);
        s.insert(make_pair(x, y));
        s.insert(make_pair(y, x));
    }
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) search(i);
    v.push_back(0);
    reverse(v.begin(), v.end());
    for (int i = 1; i <= n; ++i)
        p[v[i]] = i;
    if (check()) puts("Perfect");
    else puts("Imperfect");
    return 0;
}

BZOJ1006 [HNOI2008]神奇的国度

结论:弦图的最小染色、最大独立集、最小团覆盖都可以按照完美消除序列从后往前贪心选择。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 10005
#define M 2000005

int n, m, head[N], d[N], vis[N], p[N], col[N];
vector<int> v;
priority_queue<pair<int, int> > q;

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[M];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void search(int s)
{
    q.push(make_pair(0, s));
    while (!q.empty())
    {
        int x = q.top().second, y = q.top().first; q.pop();
        if (d[x] != y) continue;
        vis[x] = true; v.push_back(x);
        for (int i = head[x]; i; i = edge[i].next)
            if (!vis[edge[i].to])
                q.push(make_pair(++d[edge[i].to], edge[i].to));
    }
}

int main()
{
    cin >> n >> m;
    for (int x, y, i = 1; i <= m; ++i)
    {
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) search(i);
    v.push_back(0);
    reverse(v.begin(), v.end());
    for (int i = n; i; --i)
    {
        int x = v[i];
        for (int j = head[x]; j; j = edge[j].next)
            p[col[edge[j].to]] = i;
        for (int c = 1; c <= n; ++c)
            if (p[c] != i) { col[x] = c; break; }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, col[i]);
    cout << ans << endl;
    return 0;
}