1. K 本の辺を選ぶ
给定一个包含 $N$ 个点和 $M$ 条边的简单无向图。点的编号分别为 $0, 1, \cdots, N-1$,边的编号分别为 $0, 1, \cdots, M-1$。第 $i$ 条边连接点 $u_i$ 和点 $v_i$,这条边的边权为 $w_i$ 。
假设你想从此图中选出 $K$ 条边,但所选择的边不能构成环。
在此约束下,找出所选边的长度总和的最小值。但如果无法选择不会产生环的边,则输出 -1
。
限制:
- $1 \leqslant N \leqslant 10^3$
- $N-1 \leqslant M \leqslant 10^3$
- $1 \leqslant K \leqslant M$
- $1 \leqslant w_i \leqslant 100$
算法分析
容易想到最小生成树,只需在最小生成树中选出边权前 $K$ 小的边即可;但如果最小生成树不足 $K$ 条边,说明选择 $K$ 条边一定会构成环!
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
struct UnionFind {
vector<int> d;
UnionFind(int n = 0): d(n, -1) {}
int find(int x) {
if (d[x] < 0) return x;
return d[x] = find(d[x]);
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (d[x] > d[y]) swap(x, y);
d[x] += d[y];
d[y] = x;
return true;
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
return -d[find(x)];
}
};
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<pair<int, P>> es;
rep(i, m) {
int u, v, w;
cin >> u >> v >> w;
es.emplace_back(w, P(u, v));
}
sort(es.begin(), es.end());
UnionFind uf(n);
int ans = 0;
int chosen_num = 0;
for (auto [w, e] : es) {
auto [a, b] = e;
if (chosen_num >= k) break;
if (uf.same(a, b)) continue;
uf.unite(a, b);
ans += w;
chosen_num++;
}
if (chosen_num < k) ans = -1;
cout << ans << '\n';
return 0;
}
2. Reachable Nodes
给定一张 $n$ 个点 $m$ 条边的有向无环图,分别统计从每个点出发能够到达的点的数量(包含该点自身)。
限制:
- $1 \leqslant n \leqslant 5 \times 10^4$
- $1 \leqslant m \leqslant 10^5$
算法分析
先跑一遍拓扑排序
记 f[v]
表示从点 $v$ 出发的点集,$\{u_1, u_2, \cdots, u_k\}$ 为从点 $v$ 直接到达的点
$f[v] = \{v\} \cup f[u_1] \cup f[u_2] \cdots \cup f[u_k]$
然后在拓扑序下倒序求出每个点的 f[v]
(一方面,在拓扑序下,每条边 $(u, v)$, $u$ 总在 $v$ 之前;另一方面,倒序求是为了保证无后效性)
总的时间复杂度是 $O(n(n+m))$
我们可以利用 std::bitset
做进一步的优化
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::queue;
using std::bitset;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
vector<int> deg(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
deg[b]++;
}
queue<int> q;
rep(i, n) if (deg[i] == 0) q.push(i);
vector<int> ord;
while (q.size()) {
int v = q.front(); q.pop();
ord.push_back(v);
for (int u : to[v]) {
deg[u]--;
if (deg[u] == 0) q.push(u);
}
}
vector<bitset<50000>> reachable(n);
for (int i = n-1; i >= 0; --i) {
int v = ord[i];
reachable[v][v] = true;
for (int u : to[v]) {
reachable[v] |= reachable[u];
}
}
rep(i, n) {
cout << reachable[i].count() << '\n';
}
return 0;
}
3. Reachability Queries
给定一张包含 $n$ 个点和 $m$ 条边的有向图。
要求回答 $q$ 个以下形式的询问。
- 你能从点 $a$ 到达点 $b$ 吗
限制:
- $1 \leqslant n \leqslant 5 \times 10^4$
- $1 \leqslant m, q \leqslant 10^5$
算法分析
先做一遍缩点,这样就变成了和上一题类似的题了,做法一样
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::stack;
using std::queue;
using std::bitset;
using std::function;
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, m, Q;
cin >> n >> m >> Q;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
}
int idx = 0;
vector<int> dfn(n), low(n);
stack<int> stk;
vector<bool> inst(n);
int cnt = 0;
vector<int> comp(n);
function<void(int)> tarjan = [&](int v) {
dfn[v] = low[v] = ++idx;
stk.push(v); inst[v] = true;
for (int u : to[v]) {
if (dfn[u] == 0) {
tarjan(u);
chmin(low[v], low[u]);
}
else if (inst[u]) chmin(low[v], dfn[u]);
}
if (low[v] == dfn[v]) {
++cnt;
int u;
do {
u = stk.top(); stk.pop(); inst[u] = false;
comp[u] = cnt-1;
} while (u != v);
}
};
rep(i, n) if (dfn[i] == 0) tarjan(i);
vector<vector<int>> g(n);
vector<int> deg(n);
rep(v, n) {
for (int u : to[v]) {
int nv = comp[v], nu = comp[u];
if (nv == nu) continue;
g[nv].push_back(nu);
deg[nu]++;
}
}
queue<int> q;
rep(i, cnt) if (deg[i] == 0) q.push(i);
vector<int> ord;
while (q.size()) {
int v = q.front(); q.pop();
ord.push_back(v);
for (int u : g[v]) {
deg[u]--;
if (deg[u] == 0) q.push(u);
}
}
vector<bitset<50000>> reachable(cnt);
for (int i = cnt-1; i >= 0; --i) {
int v = ord[i];
reachable[v][v] = true;
for (int u : g[v]) {
reachable[v] |= reachable[u];
}
}
rep(qi, Q) {
int a, b;
cin >> a >> b;
--a; --b;
int na = comp[a], nb = comp[b];
if (na == nb) puts("YES");
else {
if (reachable[na][nb]) puts("YES");
else puts("NO");
}
}
return 0;
}
4. 圈数统计
给定一个简单无向图(不存在自环和重边),请统计这个图中有多少个简单环。环由三条或三条以上首尾相连的边构成。一个环称为简单环,是指没有点在环中出现两次。
注意,无向图没有方向,所以 $2\rightarrow3\rightarrow1\rightarrow2$ 和 $3\rightarrow2\rightarrow1\rightarrow3$ 是同一个环。
求给定的图上有多少不同的简单环。
限制:
- $0 \leqslant m \leqslant \frac{n(n-1)}{2}$
- $1 \leqslant n \leqslant 20$
算法分析
通过观察数据范围可知,或许对点数进行状压是一个思路。
可以考虑统计环的个数转化为统计简单路径的条数。
设 $f(i, j, s)$ 表示集合 $s$ 中 $i$ 到 $j$ 的简单路径条数。需要注意的是,在无向图里,$i \to j \to k$、$j \to k \to i$ 和 $k \to i \to j$ 三种递推关系本质上是在描述同一个环。观察并计算运算量,$19^2 \times 2^{19} = 189267968$,无法使用数组存下所有的状态,因此考虑一个动态规划中常用的技巧:按秩转移
。
此处可以将 秩
理解为顺序
。为了使同一个集合内的点是按顺序转移的,考虑使用 lowbit(s)
来记录答案。
整个算法流程可以理解为对于每个状态,枚举其中的元素 $i$,同时枚举另一个元素 $j$。若 $j$ 在 $s$ 里,按上文分析的只有 $\rm{lowbit}(s) = j$ 时要计入答案;如果 $j$ 不在 $s$ 里,就可以将方案数从 $s$ 转移到 $s \cup \{j\}$ 这个集合。
于是最后时间复杂度为 $O(n \cdot 2^n)$,空间复杂度为 $O(n \cdot 2^n)$。其中由于并不会跑满,所以可以较为轻松的通过。
C++ 代码
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using ll = long long;
bool g[21][21];
ll dp[2000005][21];
inline int lowbit(int x) { return x&-x; }
template<typename T>
inline T read() {
T num = 0; // 存储读取到的整数
int neg = 0; // 负数标识
char c; // 存储当前读取到的字符
c = cin.get();
while ((c < '0' or c > '9') and c != '-') {
c = cin.get();
}
if (c == '-') neg = 1;
else num = c-'0';
c = cin.get();
while (isdigit(c)) {
num = num*10+(c^48);
c = cin.get();
}
if (neg == 1) num *= -1;
return num;
}
int main() {
int n = read<int>();
int m = read<int>();
rep(i, m) {
int a = read<int>();
int b = read<int>();
--a; --b;
g[a][b] = g[b][a] = true;
}
for (int i = 1, j = 0; j < n; ++j, i <<= 1) dp[i][j] = true;
ll ans = 0;
rep(s, 1<<n) {
rep(i, n) {
if (!(s>>i&1) or !dp[s][i]) continue;
rep(j, n) {
if (!g[i][j] or lowbit(s) > (1<<j)) continue;
if ((1<<j) == lowbit(s)) ans += dp[s][i];
else if (!(s>>j&1)) dp[s|(1<<j)][j] += dp[s][i];
}
}
}
// 先去掉长度为 2 的简单环的贡献,然后由于这里是无向图算了 2 倍的贡献,所以需要除以 2
cout << (ans-m)/2 << '\n';
return 0;
}
5. 简单路径
给定一个由 $n$ 个点、$n$ 条边组成的无向连通图,这张图不存在重边
,也不存在自环
。请问在这张图上,存在多少条简单路径
? 由于数字可能很大,输出答案模 $10^9+7$ 的余数。
所谓简单
,是指路径的起点与终点不相同,且路径上的任何点、任何边都不会在路径上重复出现。所谓重边
,是指两条不同的边,连接了同一对点。所谓自环
,是指一条边,连接了同一个点。
限制:
- $3 \leqslant n \leqslant 2 \times 10^5$
算法分析
可以考虑余事象
若图上所有点都在环上,由于环上任意两点可确定两条简单路径,于是答案就是 $\binom{n}{2} \times 2 = n(n-1)$
再考虑环上的点会引出子树的情况,对于子树上的任意两点可以确定 $\binom{t_i}{2}$ 条简单路径,其中 $t_i$ 表示该子树的大小
利用余事象,得到最后的答案为 $n(n-1) - \sum \binom{t_i}{2}$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
int n;
cin >> n;
vector<vector<int>> to(n);
vector<int> deg(n);
rep(i, n) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
deg[a]++;
deg[b]++;
}
vector<int> t(n, 1);
queue<int> q;
rep(i, n) if (deg[i] == 1) q.push(i);
while (q.size()) {
int v = q.front(); q.pop();
for (int u : to[v]) {
deg[u]--;
if (deg[u] == 1) q.push(u);
t[u] += t[v];
}
}
mint ans = mint(n)*(n-1);
rep(i, n) {
if (deg[i] == 2) {
mint now = t[i];
now *= t[i]-1;
now /= 2;
ans -= now;
}
}
ans *= 2;
cout << ans << '\n';
return 0;
}
6. 偏序与全序
有 $n$ 个数字 $x_1,x_2,\dots,x_n$,我们不知道它们的大小,但是知道它们之间的 $m$ 项条件。
其中第 $i$ 项的形式为 $L_i~op_i~R_i$ 为 <
、=
、>
中的一种。含义为 $x_{L_i}$ 小于、等于、大于 $x_{R_i}$
。请根据这些条件做出判断:
- 如果这些条件之间存在矛盾,输出
Impossible
- 否则,如果这些条件能够确定所有数字之间的大小关系,输出
Total Order
- 否则,输出
Partial Order
限制:
- $1 \leqslant n \leqslant 200,000$
- $1 \leqslant m \leqslant 500,000$
算法分析
先考虑没有等于号的情况,这时小于号可以直接转换为大于号,对于一个条件 $(L_i,R_i)$,设该条件为 $x_{L_i}>x_{R_i}$,那么将 $L_i$ 向 $R_i$ 连边,然后将整个图进行拓扑排序,如果发现有环,就可以判定无解,如果没有环,那么如果拓扑序唯一,则输出 Total Order
,否则输出 Partial Order
。
考虑如何判定 DAG
的拓扑序是否唯一,显然如果队列里永远只有11个元素,那么拓扑序唯一,否则可以改变队列内的元素的出队顺序构造不同的拓扑序。
接下来考虑等号,用并查集维护即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
struct UnionFind {
vector<int> d;
UnionFind(int n = 0): d(n, -1) {}
int find(int x) {
if (d[x] < 0) return x;
return d[x] = find(d[x]);
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (d[x] > d[y]) swap(x, y);
d[x] += d[y];
d[y] = x;
return true;
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
return -d[find(x)];
}
};
template<class T>
inline T read() {
T num = 0;
int neg = 0;
char c = getchar();
while (!isdigit(c) and c != '-') {
c = getchar();
}
if (c == '-') neg = 1;
else num = c-'0';
c = getchar();
while (isdigit(c)) {
num = (num<<1)+(num<<3)+(c^48);
c = getchar();
}
return num;
}
int main() {
int n = read<int>();
int m = read<int>();
UnionFind uf(n);
vector<int> l(m), r(m);
vector<char> op(m);
rep(i, m) {
l[i] = read<int>();
op[i] = getchar();
r[i] = read<int>();
--l[i]; --r[i];
if (op[i] == '=') uf.unite(l[i], r[i]);
if (op[i] == '>') swap(l[i], r[i]);
}
vector<int> deg(n);
vector<vector<int>> to(n);
rep(i, m) if (op[i] != '=') {
int v = uf.find(l[i]);
int u = uf.find(r[i]);
++deg[u];
to[v].push_back(u);
}
queue<int> q;
int cnt = 0;
rep(i, n) {
if (uf.find(i) == i) {
++cnt;
if (deg[i] == 0) {
q.push(i);
}
}
}
bool ok = false;
while (q.size()) {
--cnt;
ok |= q.size() > 1;
int v = q.front(); q.pop();
for (int u : to[v]) {
--deg[u];
if (deg[u] == 0) {
q.push(u);
}
}
}
if (cnt) puts("Impossible");
else {
if (ok) puts("Partial Order");
else puts("Total Order");
}
return 0;
}