题解

题面描述

计算机进程运行时必须使用某些不能共享的资源，在获取到所有必须资源之前，都不会释放已持有的资源；然而资源的总数是有限的，多个进程容易出现先持有部分资源、循环等待其他进程释放资源、进而导致所有进程都处于阻塞状态的情况，称之为死锁。

• 共有 $m$ 种资源，编号为 $1$ 到 $m$，第 $j$ 种资源的可用（未被持有）数量为 $a_j$。
• 共有 $n$ 个进程，编号为 $1$ 到 $n$。第 $i$ 个进程已持有 $h_i$ 种资源，第 $i$ 个进程对第 $hr_{ij}$ 种资源持有 $hc_{ij}$ 个；同时它等待 $w_i$ 种资源，第 $wr_{ij}$ 种资源还需要 $wc_{ij}$ 个。

当某个进程的所有等待资源都可满足时，该进程即可执行并释放它已持有的所有资源，释放后这些资源数目加入全局的可用量中。若在按此策略反复执行所有可运行进程后，仍有进程等待资源，则这些剩余等待的进程即为死锁进程。

思路

1. 初始化可用资源数组 $A[1\dots m]=\{a_j\}$。
2. 对每个进程 $i$ 维护一个计数器 $rem[i]$，表示“当前可用资源不足以满足它的等待需求”的资源种类数。
3. 首先遍历每种资源 $r$，对所有等待 $r$ 的进程 $(i,need)$：
   • 若 $A[r] < need$，则令 $rem[i]++$。
4. 将所有 $rem[i]=0$ 的进程加入队列，它们可立即执行。
5. 队列非空时，取出进程 $i$：
   • 对它已持有的每种资源 $(r,c)$，先记 $old=A[r]$，再更新 $A[r]+=c$。
   • 然后检查所有等待资源 $r$ 的进程 $(j,need)$：
     • 若进程 $j$ 尚未执行，且 $old<need\le A[r]$，则令 $rem[j]--$；
     • 若此时 $rem[j]=0$，将其加入队列。
6. 最终所有未执行（$rem[i]>0$）的进程即为死锁进程。

该算法类似“资源可满足”版的拓扑排序，时间复杂度 $O\bigl(\sum h_i+\sum w_i + n+m\bigr)$，可应对 $n,m\le10^5$。

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<ll> av(m+1);
    for(int i = 1; i <= m; i++)
        cin >> av[i];

    // h[i]: 进程 i 持有的资源列表 (资源编号, 数量)
    // w[r]: 等待资源 r 的进程列表 (进程编号, 需要数量)
    vector<vector<pair<int,ll>>> h(n+1), w(m+1);
    vector<int> rem(n+1, 0);

    for(int i = 1; i <= n; i++){
        int hi; 
        cin >> hi;
        while(hi--){
            int r; ll c;
            cin >> r >> c;
            h[i].emplace_back(r, c);
        }
        int wi;
        cin >> wi;
        while(wi--){
            int r; ll c;
            cin >> r >> c;
            w[r].emplace_back(i, c);
        }
    }

    queue<int> q;
    vector<char> done(n+1, 0);

    // 初始化 rem[i]
    for(int r = 1; r <= m; r++){
        for(auto &p : w[r]){
            int i = p.first;
            ll need = p.second;
            if(av[r] < need)
                rem[i]++;
        }
    }
    // 入队所有可执行的进程
    for(int i = 1; i <= n; i++){
        if(rem[i] == 0){
            done[i] = 1;
            q.push(i);
        }
    }

    // 模拟执行并释放资源
    while(!q.empty()){
        int i = q.front(); q.pop();
        for(auto &p : h[i]){
            int r = p.first;
            ll c = p.second;
            ll prev = av[r];
            av[r] += c;
            for(auto &p2 : w[r]){
                int j = p2.first;
                ll need = p2.second;
                if(!done[j] && prev < need && av[r] >= need){
                    if(--rem[j] == 0){
                        done[j] = 1;
                        q.push(j);
                    }
                }
            }
        }
    }

    // 收集死锁进程
    vector<int> dead;
    for(int i = 1; i <= n; i++){
        if(!done[i])
            dead.push_back(i);
    }

    // 输出
    cout << dead.size() << "\n";
    if(!dead.empty()){
        for(int k = 0; k < (int)dead.size(); k++){
            if(k) cout << " ";
            cout << dead[k];
        }
        cout << "\n";
    }
    return 0;
}

Python

from collections import deque, defaultdict
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    # 可用资源 A[1..m]
    A = [0] + list(map(int, input().split()))

    # h[i]: 进程 i 持有的 [(资源, 数量), ...]
    # w[r]: 等待资源 r 的 [(进程, 需要量), ...]
    h = [[] for _ in range(n+1)]
    w = [[] for _ in range(m+1)]
    rem = [0]*(n+1)

    for i in range(1, n+1):
        hi, *rest = map(int, input().split())
        for j in range(hi):
            r, c = rest[2*j], rest[2*j+1]
            h[i].append((r, c))
        wi, *rest = map(int, input().split())
        for j in range(wi):
            r, c = rest[2*j], rest[2*j+1]
            w[r].append((i, c))

    q = deque()
    done = [False]*(n+1)

    # 初始化 rem
    for r in range(1, m+1):
        for i, need in w[r]:
            if A[r] < need:
                rem[i] += 1

    # 入队 rem[i]==0 的进程
    for i in range(1, n+1):
        if rem[i] == 0:
            done[i] = True
            q.append(i)

    # 模拟执行
    while q:
        i = q.popleft()
        for r, c in h[i]:
            prev = A[r]
            A[r] += c
            for j, need in w[r]:
                if not done[j] and prev < need <= A[r]:
                    rem[j] -= 1
                    if rem[j] == 0:
                        done[j] = True
                        q.append(j)

    # 输出死锁进程
    dead = [i for i in range(1, n+1) if not done[i]]
    print(len(dead))
    if dead:
        print(*dead)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 可用资源 A[1..m]
        long[] A = new long[m+1];
        st = new StringTokenizer(in.readLine());
        for (int i = 1; i <= m; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        // h[i]: 进程 i 持有的资源列表
        List<long[]>[] h = new List[n+1];
        // w[r]: 等待资源 r 的进程列表
        List<long[]>[] w = new List[m+1];
        for (int i = 1; i <= n; i++) h[i] = new ArrayList<>();
        for (int r = 1; r <= m; r++) w[r] = new ArrayList<>();

        int[] rem = new int[n+1];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(in.readLine());
            int hi = Integer.parseInt(st.nextToken());
            for (int j = 0; j < hi; j++) {
                int r = Integer.parseInt(st.nextToken());
                long c = Long.parseLong(st.nextToken());
                h[i].add(new long[]{r, c});
            }
            st = new StringTokenizer(in.readLine());
            int wi = Integer.parseInt(st.nextToken());
            for (int j = 0; j < wi; j++) {
                int r = Integer.parseInt(st.nextToken());
                long c = Long.parseLong(st.nextToken());
                w[r].add(new long[]{i, c});
            }
        }

        Deque<Integer> q = new ArrayDeque<>();
        boolean[] done = new boolean[n+1];

        // 初始化 rem
        for (int r = 1; r <= m; r++) {
            for (long[] p : w[r]) {
                int i = (int)p[0];
                long need = p[1];
                if (A[r] < need) rem[i]++;
            }
        }
        // 入队 rem[i]==0 的进程
        for (int i = 1; i <= n; i++) {
            if (rem[i] == 0) {
                done[i] = true;
                q.add(i);
            }
        }

        // 模拟执行
        while (!q.isEmpty()) {
            int i = q.poll();
            for (long[] p : h[i]) {
                int r = (int)p[0];
                long c = p[1];
                long prev = A[r];
                A[r] += c;
                for (long[] p2 : w[r]) {
                    int j = (int)p2[0];
                    long need = p2[1];
                    if (!done[j] && prev < need && A[r] >= need) {
                        if (--rem[j] == 0) {
                            done[j] = true;
                            q.add(j);
                        }
                    }
                }
            }
        }

        // 收集并输出死锁进程
        List<Integer> dead = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (!done[i]) dead.add(i);
        }
        System.out.println(dead.size());
        if (!dead.isEmpty()) {
            for (int i = 0; i < dead.size(); i++) {
                if (i > 0) System.out.print(" ");
                System.out.print(dead.get(i));
            }
            System.out.println();
        }
    }
}

题目内容

计算机进程运行时必须使用某些不能共享的资源，在获取到所有必须资源之前，都不会释放已持有的资源，然而资源的总数是有限的，多个进程容易出现先持有部分资源、循环等待其他进程释放资源、进而导致所有进程都处于阻塞状态的情况，称之为死锁。

我们将资源种类从 $1$ 到 $m$ 编号，每种资源的未被持有数量为 $a_i$ 。

将进程从 $1$ 到 $n$ 编号，第 $i$ 个进程已持有资源 $h_i$ 种，持有第 $hr_{ij}$ 种资源 $hc_{ij}$ 个，等待资源 $w_i$ 种，等待第 $wr_{ij}$ 种资源 $wc_{ij}$ 个。

当未被持有的资源数满足某个进程的等待资源数时，进程得以执行，执行完成后可释放所有已持有资源，被释放的资源变为未被持有状态。

当所有可释放资源都变为未持有状态，仍有进程处于等待状态时，这些进程被认为处于死锁状态，我们需要找出资源按最优分配情况下，仍然处于死锁状态的进程编号。

输入描述

第一行为两个整数 $n,m(1≤n,m≤10^5)$ ，第二行为 $m$ 个整数 $a_i(0 ≤ a_i ≤ 10^9)$ ，表示每种资源的数量，接下去 $2n$ 行：

• 第 $2i+1$ 行表示第 $i$ 个进程已持有资源情况：第一个整数 $h_i(0 ≤ h_i≤ m)$ ，接下去 $2h_i$ 个整数，第 $2j$ 个整数为 $hr_{ij}(1≤ hr_{ij} ≤m)$ ，第 $2j+1$ 个整数为 $hc_{ij} (1 ≤ hc_{ij}≤ 10^9)$ ；

• 第 $2i+2$ 行表示第 $i$ 个进程等待资源情况：第一个整数 $w_i(0≤ w_i≤m)$ ， 接下去 $2w_i$ 个整数，第 $2j$ 个整数为 $wr_{ij}(1 ≤ wr_{ij} ≤ m)$ ，第 $2j+1$ 个整数为 $wc_{ij}(1 ≤ wc_{ij} ≤ 10^9)$ 。

数据保证 $\sum_{i=1}^n$ $h_i∈[1,10^5]$,$\sum_{i=1}^n$ $w_i∈[1,10^5]$，对于任意 $j_1≠j_2$ ，都有 $hr_{ij_1}≠ hr_{ij_1},wr_{ij_1} ≠wr_{ij_2}$ 。

输出描述

第一行一个整数 $p$ ，表示存在死锁的进程数，第一行 $p$ 个整数，从小到大输出处于死锁状态的进程编号。

补充说明

对于 $60$% 的数据，$1≤n,m ≤ 1000$ ;

对于 $100$% 的数据，$1 ≤ n,m ≤ 10^5$ ，其它数据范围见输入部分。

样例1

输入

3 2
0 0
1 1 2
1 2 2
2 1 1 2 1
1 1 1
1 2 1
0

输出

2
1 2

说明

样例数据如图所示，有 $3$ 个进程 $P_1,P_2,P_3$ 两种资源 $R_1,R_2$ ，橙色圆圈个数表示资源总个数，蓝色边表示等待边，绿色边表示持有边，初始状态所有资源都被持有。

• 进程 $P_3$ 持有资源 $R_2$，执行完成后释放 $R_2$ 资源，此时资源 $R_1$ 剩余 $0$ 个，资源 $R_2$ 剩余 $1$ 个；

• 进程 $P_1$ 等待 $2$ 个 $R_2$ 资源，而 $R_2$ 目前只有 $1$ 个资源，进程 $P_2$ 等待 $1$ 个 $R_1$ 资源，而 $R_1$ 所有资源都被持有无法释放；

• 因此进程 $P_1$ 与 $P_2$ 在循环等待资源释放，都处于死锁状态。

样例2

输入

2 2
0 1
1 1 2
1 2 1
2 1 1 2 1
1 1 1

输出

0

说明

样例数据如图所示，初始状态资源 $R_1$ $3$ 个资源都被持有，资源 $R_2$ $1$ 个被持有，剩余 $1$ 个资源：

• 进程 $P_2$ 等待 $R_1$ 资源，此时 $R_1$ 无资源只能继续等待；

• 进程 $P_1$ 等待 $1$ 个 $R_2$ 资源，正好有一个 $R_2$ 资源可以使用，进程 $P_1$ 继续执行，完成后释放 $2$ 个 $R_1$ 、$1$ 个 $R_2$ 资源，此时剩下 $2$ 个 $R_1$ 资源，$1$ 个 $R_2$ 资源；

• 进程 $P_2$ 等待的 $1$ 个 $R_1$ ， 资源已被 $P_1$ 释放，等待成功，因此 $P_2$ 也得以继续执行；

• 无进程处于死锁状态