题目链接：http://poj.org/problem?id=3084
本题主要在构图上，我采用的是把要保护的房间与源点相连，有intruder的与汇点相连，相对麻烦。
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector> #define maxn 30
#define maxe 5000
using namespace std; const int INF = 0x3f3f3f; struct Edge{
int from,to,cap,flow;
int next;
}; struct Dinic{
int s,t;
int head[maxn];
int cur[maxn];
Edge edges[maxe];
int d[maxn];
bool vis[maxn];
int cnt; void init(){
memset(head,-,sizeof(head));
cnt = ;
}
void addedge(int from,int to,int cap){
edges[cnt].from = from; edges[cnt].to = to; edges[cnt].cap = cap;
edges[cnt].flow = ; edges[cnt].next = head[from]; head[from] = cnt++;
edges[cnt].from = to ; edges[cnt].to = from; edges[cnt].cap = ;
edges[cnt].flow = ; edges[cnt].next = head[to]; head[to] = cnt++;
}
bool bfs(){
memset(vis,,sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s] = true;
d[s] = ;
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i=head[u];i!=-;i=edges[i].next){
Edge& e = edges[i];
if(!vis[e.to] && e.cap>e.flow){
vis[e.to] = true;
d[e.to] = d[e.from] + ;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int u,int res){
if( u == t || res == ) return res;
int flow = ,f;
for(int& i=cur[u];i!=-;i=edges[i].next){ //还不是很理解到cur[]的作用；
Edge& e = edges[i];
if(d[e.to] == d[e.from] + && (f = dfs(e.to,min(res,e.cap-e.flow)))>){
e.flow += f;
edges[i^].flow -= f;
flow += f;
res -= f;
if(res == ) break;
}
}
return flow;
}
int Maxflow(int S,int T){
s = S; t = T;
int flow = ;
while(bfs()){
for(int i=s;i<=t;i++) cur[i] = head[i];
flow += dfs(s,INF);
}
return flow;
}
}solver; int main()
{
//if(freopen("input.txt","r",stdin)== NULL) {printf("Error\n"); exit(0);}
int T;
cin>>T;
while(T--){
solver.init();
int m,n;
scanf("%d%d",&m,&n);
n++;
int s,t;
s = ; t = m+;
solver.addedge(s,n,INF);
for(int i=;i<=m;i++){
char ch[];
int adjnum;
scanf("%s%d",ch,&adjnum);
if(ch[] == 'I'){
//printf("i %d\n",i);
solver.addedge(i,t,INF);
for(int j=;j<=adjnum;j++){
int a;
scanf("%d",&a);
a++;
solver.addedge(a,t,INF); //能从intruder所在房间到达的房间要与汇点相连 }
}
else{
for(int j=;j<=adjnum;j++){
int a;
scanf("%d",&a);
a++;
if(a == n) solver.addedge(s,i,INF); //能到达保护房间也要与源点相连；
solver.addedge(i,a,);
solver.addedge(a,i,INF); //这是一直WA的地方；
}
}
}
int ans = solver.Maxflow(s,t);
if(ans >= INF) printf("PANIC ROOM BREACH\n");
else printf("%d\n",ans);
}
}
另一种构图，简单多了
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector> #define maxn 30
#define maxe 5000
using namespace std; const int INF = 0x3f3f3f; struct Edge{
int from,to,cap,flow;
int next;
}; struct Dinic{
int s,t;
int head[maxn];
int cur[maxn];
Edge edges[maxe];
int d[maxn];
bool vis[maxn];
int cnt; void init(){
memset(head,-,sizeof(head));
cnt = ;
}
void addedge(int from,int to,int cap){
edges[cnt].from = from; edges[cnt].to = to; edges[cnt].cap = cap;
edges[cnt].flow = ; edges[cnt].next = head[from]; head[from] = cnt++;
edges[cnt].from = to ; edges[cnt].to = from; edges[cnt].cap = ;
edges[cnt].flow = ; edges[cnt].next = head[to]; head[to] = cnt++;
}
bool bfs(){
memset(vis,,sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s] = true;
d[s] = ;
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i=head[u];i!=-;i=edges[i].next){
Edge& e = edges[i];
if(!vis[e.to] && e.cap>e.flow){
vis[e.to] = true;
d[e.to] = d[e.from] + ;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int u,int res){
if( u == t || res == ) return res;
int flow = ,f;
for(int& i=cur[u];i!=-;i=edges[i].next){ //还不是很理解到cur[]的作用；
Edge& e = edges[i];
if(d[e.to] == d[e.from] + && (f = dfs(e.to,min(res,e.cap-e.flow)))>){
e.flow += f;
edges[i^].flow -= f;
flow += f;
res -= f;
if(res == ) break;
}
}
return flow;
}
int Maxflow(int S,int T){
s = S; t = T;
int flow = ;
while(bfs()){
for(int i=s;i<=t;i++) cur[i] = head[i];
flow += dfs(s,INF);
}
return flow;
}
}solver; int main()
{
//if(freopen("input.txt","r",stdin)== NULL) {printf("Error\n"); exit(0);}
int T;
cin>>T;
while(T--){
solver.init();
int m,n;
scanf("%d%d",&m,&n);
n++;
int s,t;
s = ; t = m+;
solver.addedge(n,t,INF);
for(int i=;i<=m;i++){
char ch[];
int adjnum;
scanf("%s%d",ch,&adjnum);
if(ch[] == 'I'){
solver.addedge(s,i,INF);
} for(int j=;j<=adjnum;j++){
int a;
scanf("%d",&a);
a++;
solver.addedge(i,a,INF);
solver.addedge(a,i,);
}
}
int ans = solver.Maxflow(s,t);
if(ans >= INF) printf("PANIC ROOM BREACH\n");
else printf("%d\n",ans);
}
}