题目链接:http://poj.org/problem?id=3281

看了kuangbin大佬的思路,还用着kuangbin板子orz   http://www.cnblogs.com/kuangbin/archive/2012/08/21/2649850.html

#include<cstdio>
#include<cstring>
using namespace std; const int MAXN = ;
const int MAXM = ;
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next,cap,flow;
} edge[MAXM];
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
void init()
{
tol = ;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int w,int rw=)
{
edge[tol].to = v;
edge[tol].cap = w;
edge[tol].next = head[u];
edge[tol].flow = ;
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = rw;
edge[tol].next = head[v];
edge[tol].flow = ;
head[v]=tol++;
}
int sap(int start,int end,int N)
{
memset(gap,,sizeof(gap));
memset(dep,,sizeof(dep));
memcpy(cur,head,sizeof(head));
int u = start;
pre[u] = -;
gap[] = N;
int ans = ;
while(dep[start] < N)
{
if(u == end)
{
int Min = INF;
for(int i = pre[u]; i != -; i = pre[edge[i^].to])
if(Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
for(int i = pre[u]; i != -; i = pre[edge[i^].to])
{
edge[i].flow += Min;
edge[i^].flow -= Min;
}
u = start;
ans += Min;
continue;
}
bool flag = false;
int v;
for(int i = cur[u]; i != -; i = edge[i].next)
{
v = edge[i].to;
if(edge[i].cap - edge[i].flow && dep[v]+ == dep[u])
{
flag = true;
cur[u] = pre[v] = i;
break;
}
}
if(flag)
{
u = v;
continue;
}
int Min = N;
for(int i = head[u]; i != -; i = edge[i].next)
if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
{
Min = dep[edge[i].to];
cur[u] = i;
}
gap[dep[u]]--;
if(!gap[dep[u]])return ans;
dep[u] = Min+;
gap[dep[u]]++;
if(u != start) u = edge[pre[u]^].to;
}
return ans;
} int main()
{
int n,F,D;
scanf("%d%d%d",&n,&F,&D);
init();
for (int i=;i<n;i++) addedge(i,i+n,);
for (int i=;i<n;i++)
{
int f,d;
scanf("%d%d",&f,&d);
for (int j=;j<f;j++)
{
int x;
scanf("%d",&x);
x--;
addedge(n+n+x,i,);
}
for (int j=;j<d;j++)
{
int x;
scanf("%d",&x);
x--;
addedge(n+i,n+n+F+x,);
}
}
for (int i=;i<F;i++) addedge(n+n+F+D,n+n+i,);
for (int i=;i<D;i++) addedge(n+n+F+i,n+n+F+D+,);
printf("%d",sap(n+n+F+D,n+n+F+D+,n+n+F+D+));
return ;
}

最新文章

  1. Oracle Partition Outer Join 稠化报表
  2. 常用linux 命令 -网络相关
  3. 使用Spring Sleuth和Zipkin跟踪微服务
  4. svn更新报错:svn unable to connect to a repository at url
  5. Java Hour 10
  6. Solve error: Cannot open include file: &#39;X11/Xlocale.h&#39;: No such file or directory
  7. poj 1523 求割点
  8. 深入浅出 Java Concurrency (4): 原子操作 part 3 指令重排序与happens-before法则
  9. 转:DDR3详解(以Micron MT41J128M8 1Gb DDR3 SDRAM为例)之一
  10. C# 网络编程之最简单浏览器实现
  11. zf-启动项目报错Server 127.0.0.1 has no instance named dlx 解决办法
  12. window.location.href跳转至空白页
  13. Python基础之迭代器、生成器
  14. 新版Ubuntu安装日文输入法
  15. CF835F Roads in the Kingdom/UOJ126 NOI2013 快餐店 树的直径
  16. Math.Round四舍六入五取偶Math.Ceiling只要有小数都加1Math.Floor总是舍去小数
  17. js gettext
  18. Java不同压缩算法的性能比较 程序猿 2015-01-21 本文将会对常用的几个压缩算法的
  19. streamsets rest api 转换 graphql
  20. Loj10153 二叉苹果树

热门文章

  1. 04 mysql 基础三 (进阶)
  2. django中的ContentType使用
  3. python递归函数(计算阶乘)
  4. 004---Python基本数据类型--元祖
  5. JAVA大作业汇总3
  6. C# 控制台应用程序输出颜色字体
  7. 新版IdFTP解决中文乱码问题
  8. java设计模式大全 Design pattern samples in Java(最经典最全的资料)
  9. 【数据库】 SQLite 介绍
  10. 还原T4模板执行前的警告对话框