beloved_ACM

SB,NB,都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

POJ 3084_最小割

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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理