题解

题面描述

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

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

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

题目内容

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

我们将资源种类从 $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$ 也得以继续执行；

• 无进程处于死锁状态