首页 > 代码库 > 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.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。