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