Happier233的博客

Codeforces Round #469D

发表于

题目链接 - Codeforces #469D

题目简述：

给出n个数据中心，把每天的时间分为h部分，每个数据中心有个更新时间hi(0≤hi≤h)h_i(0\leq h_i \leq h)。m个客户，每个客户的数据放在2个数据中心。
现在要调整尽量少的数据中心，让这些数据中心时间向后调整一个小时。如果2个数据中心的时间一致，则会发生风险，不允许这种情况的发生，问至少调整几个数据中心，并且输出是哪些。

题目思路：

这题分析之后，如果一个客户关联的两个数据中心u,vu,v，如果hu+1=hvh_u+1=h_v则拉一条u到vu到v的边，如果hv+1=huh_v+1=h_u则拉一条v到uv到u的边，(如果hi+1=hh_i+1=h则hi+1h_i+1视为0)。这样就产生了一个关联关系，每条边的源方向如果需要被选中，那么目的方向也必须被选中，图就建立起来了。
然后对着这个图跑Tarjan。如果要选择在上层的强连通分量，那么下层的必须要选，答案将会变大，所以只选择最底部的强连通分量。然后只需要在最底部的强连通分量里面选择一个元素最少的强连通分量，将这个强连通分量输出即可。

代码：

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// 巨菜的ACMer-Happier233

#include <bits/stdc++.h>

using namespace std;

//-----
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pw(x) (1ll << (x))
#define bt(x, k) (((x) >> k) & 1)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i, l, r) for(int i=(l);i<(r);++i)
#define per(i, l, r) for(int i=(r)-1;i>=(l);--i)
#define mst(t, v, n) memset(t, v, sizeof(decltype(*(t))) * (n))
#define sf(x) scanf("%d", &(x))
#ifndef ACM_LOCAL
#pragma GCC optimize(2)
#define endl '\n'
#endif

const int N = int(1e5 + 10);
const int M = int(2e5 + 10);
int a[N];
int n, m, h;

inline bool check(int u, int v) {
    return a[u] + 1 == a[v] || a[u] + 1 == a[v] + h;
}

int head[N], tot;
pii eg[M];

void addEdge(int u, int v) {
    eg[tot] = {v, head[u]};
    head[u] = tot++;
}

int dfn[N], low[N], st[N], belong[N], num[N];
bool inst[N];
int idx, top, scc;

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    st[top++] = u;
    inst[u] = true;
    for (int i = head[u]; i != -1; i = eg[i].second) {
        int v = eg[i].first;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inst[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    int v;
    if (dfn[u] == low[u]) {
        scc++;
        do {
            v = st[--top];
            inst[v] = false;
            belong[v] = scc;
            num[scc]++;
        } while (u != v);
    }
}

void work() {
    fill_n(dfn, n + 1, 0);
    fill_n(num, n + 1, 0);
    fill_n(inst, n + 1, false);
    idx = top = scc = 0;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            tarjan(i);
    }
}

bool g[N];

void solve() {
    while (cin >> n >> m >> h) {
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        tot = 0;
        fill_n(head, n + 1, -1);
        rep(i, 0, m) {
            int u, v;
            cin >> u >> v;
            if (check(u, v)) {
                addEdge(u, v);
            }
            if (check(v, u)) {
                addEdge(v, u);
            }
        }
        work();
        fill_n(g, n + 1, 0);
        for (int u = 1; u <= n; u++) {
            for (int i = head[u]; ~i; i = eg[i].second) {
                int v = eg[i].first;
                if (belong[u] == belong[v])continue;
                g[belong[u]] = true;
            }
        }
        int mn = -1;
        for (int i = 1; i <= scc; i++) {
            if (g[i]) continue;
            if (mn == -1 || num[i] < num[mn]) {
                mn = i;
            }
        }
        cout << num[mn] << endl;
        for (int i = 1, c = 0; i <= n; i++) {
            if (belong[i] == mn) {
                cout << i << " \n"[++c == num[n]];
            }
        }
    }
}

int main() {
#ifdef ACM_LOCAL
    freopen("./data/std.in", "r", stdin);
    // freopen("./data/std.out", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif

#ifdef ACM_LOCAL
    auto start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    auto end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}