题解:AT_bogosortcontest_div1_g Source to Sink

· · 题解

给定一张 n 个点 m 条边的有向图。一次操作选定零入度点 u,将 u 为端点的边方向反转。

最大化操作次数并输出,或报告操作无限进行。

多测,\sum n \le 10^5,\sum m \le 2\times 10^5,2 秒,1024 MB。

独立考虑原图的所有弱连通分量。如果存在 DAG 分量,翻转零入度点后不会产生有向环,操作次数无限。

设 x_u 为节点 u 的操作次数,若 u 在有向环上必有 x_u=0。

考察有向边 u \to v,将操作序列中 \ne u,v 的部分都删掉,那么必然是 u,v,u,v,\cdots 交替,从而

x_v \le x_u \le x_v+1

断言 满足所有约束的非负整数解 x_1\sim x_n,均能通过合法操作取到。

证明 删去 x_u=0 的 u,残余部分必为 DAG,取出任意拓扑序。第 k 轮操作按同一个拓扑序操作所有 x_u \ge k 的 u。

初始边 u \to v 的约束只有两种:

由拓扑序保证 u 先于 v 操作,所有操作合法,而节点 u 恰好操作 x_u 次。

判环可以拓扑排序,构造 x_1 \sim x_n 可以对差分约束系统 01BFS。

复杂度 O(n+m)。

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';
}