UVa10779 Collectors Problem(最大流)
2024-10-19 05:29:54
很容易想到源点向所类型有贴纸连边,容量为Bob一开始有的数量;然后贴纸向汇点连边,容量为1。
接下来就是交换部分的连边了。注意交换一次一次进行,每次只能交换一张。
交换,是对于两种贴纸而言,仅会发生在一种贴纸朋友拥有的数量为0,而另一种朋友拥有的数量大于1。
于是这么建图,对于每一个朋友,如果贴纸数为0,那么这种贴纸向这个朋友连一条容量为1的边;如果数量x大于1,那边这个朋友向这种贴纸连一条容量为x-1的边。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1<<30)
#define MAXN 55
#define MAXM 55*55*2 struct Edge{
int v,cap,flow,next;
}edge[MAXM];
int vs,vt,NE,NV;
int head[MAXN]; void addEdge(int u,int v,int cap){
edge[NE].v=v; edge[NE].cap=cap; edge[NE].flow=;
edge[NE].next=head[u]; head[u]=NE++;
edge[NE].v=u; edge[NE].cap=; edge[NE].flow=;
edge[NE].next=head[v]; head[v]=NE++;
} int level[MAXN];
int gap[MAXN];
void bfs(){
memset(level,-,sizeof(level));
memset(gap,,sizeof(gap));
level[vt]=;
gap[level[vt]]++;
queue<int> que;
que.push(vt);
while(!que.empty()){
int u=que.front(); que.pop();
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(level[v]!=-) continue;
level[v]=level[u]+;
gap[level[v]]++;
que.push(v);
}
}
} int pre[MAXN];
int cur[MAXN];
int ISAP(){
bfs();
memset(pre,-,sizeof(pre));
memcpy(cur,head,sizeof(head));
int u=pre[vs]=vs,flow=,aug=INF;
gap[]=NV;
while(level[vs]<NV){
bool flag=false;
for(int &i=cur[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(edge[i].cap!=edge[i].flow && level[u]==level[v]+){
flag=true;
pre[v]=u;
u=v;
//aug=(aug==-1?edge[i].cap:min(aug,edge[i].cap));
aug=min(aug,edge[i].cap-edge[i].flow);
if(v==vt){
flow+=aug;
for(u=pre[v]; v!=vs; v=u,u=pre[u]){
edge[cur[u]].flow+=aug;
edge[cur[u]^].flow-=aug;
}
//aug=-1;
aug=INF;
}
break;
}
}
if(flag) continue;
int minlevel=NV;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(edge[i].cap!=edge[i].flow && level[v]<minlevel){
minlevel=level[v];
cur[u]=i;
}
}
if(--gap[level[u]]==) break;
level[u]=minlevel+;
gap[level[u]]++;
u=pre[u];
}
return flow;
} int main(){
int t,n,m,a,b;
scanf("%d",&t);
for(int cse=;cse<=t;++cse){
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
vs=; vt=n+m+; NV=vt+; NE=; scanf("%d",&a);
int cnt[]={};
while(a--){
scanf("%d",&b);
++cnt[b];
}
for(int i=;i<=m;++i){
if(cnt[i]==) continue;
addEdge(vs,i,cnt[i]);
} for(int i=;i<=m;++i) addEdge(i,vt,); for(int i=;i<=n;++i){
scanf("%d",&a);
int cnt[]={};
while(a--){
scanf("%d",&b);
++cnt[b];
}
for(int j=;j<=m;++j){
if(cnt[j]>=){
addEdge(i+m,j,cnt[j]-);
}else if(cnt[j]==){
addEdge(j,i+m,);
}
}
} printf("Case #%d: %d\n",cse,ISAP());
}
return ;
}
最新文章
- SQL Server下载安装
- UGUI 学习笔记
- [转]MySQL 最基本的SQL语法/语句
- SQLSERVER不带JOIN的语句与带JOIN语句的区别
- Backbone中 View之间传值的解决办法
- Could not find the Visual SourceSafe Internet Web Service connection information for the specified database Would you like to launch the Visual sourceSafe connection wizard?
- BZOJ3073 : [Pa2011]Journeys
- js 程序出发事件
- Java-马士兵设计模式学习笔记-观察者模式-OOD 封装Listener
- java中substring的使用方法
- easyui 个人使用心得之下拉列表
- 什么是<;!DOCTYPE html>;
- NancyFX 第七章 模型绑定和验证
- 详解JavaScript对象继承方式
- ssm框架找不到mysql驱动类WARN DriverManagerDataSource:107 - Could not load driverClass com.mysql.jdbc.Driver
- EntityFramework优化:第一次启动优化
- Game Theory
- 解码base64加密的图片并打印到前台
- laravel的firstOrCreate的作用:先查找表,如果有就输出数据,如果没有就插入数据
- wc 命令使用说明
热门文章
- C#内部类
- Unity3d发布成exe项目后的设置(全屏自适应屏幕大小)
- js 中数组或者对象的深拷贝和浅拷贝
- zb的生日
- python中import和from...import...的区别
- spring boot实战(第十三篇)自动配置原理分析
- python - easy_install的安装和使用
- Java for LeetCode 201 Bitwise AND of Numbers Range
- 【python】argparse模块
- 安装qmake与环境变量解析