简单图论杂题

DF_G · 2026-10-14 10:34:25 · 算法·理论

::::info[前言]{open} 本文使用 deepseek+chatgpt（从未打过这么富裕的仗）润色。保证人类贡献远大于 AI 贡献。 ::::

Triangle City

注意到最优的解法需要经过图中的所有边至少一次。每个顶点的度数都是偶数，本题要求从 (1,1) 到 (n,n)，所以需要的是欧拉路径，即要求恰好起点和终点度数为奇数，其余点度数为偶数。 ::::info[欧拉路径]{open} 欧拉路径是经过图中每条边恰好一次的路径。存在条件是恰好有两个顶点度数为奇数，这两个点就是起点和终点。\ 我们求欧拉路径一般使用 Hierholzer 算法。\ 下定义 E_u 为列表中每项记录邻边另一端点及该边编号。我们维护一个 p_u 表示每一个扫描位置 p_u 表示下一条待检查的边在 E_u 中的下标。我们从起点 s 开始，对当前顶点 u 执行以下操作：

• 反复检查 E_u 中从 p_u 开始的边。
  • 如果已经到达了末尾就停止检查把顶点 u 放在答案序列的结尾。
  • 如果这条边已经访问过了，p_u\to p_u+1，然后检查下一条边。
  • 若当前边未被访问，则将其标记为已访问，然后以该边的另一端点 v 作为新的当前顶点，递归执行同样的操作。

• 从起点 s 调用上述递归。递归结束后，结果答案序列中顶点的顺序是欧拉路径的逆序。将答案序列反转，即得到从 s 出发的欧拉路径。
  初始时所有点度数均为偶数。若我们删去一条从起点到终点的路径 S，就可以使得起点和终点的度数变为奇数，其余点的度数为偶数。为了让剩下的边的长度尽可能大，S 应该尽可能小，所以 S 就是 (1,1)\to (n,n) 的最短路。\
  由于三角不等式：
  a+b>c
  所以最短路不可能在一个三角形中同时走两条边，因为 A\xrightarrow{a} B\xrightarrow{b}C 要走的路径大于 A\xrightarrow{c}C。所以我们删去最短路之后图一定仍然联通。那么答案就是 \sum_{i=1}^m w_i-\min S。
  ::::success[P14051]
  ```c++
  #include<bits/stdc++.h>
  #define int long long
  using namespace std;

const int N = 3e6 + 5; const int M = 3e6 + 5; const int INF = 1e18; typedef pair<int,int> pii; int n,u,v,w,ans,p[N],mp[M],cur[N]; vector<pii> G[N],g[N]; int dist[N],vis[N]; priority_queue<pii,vector<pii>,greater<pii> > q; void dijkstra(){ for(int i = 0;i <= (n - 1) (n + 1) + n;i ++) dist[i] = INF; dist[1] = 0; q.push({0,1}); while(!q.empty()){ int u = q.top().second; q.pop(); if(vis[u]) continue; vis[u] = 1; for(auto now : g[u]){ int v = now.first; int w = now.second; if( dist[v] > dist[u] + w){ p[v] = u; dist[v] = dist[u] + w; q.push({dist[v],v}); } } } } vector<int> Q; void Mark(){ u = (n-1)(n+1)+n; while(u != 1){ int prev = p[u]; for(auto now : G[u]){ int v = now.first; int id = now.second; if(v == prev){ mp[id] = 1; break; } } u = prev; } } void dfs(int u){ for(;cur[u] < G[u].size();cur[u] ++){ int v = G[u][cur[u]].first; int id = G[u][cur[u]].second; if(mp[id]) continue; mp[id] = 1; dfs(v); } Q.push_back(u); }

signed main(){ int T; scanf("%lld",&T); while(T --){ ans = 0; int ec = 0; scanf("%lld",&n); int mx = (n - 1) (n + 1) + n; for(int i = 0;i <= mx;i ++){ G[i].clear(); g[i].clear(); vis[i] = 0; p[i] = 0; cur[i] = 0; } for(int i = 0;i < M;i ++) mp[i] = 0; Q.clear(); while(!q.empty()) q.pop(); for(int i = 1;i < n;i ++){ for(int j = 1;j <= i;j ++){ u = (i - 1) (n + 1) + j; v = i (n + 1) + j; scanf("%lld",&w); ec ++; G[u].push_back({v,ec}); G[v].push_back({u,ec}); g[u].push_back({v,w}); g[v].push_back({u,w}); ans += w; } } for(int i = 1;i < n;i ++){ for(int j = 1;j <= i;j ++){ u = (i - 1) (n + 1) + j; v = i (n + 1) + j + 1; scanf("%lld",&w); ec ++; G[u].push_back({v,ec}); G[v].push_back({u,ec}); g[u].push_back({v,w}); g[v].push_back({u,w}); ans += w; } } for(int i = 1;i < n;i ++){ for(int j = 1;j <= i;j ++){ u = i (n + 1) + j; v = i (n + 1) + j + 1; scanf("%lld",&w); ec ++; G[u].push_back({v,ec}); G[v].push_back({u,ec}); g[u].push_back({v,w}); g[v].push_back({u,w}); ans += w; } } dijkstra(); ans -= dist[(n - 1) (n + 1) + n]; printf("%lld\n",ans); Mark(); dfs(1); printf("%lld\n",Q.size()); for(int i = Q.size() - 1;i >= 0;i --){ int tmp = Q[i]; int x = (tmp - 1) / (n + 1) + 1; int y = (tmp - 1) % (n + 1) + 1; printf("%lld %lld ",x,y); } puts(""); } return 0; }

::::
## [电报 / Telegraph](https://www.luogu.com.cn/problem/P14401)
这个题本质上是一个贪心。\
注意到整个图一开始的时候每一个节点的出度都为 $1$，但是入度不知道。我们的目的是构造最终要覆盖所有点的大环，那么我们需要最终每个点的入度恰好为 $1$ 且整个图联通。那么问题变为：
> 给定一张图，每一个节点的出度为 $1$，给定所有的 $n$ 条边形如 $i\to a_i$，可以改动一些边使得 $i\to j$，花费为 $c_i$。最终要求整个图是一个覆盖所有点的大环。

那么如果一开始的时候就构成了一个大环那么花费显然为 $0$。\
对于一个节点 $u$，我们维护 $w_u$ 表示已经处理的指向 $u$ 的点 $c$ 的最大值。由于最终 $u$ 只能保留一个入边，其它的全部删掉，所以保留 $w_u$ 应该是最优的。我们假设每一个点都要改变（事实上可以不变，待会再说），那么我们的花费就是 
$$Ans=\sum_{i=1}^n (c_i-w_i)$$
事实上，这样会导致一些点可以不做改动更优但是改了造成了无关的花费。我们拓扑排序之后，剩下的点都是环上的节点。我们对于每一个环上节点 $u$，那么我们改变 $u$ 的净收益是 $w_{a_u}-c_u$，因为 $a_u$ 可以选择在树子节点中保留一个。那么如果改变 $u$ 是赚的（$w_{a_u}-c_u>0$）我们就可以节省下来这个点的花费。如果所有的都不赚，我们选择一个节点去断边，我们选择 $w_{a_u}-c_u$ 最大的 $u$。因为这样实际上 $c_u-w_{a_u}$ 是最小的。
::::success[P14401]
```c++
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;
const long long INF = -1e18;
int n,a[N],c[N],d[N],w[N],col[N],cnt,ans;
vector<int> v[N];
queue<int> q;

void dfs(int x){
    int cur = x;
    while(!col[cur]) {
        col[cur] = cnt;
        v[cnt].push_back(cur);
        cur = a[cur];
    }
}

void topu() {
    for(int i = 1;i <= n;i ++) if(!d[i]) q.push(i);
    while(!q.empty()) {
        int u = q.front();
        q.pop();

        ans += c[u] - w[u];
        w[a[u]] = max(w[a[u]],c[u]);

        d[a[u]] --;
        if(!d[a[u]]) q.push(a[u]);
    }
}

signed main(){
    scanf("%lld",&n);
    for(int i = 1;i <= n;i ++){
        scanf("%lld%lld",&a[i],&c[i]);
        d[a[i]] ++;
    }

    int t = 1;
    for(int i = 1;i <= n;i ++) {
        if(d[i] != 1) {
            t = 0;
            break; 
        }
    } 

    if(t) {
        int cur = 1;
        int cnt = 0;
        while(true) {
            cnt++;
            cur = a[cur];
            if(cur == 1) break;
        }
        if(cnt == n) {
            puts("0");
            return 0;
        }
    }

    topu();

    for(int i = 1;i <= n;i ++) {
        if(d[i] && !col[i]) {
            cnt ++;
            dfs(i); 
        }
    }

    for(int i = 1;i <= cnt;i ++) {
        int mx = INF;
        for(auto u : v[i]) {
            int vt = w[a[u]] - c[u];
            if(vt > 0) ans -= vt;
            mx = max(mx,vt); 
        }
        if(mx < 0) ans -= mx;
    }

    printf("%lld\n",ans);
    return 0; 
}

::::

Go Playing with Reimu

我们设 f_u=\{1,0\} 表示棋子位于节点 u 轮到先手时先手是否必胜，其中 f_u=1 表示先手必胜，f_u=0 表示先手必败。那么

• 如果 u 是叶子节点，先手无法移动，那么 f_u=0。
• 否则，如果有一个子节点 v 满足 f_v=0，那么先手可以选择走 v 使得后手变成新的先手进入必败态，于是 f_u=1。

但是我们发现这两个人会删掉叶子节点 x_i，时间复杂度是 O(nq) 的。我们观察到 f_u 只是依赖于是否存在必败态儿子。我们把儿子分为重儿子和轻儿子。那么我们记录 \text{cnt}_u 为节点 u 的轻儿子中满足 f_v=0 的数量。那么

• 如果 \text{cnt}_u>0，那么存在必败态轻儿子，f_u=1。
• 否则，f_u 完全由重儿子决定，即f_u=f_{\text{son}_u}⊕1

由于重链区间的 DFS 序是连续的，将所有满足 \text{cnt}_u>0 的节点的 DFS 序存入 set 中。这样可以在 O(\log n) 时间内找到重链区间内第一个 \text{cnt}_u>0 的位置。我们注意到删掉一个节点可能会导致一条链的 f_u 的改变，所以我们向上传播修改。\ 时间复杂度是 O((n+q)\log^2 n) 的。 ::::success[P16411]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e5 + 5;
int n,q,tim;
vector<int> G[N];
int fa[N],dep[N],siz[N],son[N],f[N],cnt[N];
int dfn[N],id[N],top[N],st[N][20];
int del[N];
set<int> S;

void dfs1(int u,int p){
    fa[u] = p;
    dep[u] = dep[p] + 1;
    siz[u] = 1;
    for(auto v : G[u]){
        if(v == p) continue;
        dfs1(v,u);
        siz[u] += siz[v];
        if(siz[v] >= siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u,int gr){
    dfn[++ tim] = u;
    id[u] = tim;
    top[u] = gr;
    if(son[u]) dfs2(son[u],gr);
    for(auto v : G[u]){
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v,v);
        if(!f[v]) cnt[u] ++;
    }
    if(cnt[u]) f[u] = 1;
    else f[u] = f[son[u]] ^ 1;
    st[u][0] = son[u];
    for(int i = 1;i <= 18;i ++) st[u][i] = st[st[u][i - 1]][i - 1];
}

int len(int u){
    int res = 0;
    for(int i = 18;i >= 0;i --)
        if(!del[st[u][i]]) {res += (1 << i);u = st[u][i];}
    return res;
}

int find(int l,int r){
    auto it = S.lower_bound(l);
    if(it == S.end() || *it > r) return 0;
    return *it - 1;
}

int query(int u){
    if(!u || del[u]) return 1;
    if(S.count(id[u])) return 1;
    int l = id[u];
    int r = id[u] + len(u);
    int pos = find(l,r);
    if(!pos) return (r - l) & 1;
    else return (pos - l) & 1;
}

void update(int u,int lst,int y){
    if(!u) return;
    if(y == 1){
        cnt[u] --;
        if(cnt[u] == 0){
            int tmp = query(top[u]);
            S.erase(id[u]);
            if(tmp != query(top[u])) update(fa[top[u]],top[u],tmp ^ 1);
        }
    } else {
        cnt[u] ++;
        if(cnt[u] == 1){
            int tmp = query(top[u]);
            S.insert(id[u]);
            if(tmp != query(top[u])) update(fa[top[u]],top[u],tmp ^ 1);
        }
    }
}

signed main(){
    scanf("%lld",&n);
    del[0] = 1;
    for(int i = 1;i < n;i ++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    f[0] = 1;
    dfs1(1,0);
    dfs2(1,1);
    for(int i = 1;i <= n;i ++) if(cnt[i]) S.insert(id[i]);
    if(f[1]) puts("Marisa");
    else puts("Reimu");
    scanf("%lld",&q);
    for(int i = 1;i <= q;i ++){
        int k;
        scanf("%lld",&k);
        int tmp = query(top[k]);
        del[k] = 1;
        int tmp2 = query(top[k]);
        if(tmp != tmp2) update(fa[top[k]],top[k],tmp ^ 1);
        if(query(1)) puts("Marisa");
        else puts("Reimu");
    }
    return 0;
}

::::

Menji, we miss you!

我们设 d_u 为节点 u 的深度。单独设 D=d_X。我们考虑二分去得到 D，我们每一次查询 \text{ask}(1,\text{mid})，最终 D=\text{mid}。\ 我们确定了 D 以后，所有深度恰好为 D 的节点构成初始候选集合 S。但是深度 d 最多会有 2^{d} 个节点（我们设根节点的深度为 0）不能直接暴力枚举。我们对于每一个节点 u，维护 \text{cnt}_u 表示以 u 为根的子树中包含的候选节点数量。（这个无疑是好维护的，可以用类似求子树大小的方式去求。）\ 那么我们选择一个节点 u 使得 \max(\text{cnt}_u, |S|-\text{cnt}_u) 尽可能小，模拟重心的概念我们也称这个 u 为重心。那么我们不断得到这样的重心，每一次查询 \text{ask}(u,D-d_u)

• 如果返回 1 那么 u 是 X 的祖先，于是 X 必在 u 的子树内，我们更新 S←S∩\text{subtree}(u)。
• 否则，u 不是 X 的祖先，于是 X 不在 u 的子树内，可以更新 S←S∖\text{subtree}(u)。

那么这样查询次数是 O(\log n) 的，是可以的。 ::::success[P17121]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e4 + 5;
int g[N],to[N],nxt[N],ecnt;
int f[N],d[N],n;
int c[N],fx[N],sz;
int tin[N],tout[N],tmr;
int cnt[N],isc[N];

void add(int u,int v) { to[++ecnt] = v; nxt[ecnt] = g[u]; g[u] = ecnt; }

void dfs(int u,int fa) {
    tin[u] = ++tmr;
    d[u] = fa ? d[fa] + 1 : 0;
    for(int e = g[u];e;e = nxt[e]) {
        int v = to[e];
        if(v != fa) dfs(v, u);
    }
    tout[u] = tmr;
}

int ask(int u,int k){
    printf("? %lld %lld\n",u,k);
    fflush(stdout);
    int ans;
    if(scanf("%lld",&ans) != 1) exit(0);
    return ans;
}

signed main(){
    int t;
    scanf("%lld",&t);
    while(t --) {
        scanf("%lld",&n);
        for(int i = 1;i <= n;i ++) g[i] = 0;
        ecnt = 0;
        for(int i = 2;i <= n;i ++) {
            scanf("%lld",&f[i]);
            add(f[i],i);
        }
        tmr = 0;
        dfs(1,0);

        int l = 0,r = n;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(ask(1,mid)) r = mid;
            else l = mid + 1;
        }
        int D = l;
        sz = 0;
        for(int i = 1;i <= n;i ++) if(d[i] == D) c[sz ++] = i;
        while(sz > 1) {
            for(int i = 1;i <= n;i ++) { cnt[i] = 0; isc[i] = 0; }
            for(int i = 0;i < sz;i ++) isc[c[i]] = 1;
            for(int i = n;i >= 1;i --) {
                cnt[i] += isc[i];
                if(f[i]) cnt[f[i]] += cnt[i];
            }
            int u = -1, best = sz + 1;
            for(int i = 1;i <= n;i ++) {
                if(cnt[i] == 0 || cnt[i] == sz) continue;
                int val = max(cnt[i], sz - cnt[i]);
                if(val < best) { best = val; u = i; }
            }
            int o = ask(u,D - d[u]); 
            int nsz = 0;
            for(int i = 0;i < sz;i ++) {
                int x = c[i];
                bool in = (tin[u] <= tin[x] && tin[x] <= tout[u]);
                if(in == (o == 1)) fx[nsz ++] = x;
            }
            for(int i = 0;i < nsz;i ++) c[i] = fx[i];
            sz = nsz;
        }
        printf("! %lld\n", c[0]);
        fflush(stdout);
    }
    return 0;
}

::::

走亲访友

一条边在被删除之前，允许被多次经过。那么对于边 (u,v)，如果我们走了 x 遍，相当于我们新建了 x-1 条 (u,v) 的重边。那么我们需要解决的问题就是，要在原图上添加若干重边，使整张图成为欧拉图，然后跑欧拉回路。\ 题目中要求了最后需要保留一棵树。那么聪明的你可能会想到最小生成树，但是题目中没有限制选的边，所以事实上任意一个生成树即可。那么我们

• 对于树边而言，我们是需要多次走它的。而且最后我们需要保留它，p_i=1。
• 对于非树边，它们只需要在欧拉回路中被走一次，然后删除即可，没必要重复走。最后要删除 p_i=0。

原图所有点的度数不一定都是偶数。欧拉回路要求所有点度数为偶数。我们需要通过添加重边来调整奇度点。\ 那么我们对于生成树自底而上遍历。那么我们一旦遇到了奇度点，我们需要一条重边 u\to \text{fa}_u，这样 u 就是偶度点了。\ 这样是正确的，原来有 m 条边，重边最多 n-1 条，所以欧拉回路总边数不超过 m+n-1。题目保证 k\ge n+m，而 m+n−1<n+m\le k，因此路径长度一定满足限制。 ::::success[P11762]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 + 5;
typedef pair<int,int> pii;

int n,m,u,v,k,s,cnt,sum;
vector<pii> g[N];
int d[N],e[N],cur[N];
int t[N],x[N],vis[N],vis2[N];
pii ans[N];

void build(int u) {
    vis[u] = 1;
    int sz = g[u].size();
    for(int i = 0;i < sz;i ++) {
        int v = g[u][i].first;
        int id= g[u][i].second;
        if(x[id] || vis[v]) continue;
        build(v);
        t[e[id]] = 1;
        if(d[v] & 1) {
            cnt ++;
            g[v].push_back({u,m + cnt});
            g[u].push_back({v,m + cnt});
            e[m + cnt] = e[id];
            x[m + cnt] = 1;
            d[v] ++;
            d[u] ++; 
        }
    } 
}

void dfs(int u){
    int len = g[u].size();
    for(int &i = cur[u];i < len;i ++){
        int v = g[u][i].first;
        int id= g[u][i].second;
        if(vis2[id]) continue; 
        vis2[id] = 1;
        dfs(v);
        ans[++sum] = {e[id],t[e[id]]};
    }
}

signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&k,&s);
    for(int i = 1;i <= m;i ++){
        scanf("%lld%lld",&u,&v);
        g[u].push_back({v,i});
        g[v].push_back({u,i});
        e[i] = i;
        d[u] ++;
        d[v] ++;
    }
    build(s);
    dfs(s);
    printf("%lld\n",sum);
    for(int i = sum;i >= 1;i --) printf("%lld %lld\n",ans[i].first,ans[i].second);
    return 0;
}

::::

Edges in MST

看到 MST 考虑 Kruskal。在 Kruskal 的逻辑里，排序后权值为 w 的边能否进入 MST，只取决于它连接的两个端点在当前并查集中是否属于同一连通块，与后面的边无关。\ 那么我们排序之后把权值 w 的边放在一起处理。如果已经在同一连通块：说明 u\to v 存在一条只由权值 <w 的边构成的路径。那么这条边就可以被更小的边替代，因此不在任何 MST 中，故它是 none。不然的话它一定存在于某一个 MST。 ::::info[证明]{open} 假设存在一棵 MST 包含 (u,v,w)。我们从 MST 中删除 (u,v,w)，树分裂成两个连通分量 A,B，且 u\in A，v\in B。\ 因为 u 和 v 通过一条只由权值 <w 的边构成的路径 P 连通，所以 P 从 A 中的 u 出发，到 B 中的 v 结束。路径 P 必然经过边 e=(x,y,w')，其中 x\in A,y\in B,w'<w。考虑