题解 | #有向二分图构造#

题目链接

题目描述

给定一个包含 $N$ 个点和 $M$ 条边的有向图。你需要为每个点染上黑色或白色。一条边被称为“核心边”，当且仅当它的起点是黑色，终点是白色。

你的任务是构造一种染色方案，使得图中的核心边数量不少于 $\lfloor M/4 \rfloor + 1$ 。你需要输出你构造方案下的核心边总数，以及所有核心边的编号。

解题思路

题目的目标是构造一个染色方案，使得核心边的数量达到一个下限 $\lfloor M/4 \rfloor + 1$ 。这是一个构造性问题，可以通过一个基于贪心和概率期望思想的精巧算法来解决。

首先，考虑一个完全随机的染色方案：为每个节点独立地、等概率地（1/2）选择染成黑色或白色。对于任意一条边 $(u, v)$ ，它成为核心边（即 $u$ 为黑， $v$ 为白）的概率是 $P(u=\text{黑}) \cdot P(v=\text{白}) = 1/2 \cdot 1/2 = 1/4$ 。根据期望的线性性质，所有 $M$ 条边的期望核心边总数就是 $M/4$ 。

题目保证存在一个解，其核心边数量至少为 $\lfloor M/4 \rfloor + 1$ ，这比随机期望值略高。我们可以使用一种称为 “条件期望法”（Method of Conditional Expectations）的derandomization技术，来确定性地构造一个达到甚至超过这个期望的解。

该方法的核心思想是，将一个概率过程转化为一个确定性的贪心算法。我们按顺序为每个节点选择颜色，每一步都做出一个“局部最优”的决策，以保证最终结果不坏于期望值。

算法流程：

顺序决策：我们按节点编号 $v = 1, 2, \dots, N$ 的顺序，依次为每个节点确定颜色。
贪心选择：当决定节点 $v$ 的颜色时，我们比较将它染成黑色和白色的“收益”，然后选择收益更高的那个。这个收益是根据已经确定的颜色（节点编号 $< v$ ）和尚未确定的颜色（节点编号 $> v$ ）的期望来计算的。
- 染成黑色的收益 (score_black)：
  - 确定的收益：来自与已染色节点（ $u < v$ ）形成的边。对于每条出边 $v \to u$ ，如果 $u$ 已被染成白色，则获得 1 分。
  - 期望的收益：来自与未染色节点（ $w > v$ ）形成的边。对于每条出边 $v \to w$ ，由于 $w$ 未来被染成白色的概率是 1/2，这里期望收益是 0.5 分。
- 染成白色的收益 (score_white)：
  - 确定的收益：对于每条入边 $u \to v$ ，如果 $u$ 已被染成黑色，则获得 1 分。
  - 期望的收益：对于每条入边 $w \to v$ ，由于 $w$ 未来被染成黑色的概率是 1/2，这里期望收益是 0.5 分。
颜色确定与实现：
- 为了避免浮点数计算，我们将所有收益乘以 2。
- 对于节点 $v$ ：
  - score_black = 2 * (v 指向的已染白色的邻居 u<v 的数量) + (v 指向的未染色邻居 w>v 的数量)
  - score_white = 2 * (指向 v 的已染黑色的邻居 u<v 的数量) + (指向 v 的未染色邻居 w>v 的数量)
- 如果 score_black >= score_white，则将节点 $v$ 染成黑色；否则染成白色。
- 这个贪心选择保证了我们每一步都在最大化最终核心边数量的条件期望值。
输出结果：当所有 $N$ 个节点的颜色都确定后，我们再完整地遍历一次所有 $M$ 条边，找出所有实际形成的核心边（起点黑，终点白），并输出它们的编号。

该算法的整体时间复杂度为 $\mathcal{O}(N+M)$ ，因为在决策阶段，我们需要遍历每个节点的邻居一次。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

// 定义节点颜色
const int UNCOLORED = 0;
const int BLACK = 1;
const int WHITE = 2;

struct Edge {
    int u, v, id;
};

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<Edge> all_edges;
    std::vector<std::vector<int>> adj(n + 1), rev_adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        all_edges.push_back({u, v, i + 1});
        adj[u].push_back(v);
        rev_adj[v].push_back(u);
    }

    std::vector<int> colors(n + 1, UNCOLORED);

    for (int v = 1; v <= n; ++v) {
        long long score_black = 0;
        long long score_white = 0;

        // 计算染黑的收益
        for (int neighbor : adj[v]) {
            if (neighbor < v) { // 邻居已染色
                if (colors[neighbor] == WHITE) {
                    score_black += 2;
                }
            } else { // 邻居未染色
                score_black += 1;
            }
        }

        // 计算染白的收益
        for (int neighbor : rev_adj[v]) {
            if (neighbor < v) { // 邻居已染色
                if (colors[neighbor] == BLACK) {
                    score_white += 2;
                }
            } else { // 邻居未染色
                score_white += 1;
            }
        }
        
        if (score_black >= score_white) {
            colors[v] = BLACK;
        } else {
            colors[v] = WHITE;
        }
    }

    std::vector<int> core_edges;
    for (const auto& edge : all_edges) {
        if (colors[edge.u] == BLACK && colors[edge.v] == WHITE) {
            core_edges.push_back(edge.id);
        }
    }

    std::cout << core_edges.size() << "\n";
    for (int i = 0; i < core_edges.size(); ++i) {
        std::cout << core_edges[i] << (i == core_edges.size() - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static final int UNCOLORED = 0;
    static final int BLACK = 1;
    static final int WHITE = 2;

    static class Edge {
        int u, v, id;
        Edge(int u, int v, int id) {
            this.u = u;
            this.v = v;
            this.id = id;
        }
    }

    public static void main(String[] args) throws IOException {
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc, out);
        }
        out.flush();
    }

    private static void solve(FastReader sc, PrintWriter out) throws IOException {
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        List<Edge> allEdges = new ArrayList<>();
        List<List<Integer>> adj = new ArrayList<>(n + 1);
        List<List<Integer>> revAdj = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
            revAdj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            allEdges.add(new Edge(u, v, i + 1));
            adj.get(u).add(v);
            revAdj.get(v).add(u);
        }

        int[] colors = new int[n + 1]; // 默认全为 UNCOLORED

        for (int v = 1; v <= n; v++) {
            long scoreBlack = 0;
            long scoreWhite = 0;

            for (int neighbor : adj.get(v)) {
                if (neighbor < v) {
                    if (colors[neighbor] == WHITE) scoreBlack += 2;
                } else {
                    scoreBlack += 1;
                }
            }

            for (int neighbor : revAdj.get(v)) {
                if (neighbor < v) {
                    if (colors[neighbor] == BLACK) scoreWhite += 2;
                } else {
                    scoreWhite += 1;
                }
            }

            if (scoreBlack >= scoreWhite) {
                colors[v] = BLACK;
            } else {
                colors[v] = WHITE;
            }
        }

        List<Integer> coreEdges = new ArrayList<>();
        for (Edge edge : allEdges) {
            if (colors[edge.u] == BLACK && colors[edge.v] == WHITE) {
                coreEdges.add(edge.id);
            }
        }

        out.println(coreEdges.size());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < coreEdges.size(); i++) {
            sb.append(coreEdges.get(i));
            if (i < coreEdges.size() - 1) {
                sb.append(" ");
            }
        }
        out.println(sb.toString());
    }
    
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

import sys

UNCOLORED, BLACK, WHITE = 0, 1, 2

def solve():
    line = sys.stdin.readline()
    if not line.strip(): return
    n, m = map(int, line.split())
    
    all_edges = []
    adj = [[] for _ in range(n + 1)]
    rev_adj = [[] for _ in range(n + 1)]

    for i in range(m):
        u, v = map(int, sys.stdin.readline().split())
        all_edges.append((u, v, i + 1))
        adj[u].append(v)
        rev_adj[v].append(u)

    colors = [UNCOLORED] * (n + 1)

    for v in range(1, n + 1):
        score_black = 0
        score_white = 0

        for neighbor in adj[v]:
            if neighbor < v:
                if colors[neighbor] == WHITE:
                    score_black += 2
            else:
                score_black += 1
        
        for neighbor in rev_adj[v]:
            if neighbor < v:
                if colors[neighbor] == BLACK:
                    score_white += 2
            else:
                score_white += 1

        if score_black >= score_white:
            colors[v] = BLACK
        else:
            colors[v] = WHITE

    core_edges = []
    for u, v, edge_id in all_edges:
        if colors[u] == BLACK and colors[v] == WHITE:
            core_edges.append(edge_id)
    
    print(len(core_edges))
    print(' '.join(map(str, core_edges)))


def main():
    t_str = sys.stdin.readline()
    if not t_str.strip(): return
    t = int(t_str)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法: 贪心算法、条件期望法
时间复杂度: $\mathcal{O}(T \cdot (N+M))$ ，其中 $T$ 是测试数据组数。对于每组数据，构造颜色方案需要遍历所有边一次（均摊到每个点上），最后统计答案需要再遍历所有边一次。
空间复杂度: $\mathcal{O}(N+M)$ ，用于存储图的邻接表和所有边。