题目链接:https://codeforces.com/problemset/problem/1912/H
题意
有 \(n\) 个城市,\(m\) 个人。第 \(i\) 人想从城市 \(a_i\) 移动到 \(b_i\)。每个城市每天可以使用至多一次传送胶囊,可以将任意数目的人从该城市传送到任意一个(相同的)其它城市。注意传送有时间顺序。
求是否可以让所有人到达目的地。如果可以达到,给出使用传送胶囊最少的传送方案,输出每个传送胶囊的起终点。\(n \le 10^3, m \le 10^5\)。
题解(官解)
这题很有意思,但是官解讲的有点不清晰,我尽量添加一些细节,包括一些关键结论的证明。而且这个数据范围也有些迷惑,我还以为会是 \(O(m + n^2)\) 之类的时间复杂度。
如果有合适的传送方案,以传送方案为边建图 \(T\),则显然每个连通片是树或基环树。
结论 \(1\):如果存在方案,存在一种方案,使每个连通片是链或环。
证明:只要存在形如 \(a \to c, b \to c\) 的连边,将其改为 \(a \to b \to c\),\(a \to b\) 在 \(b \to c\) 之前发生,原来可行的方案一定仍然可行。不断进行这样的调整,树和基环树最终被调整为链或环。
有了这个结论我们可以把操作的时间顺序固定下来。对链显然时间顺序等于边的顺序最优;对环从一个起点绕环一圈的时间顺序最优。注意由于有时间顺序的限制,环其实是假的环,相当于起点 \(u\) 可以到达其它所有点,外加一条链。
以每个人的源和目的建图 \(G\)。
结论 \(2\):最优方案中,\(T\) 的每个连通片(弱连通分量)的点集和 \(G\) 相同。
证明:首先显然每个 \(G\) 的连通片必须在 \(T\) 中连通。如果 \(G\) 中的两个连通片在 \(T\) 中连通,若为链则一定可以分开为两条链(按照时间顺序重新连接两条链即可);若为环也一定可以分成两个环(同样按照时间顺序重新连接两个环)。
有了这两个结论,我们就可以分开 \(G\) 的每个连通片考虑。
如果这个连通片无环,则按照拓扑序指定一条链。拓扑序保证了每个人终点在起点之后可达。否则,需要指定一个环。枚举每个点 \(u\) 作为环的起点。由关于时间顺序的说明,如果存在方案使得点 \(u\) 作为环的起点,该连通片除去从 \(u\) 出发的所有边一定是无环的。构造这部分的一条链,加上点 \(u\) 作为起点组成环就是答案。如果任意一个点都不能作为起点,无解。
时间复杂度 \(O(n(n + m))\)。
代码实现(C++)
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> uadj(n), adj(n);
for (int ei = 0; ei < m; ei++) {
int u, v;
cin >> u >> v;
u--, v--;
uadj[u].push_back(v), uadj[v].push_back(u);
adj[u].push_back(v);
}
vector<int> vis(n);
vector<vector<int>> comp;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
comp.push_back({});
queue<int> q;
vis[i] = true;
q.push(i);
while (q.size()) {
int u = q.front();
q.pop();
comp.back().push_back(u);
for (int v : uadj[u]) {
if (!vis[v]) vis[v] = 1, q.push(v);
}
}
}
}
vector<pair<int, int>> ans;
auto topo_order = [&](const auto &vec) -> vector<int> {
vector<int> in_deg(n);
for (int u : vec)
for (int v : adj[u])
in_deg[v]++;
queue<int> q;
for (int u : vec) {
if (!in_deg[u]) { q.push(u); }
}
vector<int> res;
while (q.size()) {
int u = q.front();
q.pop();
res.push_back(u);
for (int v : adj[u]) {
if (!--in_deg[v]) q.push(v);
}
}
return res;
};
auto handle_cyclic = [&](auto &vec) {
for (int u : vec) {
auto adju = std::move(adj[u]);
vector<int> res = topo_order(vec);
if (res.size() == vec.size()) {
res.erase(ranges::find(res, u));
ans.push_back({u, res[0]});
for (int i = 0; i < (int)res.size() - 1; i++)
ans.push_back({res[i], res[i + 1]});
ans.push_back({res.back(), u});
return;
}
adj[u] = std::move(adju);
}
cout << -1 << "\n";
exit(0);
};
for (auto vec : comp) {
if (auto res = topo_order(vec); res.size() == vec.size()) {
for (int i = 0; i < (int)res.size() - 1; i++)
ans.push_back({res[i], res[i + 1]});
} else {
handle_cyclic(vec);
}
}
cout << ans.size() << "\n";
for (auto [u, v] : ans)
cout << u + 1 << " " << v + 1 << "\n";
}
标签:连通,vector,int,res,back,Commute,push,Hypercatapult,CF1912H
From: https://www.cnblogs.com/cpchenpi/p/17920153.html