\(\color{green}(1)\) CF711D Directed Roads
有 \(n\) 个点和 \(n\) 条边，第 \(i\) 条边从 \(i\) 连到 \(a_i\)（保证 \(i \ne a_i\)）。 每条边需要指定一个方向（无向边变为有向边）。问有多少种指定方向的方案使得图中不出现环，答案对 \(10^9 + 7\) 取模。
\(n \le 2 \times 10^5\)。
显然图构成了若干棵互不干涉的基环树。那么我们对于每一棵基环树单独考虑，相乘即为答案。
若第 \(i\) 棵基环树中有 \(p_i\) 条边在环上，\(q_i\) 条边不在换上。首先显然有 \(\sum p_i + q_i = n\)。
考虑定向后出现环的条件，是当前这 \(p_i\) 条边的指向全部相同，即存在 \(2\) 中存在环的方案。所以不出现环的方案数即 \((2^{p_i} - 2) \times 2^{q_i}\)。
$\color{blue}\text{Code}$
int n, a[N], id[N], sum;
vector<int> vec;
int vis[N];
void dfs(int u, int t) {
id[u] = t;
vis[u] = 1;
if (!vis[a[u]]) dfs(a[u], t + 1);
else if (vis[a[u]] == 1) {
int w = t - id[a[u]] + 1;
vec.push_back(w);
sum -= w;
}
vis[u] = 2;
}
int fpm(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = (ll)res * a % P;
b >>= 1, a = (ll)a * a % P;
}
return res;
}
void Luogu_UID_748509() {
fin >> n;
for (int i = 1; i <= n; ++ i ) fin >> a[i];
sum = n;
for (int i = 1; i <= n; ++ i )
if (!id[i])
dfs(i, 1);
int res = fpm(2, sum);
for (int t : vec) res = (ll)res * (fpm(2, t) - 2) % P;
fout << res;
}
\(\color{blue}(2)\) CF85E Guard Towers
- 在直角坐标系上有 \(n\) 座塔。要求把这些塔分成两组，使得同组内的两座塔的曼哈顿距离的最大值最小，并求出在此前提下求出有多少种分组方案，对 \(10^9 + 7\) 取模。
- \(n, x_i, y_i \le 5 \times 10^3\)。
首先二分答案。然后以平方的复杂度暴力将不满足条件的塔之间连边。此时，若图形成了一张二分图，那么答案可行。这是第一问。
在这张二分图中会呈现若干个连通块，每个连通块显然后两种黑白染色的方案，即将点分成两组的方案。那么答案即 \(2\) 的连通块数量的幂。这是第二问。
$\color{blue}\text{Code}$
int n, a[N], b[N];
struct Gragh {
vector<int> g[N];
void clear() { for (int i = 1; i <= n; ++ i ) g[i].clear(); }
void add(int a, int b) { g[a].push_back(b); }
int col[N];
int dfs(int u, int c) {
col[u] = c;
int cnt = 1;
for (int v : g[u]) {
if (!col[v]) {
int t = dfs(v, 3 - c);
if (t == -1) return -1;
cnt += t;
}
else if (col[v] == c) return -1;
}
return cnt;
}
int dsu() {
fill(col + 1, col + n + 1, 0);
int res = 1;
for (int i = 1; i <= n; ++ i )
if (!col[i]) {
int t = dfs(i, 1);
if (t == -1) return -1;
res = res * 2ll % P;
}
return res;
}
}G;
int chk(int mid) {
G.clear();
for (int i = 1; i <= n; ++ i )
for (int j = i + 1; j <= n; ++ j )
if (abs(a[i] - a[j]) + abs(b[i] - b[j]) > mid)
G.add(i, j), G.add(j, i);
return G.dsu();
}
void Luogu_UID_748509() {
fin >> n;
for (int i = 1; i <= n; ++ i ) {
fin >> a[i] >> b[i];
}
int l = 0, r = 1e4, res1 = 0, res2 = 0;
while (l <= r) {
int mid = l + r >> 1;
int t = chk(mid);
if (t == -1) l = mid + 1;
else r = mid - 1, res1 = mid, res2 = t;
}
fout << res1 << '\n' << res2 << '\n';
}
\(\color{purple}(3)\) CF732F Tourist Reform
- 给定一张 \(n\) 个点 \(m\) 条边的简单无向图，你需要给每条边都确定一个方向，使原图变成一个有向图。设 \(R_i\) 为从 \(i\) 号点出发能到达的不同点的数量。最大化所有 \(R_i\) 的最小值。
- 输出这个最小值以及每条边的定向方案。
- \(n , m \le 4 \times 10^5\)。
首先根据 CF118E 的思路，一定存在一种为一个 dcc（边双连通分量）中所有边定向的方案，使其成为一个 scc（强连通分量）。具体见这里。
所以将所有 dcc 缩点，那么原图将成为一颗树，每个点的点权为这个点所代表的 dcc 的点数。接下来最优的构造方案是将点权最大的点作为这棵树的根，然后让其余边都从儿子指向父亲。容易证明这样是正确的。
$\color{blue}\text{Code}$
没写。