首页 > 代码库 > POJ 3084 Panic Room 求最小割

POJ 3084 Panic Room 求最小割

2024-07-14 11:53:31   223人阅读

建模的思路大概是这样的，把房间当做点，门当做是边，如果从房间A能到房间B中间有一个门，如果锁在A这边那么A->B容量就是INF，B->A的容量就是1。

攻击者如果在A这边的话显然就算你锁了门也是没有意义的，在B这边如果锁上是有意义的，所以算1个门，然后就很简单了，建立源点到所有攻击者点的边，容量为INF，汇点就是要保护的那个房间。求最小割即可。

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 30;const int INF = INT_MAX / 3;int cap[maxn][maxn],n,s,t;int level[maxn],q[maxn],qs,qe;char buf[128];bool bfs() {    qs = qe = 0;    q[qe++] = s;    memset(level,0,sizeof(level));    level[s] = 1;    while(qs < qe) {        int now = q[qs++];        for(int i = 0;i <= n;i++) if(cap[now][i] && level[i] == 0) {            level[i] = level[now] + 1; q[qe++] = i;        }    }    return level[t];}int dfs(int now,int alpha) {    if(now == t) return alpha;    int sum = 0;    for(int i = 0;i <= n && alpha;i++) {        if(cap[now][i] && level[i] == level[now] + 1) {            int ret = dfs(i,min(alpha,cap[now][i]));            sum += ret; alpha -= ret;            cap[now][i] -= ret; cap[i][now] += ret;        }    }    if(sum == 0) level[now] = -1;    return sum;}void solve() {    int ans = 0;    while(bfs()) ans += dfs(s,INT_MAX);    if(ans >= INF) puts("PANIC ROOM BREACH");    else printf("%d\n",ans);}int main() {    int T; scanf("%d",&T);    while(T--) {        memset(cap,0,sizeof(cap));        scanf("%d%d",&n,&t);        s = n;        for(int i = 0;i < n;i++) {            int m;            scanf("%s%d",buf,&m);            for(int j = 0;j < m;j++) {                int tmp; scanf("%d",&tmp);                cap[i][tmp] = INF;                cap[tmp][i]++;            }            if(buf[0] == ‘I‘) cap[s][i] = INF;        }        solve();    }    return 0;}

　　


联系
我们