poj 3084 最小割

题目链接：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);

    }

}