Posted on 2010-10-01 20:53
成幸毅 阅读(484)
评论(0) 编辑 收藏 引用
这道题目读起来难度挺大,主要还是建模,模型还是不难。下面复制下别人的解题报告,代码是自己的。
【题目大意】
针对输入数据来说题目意思吧。
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;
}