【
題意】理解了半天……大意就是，有一些房間，初始時某些房間之間有一些門，并且這些門是打開的，也就是可以來回走動的，但是這些門是確切屬于某個房間的，也就是說如果要鎖門，則只有在那個房間里才能鎖。 現在一些房間里有一些恐怖分子，要搞破壞，但是現在有個房間很重要，不能被他們破壞，這就需要鎖一部分的門，不讓恐怖分子有可趁之機，求最少需要鎖多少個門。 【
建圖】 這個一看就能聯想到最小割……但是建圖還是需要注意一些地方。從恐怖分子到重要房間我們就能聯想到s->t流，所以建一個源點連接所有恐怖分子所在房間，然后匯點便是那個保護的房間。然后需要處理邊了~
對于每個門的描述(u, v)，其中u可以控制鎖的開關，也就是說恐怖分子從u是一定能夠走到v的，這條邊不能被割，所以我們連一條(u, v, oo)的邊，同時，如果恐怖分子從v往u走，那么我們可以鎖門，所以再連一條(v, u, 1)的邊~然后求最小割就好~如果最小割oo則輸出PANIC ROOM BREACH。偏最小二乘建模的思想與步驟、 ?
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXV = 50;
const int MAXE = 2005;
const int oo = 0x3fffffff;/* Dinic-2.0-2013.07.21: adds template. double & int 轉換方便多了，也不易出錯 ~*/
template
struct Dinic{struct node{int u, v;T flow;int opp;int next;}arc[2*MAXE];int vn, en, head[MAXV];int cur[MAXV];int q[MAXV];int path[2*MAXE], top;int dep[MAXV];void init(int n){vn = n;en = 0;mem(head, -1);}void insert_flow(int u, int v, T flow){arc[en].u = u;arc[en].v = v;arc[en].flow = flow;arc[en].next = head[u];head[u] = en ++;arc[en].u = v;arc[en].v = u;arc[en].flow = 0;arc[en].next = head[v];head[v] = en ++;}bool bfs(int s, int t){mem(dep, -1);int lq = 0, rq = 1;dep[s] = 0;q[lq] = s;while(lq < rq){int u = q[lq ++];if (u == t){return true;}for (int i = head[u]; i != -1; i = arc[i].next){int v = arc[i].v;if (dep[v] == -1 && arc[i].flow > 0){dep[v] = dep[u] + 1;q[rq ++] = v;}}}return false;}T solve(int s, int t){T maxflow = 0;while(bfs(s, t)){int i, j;for (i = 1; i <= vn; i ++) cur[i] = head[i];for (i = s, top = 0;;){if (i == t){int mink;T minflow = 0x7fffffff; //要比容量的oo大for (int k = 0; k < top; k ++)if (minflow > arc[path[k]].flow){minflow = arc[path[k]].flow;mink = k;}for (int k = 0; k < top; k ++)arc[path[k]].flow -= minflow, arc[path[k]^1].flow += minflow;maxflow += minflow;top = mink;i = arc[path[top]].u;}for (j = cur[i]; j != -1; cur[i] = j = arc[j].next){int v = arc[j].v;if (arc[j].flow && dep[v] == dep[i] + 1)break;}if (j != -1){path[top ++] = j;i = arc[j].v;}else{if (top == 0) break;dep[i] = -1;i = arc[path[-- top]].u;}}}return maxflow;}
};
Dinic dinic;int main(){//freopen("test.in", "r", stdin);//freopen("test.out", "w", stdout);int t;scanf("%d", &t);while(t --){int n, m;scanf("%d %d", &n, &m);m ++;dinic.init(n+1);int sum = 0;for (int i = 1; i <= n; i ++){char str[5];int num;scanf("%s %d", str, &num);sum += num;if (str[0] == 'I'){dinic.insert_flow(n+1, i, oo);}for (int j = 0; j < num; j ++){int tmp;scanf("%d", &tmp);dinic.insert_flow(i, tmp+1, oo);dinic.insert_flow(tmp+1, i, 1);}}int res = dinic.solve(n+1, m);if (res > sum){puts("PANIC ROOM BREACH");}else{printf("%d\n", res);}}return 0;
}
?
