题意：给定若干个房间，现在这些房间之间能够相互的联通，房间门是单向的，现在问一些门中都有人的情况下，至少要堵住多少条门才能够使得无法到达终点。
解法：显然这是一个集合的分割问题，即求这样的一个割：使得终点房间与某些存在人的房间的一个分割，题中求的最少的人就是求解一个最小割。将问题转化为网络流求解。通过建立从超级源点到存在人的一些房间，那么从汇点反向遍历寻找这样的一个割。如果从源点到有人房间的边满流，那么反向遍历一定不会将这个节点划分到汇点集合里面去，如果该边不满流的话，如果划分到了汇点集合，则表明存在从源点到汇点的流量，于最大流相悖。因此所求既满足题意。
代码如下：
#include#include #include #include #include using namespace std;int N, M, TT;const int SS = 40;const int INF = 0x3fffffff;struct Edge { int v, c, next; };Edge e[10000];int idx, head[50];int lv[50], que[50];int front, tail;void insert(int a, int b, int c) { e[idx].v = b, e[idx].c = c; e[idx].next = head[a]; head[a] = idx++;}bool bfs() { front = tail = 0; memset(lv, 0xff, sizeof (lv)); lv[SS] = 1; que[tail++] = SS; while (front < tail) { int u = que[front++]; for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; if (!(~lv[v]) && e[i].c) { lv[v] = lv[u] + 1; if (v == TT) return true; que[tail++] = v; } } } return false;}int dfs(int u, int sup) { if (u == TT) return sup; int tf = 0, f; for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; if (lv[u]+1==lv[v] && e[i].c && (f=dfs(v, min(e[i].c, sup-tf)))) { tf += f; e[i].c -= f, e[i^1].c += f; if (tf == sup) return sup; } } if (!tf) lv[u] = -1; return tf;}int dinic() { int ret = 0; while (bfs()) { ret += dfs(SS, INF); } return ret;}int main() { int T; scanf("%d", &T); while (T--) { int x, y; char op[5]; idx = 0; memset(head, 0xff, sizeof (head)); scanf("%d %d", &M, &N); TT = N; for (int i = 0; i < M; ++i) { scanf("%s %d", op, &x); if (op[0] == 'I') { // 在x点有敌人潜入 insert(SS, i, INF); insert(i, SS, 0); } for (int j = 0; j < x; ++j) { scanf("%d", &y); insert(i, y, INF); insert(y, i, 1); } } int ans = dinic(); if (ans < INF) { printf("%d\n", ans); } else { puts("PANIC ROOM BREACH"); } } return 0; }