首页 技术 正文
技术 2022年11月23日
0 收藏 897 点赞 3,483 浏览 1644 个字

题目链接

非常简单的一道网络流题

我们发现每个单位的人要坐到不同餐桌上,那也就是说每张餐桌上不能有同一单位的人。这样的话,我们对于每个单位向每张餐桌连一条边权为1的边,表示同一餐桌不得有相同单位的人。从源点向每个单位连一条边权为人数的边,从餐桌向汇点连一条边权为餐桌容量的边,这样的话跑最大流,跑出来的结果就是在满足以上条件的情况下最多能坐多少人,如果结果等于总人数,说明可行,否则不可行。

那么怎么输出方案呢?

我们记录每个单位向每张餐桌连的边的序号,如果这条边流满了,则说明这个单位有一个人坐在这张餐桌上。这样输出即可

下放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define gc getchar
#define maxn 505
#define maxm 100005
using namespace std;inline ll read(){
ll a=0;int f=0;char p=gc();
while(!isdigit(p)){f|=p=='-';p=gc();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
return f?-a:a;
}int n,m,S,T,ans;struct ahaha{
int w,to,next;
}e[maxm<<1];int tot,head[maxn];
inline void add(int u,int v,int w){
e[tot]={w,v,head[u]};head[u]=tot++;
}int q[maxn],dep[maxn];
int bfs(){memset(dep,-1,sizeof dep); //非常朴素的dinic
int h=0,t=1;dep[S]=0;
while(++h<=t){
int u=q[h];
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;if(~dep[v]||e[i].w<=0)continue;
dep[v]=dep[u]+1;q[++t]=v;
if(v==T)return 1;
}
}return 0;
}
int dfs(int u,int w){
if(u==T)return w;
int sum=0;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;if(dep[v]!=dep[u]+1||e[i].w<=0)continue;
int d=dfs(v,min(w-sum,e[i].w));
e[i].w-=d,e[i^1].w+=d;
sum+=d;if(sum==w)break;
}
if(sum<w)dep[u]=-1;
return sum;
}int main(){memset(head,-1,sizeof dep);
n=read();m=read();T=n+m+1;
for(int i=1;i<=n;++i) //因为先添加这种边,所以无需记录编号,直接计算得即可
for(int j=1;j<=m;++j){
add(i,j+n,1);
add(j+n,i,0);
}
for(int i=1;i<=n;++i){
int a=read();ans+=a;
add(S,i,a);add(i,S,0);
}
for(int i=1;i<=m;++i){
int a=read();
add(n+i,T,a);add(T,n+i,0);
}
while(bfs())
ans-=dfs(S,2147483647);
if(ans){
puts("0");
return 0;
}
puts("1");
for(int i=1;i<=n;++i,puts("")) //这里就是上面说的输出方案
for(int j=1;j<=m;++j){
int p=((i-1)*m+j-1)*2;
if(e[p].w)continue;
printf("%d ",j);
}
return 0;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141134.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,090
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,509
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,315
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站