POJ 3084 Panic Room （最小割）

題意和分析轉自http://blog.csdn.net/sdj222555/article/details/7798949

大意就是，有一些房間，初始時某些房間之間有一些門，并且這些門是打開的，也就是可以來回走動的，但是這些門是确切屬于某個房間的，也就是說如果要鎖門，則隻有在那個房間裡才能鎖，這跟現實很符合啊，不然随便個人站你家外邊把你門給鎖了是什麼情況。 現在一些房間裡有一些恐怖分子，要搞破壞，但是我們現在有個房間很重要，不能被他們破壞，這就需要鎖一部分的門，不讓恐怖分子有可趁之機，那麼最少需要鎖多個門呢？

很容易聯系到最小割上面，剛開始我沒讀清楚，覺得既然門是可以來回走的，那麼建個雙向邊好了，結果發現不是這樣啊。

假設a->b代表a房間有個門到b，那麼顯然鎖門的控制權在a上，鎖1個門就可以不讓b裡面的人到a去，于是我們就建邊b-a，容量為1，然後再建立邊a->b，容量為無窮大，

為啥為無窮大呢，因為你無論怎麼鎖門，你在a裡邊可以随便開門，随便進入b，是以a->b這條邊是鎖不掉的

然後建立源點，與所有的存在恐怖分子的房間連邊，容量為無窮大，因為題目也說了，可能有很多的鎖很多的恐怖分子。

最後以被保護的那個房間為彙點，求最大流即可

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define INF 0x1f1f1f
typedef  struct {
    int v, next, val;
} edge;
const int MAXN = 20010;
const int MAXM = 500010;
edge e[MAXM];
int p[MAXN], eid;
inline void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
//有向
inline void insert1(int from, int to, int val) {
    e[eid].v = to;
    e[eid].val = val;
    e[eid].next = p[from];
    p[from] = eid++;
    swap(from, to);
    e[eid].v = to;
    e[eid].val = 0;
    e[eid].next = p[from];
    p[from] = eid++;
}
//無向
inline void insert2(int from, int to, int val) {
    e[eid].v = to;
    e[eid].val = val;
    e[eid].next = p[from];
    p[from] = eid++;
    swap(from, to);
    e[eid].v = to;
    e[eid].val = val;
    e[eid].next = p[from];
    p[from] = eid++;
}
int n, m; //n為點數 m為邊數
int h[MAXN];
int gap[MAXN];
int source, sink;
inline int dfs(int pos, int cost) {
    if (pos == sink) {
        return cost;
    }
    int j, minh = n - 1, lv = cost, d;
    for (j = p[pos]; j != -1; j = e[j].next){
        int v = e[j].v, val = e[j].val;
        if(val > 0){
            if (h[v] + 1 == h[pos]) {
                if (lv < e[j].val) d = lv;
                else d = e[j].val;
                d = dfs(v, d);
                e[j].val -= d;
                e[j ^ 1].val += d;
                lv -= d;
                if (h[source] >= n)return cost - lv;
                if (lv == 0)break;
            }
            if (h[v] < minh)minh = h[v];
        }
    }
    if (lv == cost) {
        --gap[h[pos]];
        if (gap[h[pos]] == 0)h[source] = n;
        h[pos] = minh + 1;
        ++gap[h[pos]];
    }
    return cost - lv;
}
int sap(int st, int ed) {

    source = st;
    sink = ed;
    int ret = 0;
    memset(gap, 0, sizeof(gap));
    memset(h, 0, sizeof(h));
    gap[0] = n;
    while (h[st] < n)ret += dfs(st, INF);
    return ret;
}
int main()
{
    int a,i,T,src,end,t;
    char s[10];
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        src=n+1;
        end=++m;
        for(i=1;i<=n;i++){
            scanf("%s%d",s,&t);
            if(s[0]=='I')insert1(src,i,INF);
            while(t--){
                scanf("%d",&a);
                insert1(i,a+1,INF);
                insert1(a+1,i,1);
            }
        }
        n=n+1;
        int res=sap(src,end);
        if(res>= INF)puts("PANIC ROOM BREACH");
        else printf("%d\n", res);
    }
    return 0;
}