题意很蛋疼,看了好久才明白过来什么意思
大意就是,有一些房间,初始时某些房间之间有一些门,并且这些门是打开的,也就是可以来回走动的,但是这些门是确切属于某个房间的,也就是说如果要锁门,则只有在那个房间里才能锁,这跟现实很符合啊,不然随便个人站你家外边把你门给锁了是什么情况。 现在一些房间里有一些恐怖分子,要搞破坏,但是我们现在有个房间很重要,不能被他们破坏,这就需要锁一部分的门,不让恐怖分子有可趁之机,那么最少需要锁多个门呢?
很容易联系到最小割上面,刚开始我没读清楚,觉得既然门是可以来回走的,那么建个双向边好了,结果发现不是这样啊。
假设a->b代表a房间有个门到b,那么显然锁门的控制权在a上,锁1个门就可以不让b里面的人到a去,于是我们就建边b-a,容量为1,然后再建立边a->b,容量为无穷大,
为啥为无穷大呢,因为你无论怎么锁门,你在a里边可以随便开门,随便进入b,所以a->b这条边是锁不掉的
然后建立源点,与所有的存在恐怖分子的房间连边,容量为无穷大,因为题目也说了,可能有很多的锁很多的恐怖分子。
最后以被保护的那个房间为汇点,求最大流即可
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 111
#define MAXM 11111
#define INF 10000007
using namespace std;
struct node
{
int ver; // vertex
int cap; // capacity
int flow; // current flow in this arc
int next, rev;
}edge[MAXM];
int dist[MAXN], numbs[MAXN], src, des, n;
int head[MAXN], e;
void add(int x, int y, int c)
{ //e记录边的总数
edge[e].ver = y;
edge[e].cap = c;
edge[e].flow = 0;
edge[e].rev = e + 1; //反向边在edge中的下标位置
edge[e].next = head[x]; //记录以x为起点的上一条边在edge中的下标位置
head[x] = e++; //以x为起点的边的位置
//反向边
edge[e].ver = x;
edge[e].cap = 0; //反向边的初始容量为0
edge[e].flow = 0;
edge[e].rev = e - 1;
edge[e].next = head[y];
head[y] = e++;
}
void rev_BFS()
{
int Q[MAXN], qhead = 0, qtail = 0;
for(int i = 1; i <= n; ++i)
{
dist[i] = MAXN;
numbs[i] = 0;
}
Q[qtail++] = des;
dist[des] = 0;
numbs[0] = 1;
while(qhead != qtail)
{
int v = Q[qhead++];
for(int i = head[v]; i != -1; i = edge[i].next)
{
if(edge[edge[i].rev].cap == 0 || dist[edge[i].ver] < MAXN)continue;
dist[edge[i].ver] = dist[v] + 1;
++numbs[dist[edge[i].ver]];
Q[qtail++] = edge[i].ver;
}
}
}
void init()
{
e = 0;
memset(head, -1, sizeof(head));
}
int maxflow()
{
int u;
int totalflow = 0;
int Curhead[MAXN], revpath[MAXN];
for(int i = 1; i <= n; ++i)Curhead[i] = head[i];
u = src;
while(dist[src] < n)
{
if(u == des) // find an augmenting path
{
int augflow = INF;
for(int i = src; i != des; i = edge[Curhead[i]].ver)
augflow = min(augflow, edge[Curhead[i]].cap);
for(int i = src; i != des; i = edge[Curhead[i]].ver)
{
edge[Curhead[i]].cap -= augflow;
edge[edge[Curhead[i]].rev].cap += augflow;
edge[Curhead[i]].flow += augflow;
edge[edge[Curhead[i]].rev].flow -= augflow;
}
totalflow += augflow;
u = src;
}
int i;
for(i = Curhead[u]; i != -1; i = edge[i].next)
if(edge[i].cap > 0 && dist[u] == dist[edge[i].ver] + 1)break;
if(i != -1) // find an admissible arc, then Advance
{
Curhead[u] = i;
revpath[edge[i].ver] = edge[i].rev;
u = edge[i].ver;
}
else // no admissible arc, then relabel this vertex
{
if(0 == (--numbs[dist[u]]))break; // GAP cut, Important!
Curhead[u] = head[u];
int mindist = n;
for(int j = head[u]; j != -1; j = edge[j].next)
if(edge[j].cap > 0)mindist = min(mindist, dist[edge[j].ver]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != src)
u = edge[revpath[u]].ver; // Backtrack
}
}
return totalflow;
}
int nt, m;
int main()
{
int T, t, x;
scanf("%d", &T);
char s[5];
while(T--)
{
scanf("%d%d", &nt, &des);
des++;
src = nt + 1;
n = nt + 1;
init();
for(int i = 1; i <= nt; i++)
{
scanf("%s%d", s, &t);
while(t--)
{
scanf("%d", &x);
add(i, x + 1, INF);
add(x + 1, i, 1);
}
if(s[0] == 'I') add(src, i, INF);
}
rev_BFS();
int ans = maxflow();
if(ans >= INF) puts("PANIC ROOM BREACH");
else printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
poj2516代码最小费用最大流
关于在最小割推荐题目中的源码(包括poj,Hdu两大题库的题目)
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1705139
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码