首页 > 代码库 > zoj2788最小割

zoj2788最小割

  这个建图比较好建,门在i房间里通向j ,i->j= INF ,j->i=1

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int e1;int s;const int INF=0xfffffff;int Min(int a,int b){    return a>b?b:a;}const int maxn=111;int m;int len;int head[maxn];struct edge{    int val;int to;int next;int op;}e[1111111];int level[maxn];void add(int from,int to,int  val){    e[len].to=to;e[len].val=val;    e[len].next=head[from];    e[len].op=len+1;    head[from]=len++;    e[len].to=from;e[len].val=0;    e[len].next=head[to];    e[len].op=len-1;    head[to]=len++;}bool bfs(){    memset(level,0,sizeof(level));    queue<int> q;    q.push(s) ; level[s]=1;    while(!q.empty()){        int cur=q.front(); q.pop();        for(int i=head[cur];i!=-1;i=e[i].next){            if(e[i].val==0) continue;            int cc=e[i].to;            if(!level[cc]){                q.push(cc);                level[cc]=level[cur]+1;            }        }    }    return level[e1];}int dfs(int x,int val){    int sum=0;    if(x==e1) return val;    for(int i=head[x];val&&i!=-1;i=e[i].next){        if(!e[i].val) continue;        int cc=e[i].to;        if(level[cc]==level[x]+1){            int t=dfs(cc,Min(val,e[i].val));            e[i].val-=t;e[e[i].op].val+=t;            sum+=t;val-=t;        }    }    if(sum==0) level[x]=-1;    return sum;}int dinic(){    int ans=0;    int t;    while(bfs()){        while(t=dfs(s,INF)) ans+=t;    }    return ans;}void solve(){    int ans=dinic();    if(ans>=INF) printf("PANIC ROOM BREACH\n");    else printf("%d\n",ans);}int main(){    int Icase;    int n;    int c,t;char str[100];    scanf("%d",&Icase);    while(Icase--){        memset(head,-1,sizeof(head));        scanf("%d%d",&m,&n);        s=m,e1=n;        for(int i=0;i<m;i++){            scanf("%s",str);scanf("%d",&c);            if(strcmp(str,"I")==0){                add(s,i,INF);                for(int j=0;j<c;j++){                    scanf("%d",&t);                    add(i,t,INF);                    add(t,i,1);                }            }            else{                for(int j=0;j<c;j++){                    scanf("%d",&t);                    add(i,t,INF);                    add(t,i,1);                }            }        }        solve();    }    return 0;}

 

。 如果这个房间有坏蛋,设源点m ,  m->i=INF.