题解：BISHI38 有向二分图构造
题目链接
题目描述
给定一张有向图，含 个点与
条有向边。需要给每个点染成黑或白两色。若一条边的起点为黑色、终点为白色，则称其为“核心边”。请构造一种染色方案，使得核心边的条数不少于
，并输出你构造方案下所有核心边的编号（按输入顺序从
到
编号）。保证至少存在一种可行解。
解题思路
随机将每个点独立地以 概率染黑 / 染白时，任意一条边成为“黑
白”的概率是
，因此核心边条数的期望为
，从而存在一份染色使核心边不少于
。我们用“条件期望法”进行完全去随机化，线性时间即可构造：
- 设当前已为部分点定色，其余点未定。对一个未定点
：
- 若将其染黑，则它指向的“已定为白”的出边全部计入答案；指向“未定”点的每条出边以
的期望贡献记入；
- 若将其染白，则指向它的“已定为黑”的入边全部计入答案；来自“未定”点的每条入边以
- 若将其染黑，则它指向的“已定为白”的出边全部计入答案；指向“未定”点的每条出边以
- 我们在两种选择中取期望贡献较大的那一种，并据此把点
。
实现要点：
- 需要维护每个未定点
（指向未定点的出边数）、
（指向已定白点的出边数）、
（来自未定点的入边数）、
（来自已定黑点的入边数）。
- 比较
与
，前者大就染黑，否则染白。
- 所有点定色后，再线性扫描所有边，输出起点黑且终点白的边编号。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--) {
int n, m;
cin >> n >> m;
vector<pair<int,int>> edges(m+1);
vector<vector<int>> outG(n+1), inG(n+1);
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
edges[i] = {u, v};
outG[u].push_back(v);
inG[v].push_back(u);
}
vector<int> color(n+1, -1), decided(n+1, 0);
vector<int> outUndec(n+1), inUndec(n+1), outWhite(n+1, 0), inBlack(n+1, 0);
for (int i = 1; i <= n; ++i) {
outUndec[i] = (int)outG[i].size();
inUndec[i] = (int)inG[i].size();
}
for (int i = 1; i <= n; ++i) {
long long sBlack = 2LL * outWhite[i] + outUndec[i];
long long sWhite = 2LL * inBlack[i] + inUndec[i];
if (sBlack >= sWhite) {
color[i] = 0; // 黑
} else {
color[i] = 1; // 白
}
decided[i] = 1;
// 更新与 i 相邻的未定点统计
if (color[i] == 0) {
// i 为黑：其出边使目标点的 inBlack 增加
for (int v : outG[i]) if (!decided[v]) {
--inUndec[v];
++inBlack[v];
}
for (int u : inG[i]) if (!decided[u]) {
--outUndec[u];
}
} else {
// i 为白：其入边使源点的 outWhite 增加
for (int v : outG[i]) if (!decided[v]) {
--inUndec[v];
}
for (int u : inG[i]) if (!decided[u]) {
--outUndec[u];
++outWhite[u];
}
}
}
vector<int> ans;
ans.reserve(m);
for (int i = 1; i <= m; ++i) {
int u = edges[i].first, v = edges[i].second;
if (color[u] == 0 && color[v] == 1) ans.push_back(i);
}
cout << (int)ans.size() << '\n';
for (int i = 0; i < (int)ans.size(); ++i) {
if (i) cout << ' ';
cout << ans[i];
}
cout << '\n';
}
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { this.in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
long nextLong() throws IOException {
int c; long sgn = 1, x = 0;
do { c = read(); } while (c <= 32);
if (c == '-') { sgn = -1; c = read(); }
while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
return x * sgn;
}
int nextInt() throws IOException { return (int) nextLong(); }
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
StringBuilder sb = new StringBuilder();
int T = fs.nextInt();
while (T-- > 0) {
int n = fs.nextInt();
int m = fs.nextInt();
int[] eu = new int[m + 1];
int[] ev = new int[m + 1];
List<Integer>[] outG = new ArrayList[n + 1];
List<Integer>[] inG = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) { outG[i] = new ArrayList<>(); inG[i] = new ArrayList<>(); }
for (int i = 1; i <= m; i++) {
int u = fs.nextInt();
int v = fs.nextInt();
eu[i] = u; ev[i] = v;
outG[u].add(v);
inG[v].add(u);
}
int[] color = new int[n + 1];
int[] decided = new int[n + 1];
Arrays.fill(color, -1);
int[] outUndec = new int[n + 1];
int[] inUndec = new int[n + 1];
int[] outWhite = new int[n + 1];
int[] inBlack = new int[n + 1];
for (int i = 1; i <= n; i++) {
outUndec[i] = outG[i].size();
inUndec[i] = inG[i].size();
}
for (int i = 1; i <= n; i++) {
long sBlack = 2L * outWhite[i] + outUndec[i];
long sWhite = 2L * inBlack[i] + inUndec[i];
color[i] = (sBlack >= sWhite) ? 0 : 1;
decided[i] = 1;
if (color[i] == 0) {
for (int v : outG[i]) if (decided[v] == 0) { inUndec[v]--; inBlack[v]++; }
for (int u : inG[i]) if (decided[u] == 0) { outUndec[u]--; }
} else {
for (int v : outG[i]) if (decided[v] == 0) { inUndec[v]--; }
for (int u : inG[i]) if (decided[u] == 0) { outUndec[u]--; outWhite[u]++; }
}
}
int cnt = 0;
for (int i = 1; i <= m; i++) if (color[eu[i]] == 0 && color[ev[i]] == 1) cnt++;
sb.append(cnt).append('\n');
int printed = 0;
for (int i = 1; i <= m; i++) {
if (color[eu[i]] == 0 && color[ev[i]] == 1) {
if (printed++ > 0) sb.append(' ');
sb.append(i);
}
}
sb.append('\n');
}
System.out.print(sb.toString());
}
}
import sys
def solve():
data = sys.stdin.buffer.read().split()
it = iter(data)
T = int(next(it))
out_lines = []
for _ in range(T):
n = int(next(it)); m = int(next(it))
eu = [0]*(m+1); ev = [0]*(m+1)
outG = [[] for _ in range(n+1)]
inG = [[] for _ in range(n+1)]
for i in range(1, m+1):
u = int(next(it)); v = int(next(it))
eu[i] = u; ev[i] = v
outG[u].append(v)
inG[v].append(u)
color = [-1]*(n+1)
decided = [0]*(n+1)
outUndec = [0]*(n+1)
inUndec = [0]*(n+1)
outWhite = [0]*(n+1)
inBlack = [0]*(n+1)
for i in range(1, n+1):
outUndec[i] = len(outG[i])
inUndec[i] = len(inG[i])
for i in range(1, n+1):
sBlack = 2*outWhite[i] + outUndec[i]
sWhite = 2*inBlack[i] + inUndec[i]
color[i] = 0 if sBlack >= sWhite else 1
decided[i] = 1
if color[i] == 0:
for v in outG[i]:
if decided[v] == 0:
inUndec[v] -= 1
inBlack[v] += 1
for u in inG[i]:
if decided[u] == 0:
outUndec[u] -= 1
else:
for v in outG[i]:
if decided[v] == 0:
inUndec[v] -= 1
for u in inG[i]:
if decided[u] == 0:
outUndec[u] -= 1
outWhite[u] += 1
ans = [str(i) for i in range(1, m+1) if color[eu[i]] == 0 and color[ev[i]] == 1]
out_lines.append(str(len(ans)))
out_lines.append(' '.join(ans))
sys.stdout.write('\n'.join(out_lines))
if __name__ == '__main__':
solve()
算法及复杂度
- 算法：条件期望法去随机化；顺序定点颜色并维护局部统计，最终核心边数不少于
- 时间复杂度：
每组
- 空间复杂度：
京公网安备 11010502036488号