题目链接
题目描述
在一个工人和任务的分配场景中，每个工人 W 初始负责任务 T。此外还有一些“跨职能”的分配关系。一个初始分配 W -> T 被认为是“不稳定”的，如果去掉这条分配后，仍然能让所有工人完成所有任务（即存在一个完美匹配）。否则，该分配是“稳定”的。需要判断每个初始分配的稳定性。
解题思路
这是一个关于二分图完美匹配中边的性质判断问题。如果逐一删除每条边并重新计算最大匹配，对于 高达
的数据规模，复杂度过高。我们需要一种更高效的算法。这个问题的标准解法是结合完美匹配和强连通分量 (SCC)。
核心思想
-
二分图建模：
- 工人和任务构成二分图的两个顶点集。
- “所有工人完成所有任务”等价于图中存在一个大小为
N的完美匹配。
-
稳定性定义：
- 一个初始分配
W -> T是稳定的，意味着这条边必须存在于任何一个完美匹配中。 - 一个初始分配
W -> T是不稳定的，意味着存在至少一个完美匹配不包含这条边。
- 一个初始分配
-
关键洞察与算法：
题目中给出的
n条初始分配W_i -> T_i本身就已经构成了一个完美匹配。我们无需去计算，可以直接利用这个已知的匹配M。我们可以通过以下步骤来高效判断所有初始分配的稳定性：
a. 构建有向图 D：基于初始的完美匹配
M和m条跨职能关系，构建一个有向图D。规则如下:-
对于每一条在完美匹配
M中的初始分配(W_i, T_i)，我们添加一条从任务到工人的有向边T_i -> W_i。 -
对于每一条不在
M中的跨职能关系(W_x, T_y)，我们添加一条从工人到任务的有向边W_x -> T_y。
b. 寻找 SCC：在这个有向图
D上运行 Tarjan 算法，找出所有的强连通分量。c. 判断稳定性：
-
对于一个初始分配
(W_i, T_i)，如果其对应的两个顶点W_i和T_i在有向图D中属于同一个强连通分量，这说明它们处在一个“交错环”上，可以通过调整环上的匹配来构造一个不包含(W_i, T_i)的新完美匹配。因此，该分配是不稳定 (Unstable)。 -
如果它们不属于同一个强连通分量，说明这条边是连接两个部分的“桥”，是所有完美匹配的必经之路。因此，它是稳定 (Stable)。
-
这个算法的时间复杂度为 ，完全可以满足题目的要求。
代码
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX_NODES = 200005;
// For Tarjan's SCC
vector<int> directed_adj[MAX_NODES];
int dfn[MAX_NODES], low[MAX_NODES], scc_id[MAX_NODES];
bool in_stack[MAX_NODES];
stack<int> st;
int timer, scc_count;
int n;
void tarjan(int u) {
dfn[u] = low[u] = ++timer;
st.push(u);
in_stack[u] = true;
for (int v : directed_adj[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
scc_count++;
int node;
do {
node = st.top();
st.pop();
in_stack[node] = false;
scc_id[node] = scc_count;
} while (node != u);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
map<string, int> name_to_id;
vector<pair<string, string>> initial_pairs(n);
int id_counter = 1;
// Workers: 1 to n
// Tasks: n+1 to 2n
for (int i = 0; i < n; ++i) {
string worker_name, task_name;
cin >> worker_name >> task_name;
int worker_id, task_id;
if (name_to_id.find(worker_name) == name_to_id.end()) {
name_to_id[worker_name] = id_counter++;
}
worker_id = name_to_id[worker_name];
if (name_to_id.find(task_name) == name_to_id.end()) {
name_to_id[task_name] = id_counter++;
}
task_id = name_to_id[task_name];
// Initial matching edge: T -> W
directed_adj[task_id].push_back(worker_id);
initial_pairs[i] = {worker_name, task_name};
}
int m;
cin >> m;
for (int i = 0; i < m; ++i) {
string worker_name, task_name;
cin >> worker_name >> task_name;
int u = name_to_id[worker_name];
int v = name_to_id[task_name];
// Cross-functional edge: W -> T
directed_adj[u].push_back(v);
}
// Find SCCs on the directed graph
for (int i = 1; i <= 2 * n; ++i) {
if (!dfn[i]) {
tarjan(i);
}
}
// Check stability
for (const auto& p : initial_pairs) {
int worker_id = name_to_id[p.first];
int task_id = name_to_id[p.second];
if (scc_id[worker_id] == scc_id[task_id]) {
cout << "Unstable\n";
} else {
cout << "Stable\n";
}
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
static List<List<Integer>> directedAdj;
static int[] dfn, low, sccId;
static boolean[] inStack;
static Stack<Integer> st;
static int timer, sccCount;
static int n;
static void tarjan(int u) {
dfn[u] = low[u] = ++timer;
st.push(u);
inStack[u] = true;
for (int v : directedAdj.get(u)) {
if (dfn[v] == 0) {
tarjan(v);
low[u] = Math.min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = Math.min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
sccCount++;
int node;
do {
node = st.pop();
inStack[node] = false;
sccId[node] = sccCount;
} while (node != u);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
Map<String, Integer> nameToId = new HashMap<>();
List<String[]> initialPairs = new ArrayList<>();
int idCounter = 1;
directedAdj = new ArrayList<>();
for (int i = 0; i <= 2 * n; i++) directedAdj.add(new ArrayList<>());
for (int i = 0; i < n; i++) {
StringTokenizer st_in = new StringTokenizer(br.readLine());
String workerName = st_in.nextToken();
String taskName = st_in.nextToken();
if (!nameToId.containsKey(workerName)) nameToId.put(workerName, idCounter++);
if (!nameToId.containsKey(taskName)) nameToId.put(taskName, idCounter++);
int workerId = nameToId.get(workerName);
int taskId = nameToId.get(taskName);
// Initial matching edge: T -> W
directedAdj.get(taskId).add(workerId);
initialPairs.add(new String[]{workerName, taskName});
}
int m = Integer.parseInt(br.readLine());
for (int i = 0; i < m; i++) {
StringTokenizer st_in = new StringTokenizer(br.readLine());
String workerName = st_in.nextToken();
String taskName = st_in.nextToken();
int u = nameToId.get(workerName);
int v = nameToId.get(taskName);
// Cross-functional edge: W -> T
directedAdj.get(u).add(v);
}
dfn = new int[2 * n + 1];
low = new int[2 * n + 1];
sccId = new int[2 * n + 1];
inStack = new boolean[2 * n + 1];
st = new Stack<>();
timer = 0;
sccCount = 0;
for (int i = 1; i <= 2 * n; i++) {
if (dfn[i] == 0) tarjan(i);
}
PrintWriter out = new PrintWriter(System.out);
for (String[] p : initialPairs) {
int workerId = nameToId.get(p[0]);
int taskId = nameToId.get(p[1]);
if (sccId[workerId] == sccId[taskId]) {
out.println("Unstable");
} else {
out.println("Stable");
}
}
out.flush();
}
}
import sys
# It's necessary to increase recursion limit for deep graphs
sys.setrecursionlimit(200005 * 2)
def solve():
try:
n_str = sys.stdin.readline()
if not n_str: return
n = int(n_str)
except (IOError, ValueError):
return
name_to_id = {}
id_counter = 1
initial_pairs = []
directed_adj = [[] for _ in range(2 * n + 1)]
for _ in range(n):
worker_name, task_name = sys.stdin.readline().split()
if worker_name not in name_to_id:
name_to_id[worker_name] = id_counter
id_counter += 1
if task_name not in name_to_id:
name_to_id[task_name] = id_counter
id_counter += 1
worker_id = name_to_id[worker_name]
task_id = name_to_id[task_name]
# Initial matching edge: T -> W
directed_adj[task_id].append(worker_id)
initial_pairs.append((worker_name, task_name))
m_str = sys.stdin.readline()
if not m_str: m = 0
else: m = int(m_str)
for _ in range(m):
worker_name, task_name = sys.stdin.readline().split()
u = name_to_id[worker_name]
v = name_to_id[task_name]
# Cross-functional edge: W -> T
directed_adj[u].append(v)
dfn = [0] * (2 * n + 1)
low = [0] * (2 * n + 1)
scc_id = [0] * (2 * n + 1)
in_stack = [False] * (2 * n + 1)
stack = []
timer = 0
scc_count = 0
def tarjan(u):
nonlocal timer, scc_count
timer += 1
dfn[u] = low[u] = timer
stack.append(u)
in_stack[u] = True
for v in directed_adj[u]:
if dfn[v] == 0:
tarjan(v)
low[u] = min(low[u], low[v])
elif in_stack[v]:
low[u] = min(low[u], dfn[v])
if dfn[u] == low[u]:
scc_count += 1
while True:
node = stack.pop()
in_stack[node] = False
scc_id[node] = scc_count
if node == u:
break
for i in range(1, 2 * n + 1):
if dfn[i] == 0:
tarjan(i)
for worker_name, task_name in initial_pairs:
worker_id = name_to_id[worker_name]
task_id = name_to_id[task_name]
if scc_id[worker_id] == scc_id[task_id]:
print("Unstable")
else:
print("Stable")
solve()
算法及复杂度
- 算法：强连通分量 (Tarjan 算法)
- 时间复杂度：
。其中
是工人数，
是跨职能关系数。
- 字符串到ID的映射：
- 构建有向图：
- Tarjan 算法：
- 总复杂度是线性的。
- 字符串到ID的映射：
- 空间复杂度：
京公网安备 11010502036488号