beloved_ACM

【题目大意】

针对输入数据来说题目意思吧。
7 2 （N个房间，要保护2号房间）
NI 0 {0号房间，NI代表没有入侵者}
I 3 0 4 5 {1号房间，I代表该房间内有入侵者，该房间有3个门，分别连向0，4，5号房间，且控制端在1号房间}
NI 2 1 6
NI 2 1 2
NI 0
NI 0
NI 0
门一开始都是可以打开的，若要关闭或再次打开某扇门必须在控制端进行。
问使得所有入侵者不进入要保护的房间最少需要关闭几扇门，如果入侵者必然会进入要保护的房间则输出PANIC ROOM BREACH

【解题思路】

把要保护的房间作为汇点，设为T，新增源点S。
对于有入侵者的房间I，连一条从S向I容量为inf的弧。
对于每扇门连接的（I,J），若控制端在I，则从I向J连一条容量为Max的弧，从J向I连一条容量为1的弧。
这样，想使得S和T不连通，图中的最小割就对应了一种最小的关门方案，如果割中存在容量为inf的弧，显然是无解的。

#include <iostream>
using namespace std;

const int INF = 1000000000;
const int N = 500;
char str[3];
int s,t;
int g;
int n,m;
int NN;
int sps;
int e[N];
int head[N];
struct node {
   int u,v,next,w;
}edge[N];

void addedge(int u,int v,int val1,int val2) {
   
   edge[sps].v = v;
   edge[sps].w = val1;
   edge[sps].next = head[u];
   head[u] = sps++;
   
   edge[sps].v = u;
   edge[sps].w = val2;
   edge[sps].next = head[v];
   head[v] = sps++;
}

int sap()
{   
    memset(e,0,sizeof(e));
    int pre[N],cur[N],dis[N],gap[N];
    int flow=0,aug=INF,u;
    bool flag;
    for(int i=0;i<=NN;i++)
    {
        gap[i]=dis[i]=0;
    }
    gap[s]=NN;
    u=pre[s]=s;
    while(dis[s]<NN)
    {
        flag=0;
        for(int j= head[u];j!=-1;j=edge[j].next)  
        {
            int v=edge[j].v;
            if(edge[j].w>0&&dis[u]==dis[v]+1)
            {
                flag=1;
                if(edge[j].w<aug) aug=edge[j].w;
                e[u] = j;
                pre[v]=u;
                u=v;
                if(u==t)
                {
                    flow+=aug;
                    while(u!=s)
                    {
                        u=pre[u];
                        edge[e[u]].w-=aug;
                        edge[e[u]^1].w+=aug;
                    }
                    aug=INF;
                }
                break;
            }
        }
        if(flag)
            continue;
        int mindis=NN;
        for(int j=head[u];j!=-1;j=edge[j].next)
        {
            int v=edge[j].v;
            if(edge[j].w>0&&dis[v]<mindis)
            {
             mindis=dis[v];
             e[u]=j;
            }
        }
        if((--gap[dis[u]])==0)
            break;
       gap[dis[u]=mindis+1]++;
       u=pre[u];
    }
    return flow;
}

int main() {
   int cas;
   while(scanf("%d",&cas) != EOF) {
      while(cas--) {
         s = sps = 0;
         memset(head,-1,sizeof(head));
         scanf("%d%d",&n,&t); 
            t++;
            NN = n+1;
            for(int i = 1; i <= n; i++) {
               scanf("%s %d",str,&m);
               if(str[0] == 'I')
                     addedge(s,i,INF,0);  
               for(int j = 0; j < m; j++) {
                  scanf("%d",&g);
                  g++;
                  addedge(i,g,INF,1);
               }
            }
         int ans = sap();
         if(ans < INF) 
            printf("%d\n",ans);
         else
            printf("PANIC ROOM BREACH\n");
      }
   }
   
  // system("pause");
   return 0;
}