BOJ 15 Panic Room

/*邊聯通度的題；給定n個門，每個門連接配接兩個房間，門面向其中的一個房間x，
從這個房間x任意情況都可以到另外一個房間y,y隻能在門開着的時候可以進入x,
其中有些房間有入侵者，現在求解至少關幾個門，可以保護某個房間的安全
對于x,y之間面向x的門，連x到y的邊，流量無窮，y到x的邊，流量1
增加一個源點，标号為m,連接配接源點到有入侵者的點，流量無窮，要保護的點
作為彙點.如果最大流為無窮，則不存在保護方案，反之，最大流即是最少要關的門的數量*/
//SAP版本
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
const int N=11000,M=100100,INF=1e8,L=999999;
using namespace std;
struct Edge{int dest,len,next;}edge[M];
int p[M],pi;
void Insert(int a,int b,int len){
    edge[pi].dest=b;edge[pi].len=len;edge[pi].next=p[a];p[a]=pi++;
    edge[pi].dest=a;edge[pi].len=0;  edge[pi].next=p[b];p[b]=pi++;
}
int dis[N],pre[N],cur[N],gap[N];
int sap(int s,int t,int n){
    int i,ans=0,now=pre[s]=s,dest,mmin=INF;
    for(i=0;i<n;i++){
        cur[i]=p[i];
        dis[i]=gap[i]=0;
    }
    gap[s]=n;
    bool flag;
    while(dis[s]<n){
        flag=false;
        for(i=cur[now];i!=-1;i=edge[i].next){
            cur[now]=i;
            dest=edge[i].dest;
            if(dis[now]==dis[dest]+1&&edge[i].len>0){
                flag=true;
                mmin=min(mmin,edge[i].len);
                pre[dest]=now;
                now=dest;
                if(now==t){
                    ans+=mmin;
                    while(now!=s){
                        now=pre[now];
                        edge[cur[now]].len-=mmin;
                        edge[cur[now]^1].len+=mmin;
                    }
                    mmin=INF;
                }
                break;
            }
        }
        if(flag)continue;
        int mindis=n;
        for(i=p[now];i!=-1;i=edge[i].next){
            dest=edge[i].dest;
            if(edge[i].len>0&&dis[now]<mindis){
                mindis=dis[now];
                cur[now]=i;
            }
        }
        if((--gap[dis[now]])==0)break;
        gap[dis[now]=mindis+1]++;//真是奇葩代碼
        now=pre[now];
    }
    return ans;
}
int n,m;
void init(){
    int i,j,num,b;
    char op[3];
    memset(p,-1,sizeof(p));
    pi=0;
    scanf("%d%d",&m,&n);
    for(i=0;i<m;i++){
        scanf("%s",&op);
        if(op[0]=='I')Insert(m,i,L);
        scanf("%d",&num);
        for(j=0;j<num;j++){
            scanf("%d",&b);
            Insert(i,b,L);
            Insert(b,i,1);
        }
    }
}
int main(){
    int T;
    for(scanf("%d",&T);T--;){
        init();
        int ans=sap(m,n,m+1);
        if(ans>=L)printf("PANIC ROOM BREACH\n");
        else printf("%d\n",ans);
    }
    return 0;
}


//标程
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#define M 25
#define INF 5000
using namespace std;
int map[M][M],m,n,t,pre[M];
bool vis[M];
int Maxflow(){
    int ans=0;
    while(true){
        memset(vis,false,sizeof(vis));
        memset(pre,0,sizeof(pre));
        queue<int>q;
        q.push(m);//源點壓入隊列
        vis[m]=true;
        while(!q.empty()){
            int cur=q.front();
            q.pop();
            if(cur==n)break;
            for(int i=0;i<m;i++){
                if(!vis[i]&&map[cur][i]){
                    vis[i]=true;
                    q.push(i);
                    pre[i]=cur;
                }
            }
        }
        if(!vis[n])break;
        int Min=INF,u;
        for(u=n;u!=m;u=pre[u]){
            if(Min>map[pre[u]][u])Min=map[pre[u]][u];
        }
        for(u=n;u!=m;u=pre[u]){
            map[pre[u]][u]-=Min;
            map[u][pre[u]]+=Min;
        }
        ans+=Min;
    }
    return ans;

}
int main(){
    int i,u,v,room,mnt;
    string ch;
    for(scanf("%d",&t);t--;){
        memset(map,0,sizeof(map));
        scanf("%d%d",&m,&n);
        for(i=0;i<m;i++){
            cin>>ch>>mnt;
            if(ch=="I")map[m][i]=INF;
            while(mnt--){
                scanf("%d",&v);
                map[i][v]=INF;
                map[v][i]++;
            }
        }
        int ans=Maxflow();
        if(ans>=INF)printf("PANIC ROOM BREACH\n");
        else printf("%d\n",ans);
    }
    return 0;
}
           

Panic Room

Time Limit:1000MS    Memory Limit:65536KB

Description

You are the lead programmer for the Securitron 9042, the latest and greatest in home security software from Jellern Inc. (Motto: We secure your stuff so YOU can't even get to it). The software is designed to "secure" a room; it does this by determining the minimum number of locks it has to perform to prevent access to a given room from one or more other rooms. Each door connects two rooms and has a single control panel that will unlock it. This control panel is accessible from only one side of the door. So, for example, if the layout of a house looked like this:

，

with rooms numbered 0-6 and control panels marked with the letters "CP" (each next to the door it can unlock and in the room that it is accessible from), then one could say that the minimum number of locks to perform to secure room 2 from room 1 is two; one has to lock the door between room 2 and room 1 and the door between room 3 and room 1. Note that it is impossible to secure room 2 from room 3, since one would always be able to use the control panel in room 3 that unlocks the door between room 3 and room 2.

Input

Input to this problem will begin with a line containing a single integer x indicating the number of datasets. Each data set consists of two components:

1. Start line – a single line "m n" (1 <=m<= 20; 0 <=n<= 19) where m indicates the number of rooms in the house and n indicates the room to secure (the panic room).
2. Room list – a series of m lines. Each line lists, for a single room, whether there is an intruder in that room ("I" for intruder, "NI" for no intruder), a count of doors c (0 <= c <= 20) that lead to other rooms and have a control panel in this room, and a list of rooms that those doors lead to. For example, if room 3 had no intruder, and doors to rooms 1 and 2, and each of those doors' control panels were accessible from room 3 (as is the case in the above layout), the line for room 3 would read "NI 2 1 2". The first line in the list represents room 0. The second line represents room 1, and so on until the last line, which represents room m - 1. On each line, the rooms are always listed in ascending order. It is possible for rooms to be connected by multiple doors and for there to be more than one intruder!

Output

For each dataset, output the fewest number of locks to perform to secure the panic room from all the intruders. If it is impossible to secure the panic room from all the intruders, output "PANIC ROOM BREACH". Assume that all doors start out unlocked and there will not be an intruder in the panic room.

Sampleinput

3
7 2
NI 0
I 3 0 4 5
NI 2 1 6
NI 2 1 2
NI 0
NI 0
NI 0
7 2
I 0
NI 3 0 4 5
NI 2 1 6
I 2 1 2
NI 0
NI 0
NI 0
4 3
I 0
NI 1 2
NI 1 0
NI 4 1 1 2 2      

Sampleoutput

2

PANIC ROOM BREACH

1