题解:AT_bogosortcontest_div1_g Source to Sink
stripe_python · · 题解
给定一张
n 个点m 条边的有向图。一次操作选定零入度点u ,将u 为端点的边方向反转。最大化操作次数并输出,或报告操作无限进行。
多测,
\sum n \le 10^5 ,\sum m \le 2\times 10^5 ,2 秒,1024 MB。
独立考虑原图的所有弱连通分量。如果存在 DAG 分量,翻转零入度点后不会产生有向环,操作次数无限。
设
考察有向边
断言 满足所有约束的非负整数解
证明 删去
初始边
由拓扑序保证
判环可以拓扑排序,构造
复杂度
const int N = 1e5 + 5, inf = 1e9;
int n, m, fa[N], d[N], dis[N];
bool vis[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<int> e[N];
vector<pair<int, int>> g[N];
vector<int> p[N];
bool solve(vector<int>& p) {
if (p.empty()) return true;
queue<int> Q;
for (int u : p)
if (d[u] == 0) Q.emplace(u), vis[u] = true;
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int v : e[u]) if (--d[v] == 0) Q.emplace(v), vis[v] = true;
}
bool c = 0;
for (int u : p) if (!vis[u]) g[0].pb(u, 0), c = 1;
return c;
}
void bfs() {
deque<int> Q; Q.pb(0);
while (!Q.empty()) {
int u = Q.front(); Q.pop_front();
for (auto [v, w] : g[u])
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (w == 0) Q.emplace_front(v);
else Q.emplace_back(v);
}
}
}
void _main() {
cin >> n >> m;
iota(fa + 1, fa + n + 1, 1);
fill(d + 1, d + n + 1, 0);
for (int i = 0; i <= n; i++)
e[i].clear(), g[i].clear(), p[i].clear();
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v; fa[find(u)] = find(v);
e[u].pb(v), ++d[v];
g[u].pb(v, 0), g[v].pb(u, 1);
}
for (int i = 1; i <= n; i++) p[find(i)].pb(i);
fill(vis + 1, vis + n + 1, 0);
for (int i = 1; i <= n; i++)
if (!solve(p[i])) return cout << -1 << '\n', void();
fill(dis+1, dis+n+1, inf), bfs();
cout << accumulate(dis+1, dis+n+1, 0LL) << '\n';
}