圆桌排序公式_大圆桌怎么坐

圆桌排序公式_大圆桌怎么坐假设有来自 m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri(i=1,2,…,m)。会议餐厅共有 n 张餐桌,每张餐桌可容纳 ci(i=1,2,…,n) 个代表就餐。为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法,给出满足要求的代表就餐方案。输入格式第 1 行有 2 个正整数 m 和 n,m 表示单位数,n 表示餐桌数。第 2 行有 m 个正整数,分别表示每个单位的代表数 ri。第 3 行有 n 个正整数,分别表示每个餐桌的容量 ci。输

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

假设有来自 m 个不同单位的代表参加一次国际会议。

每个单位的代表数分别为 ri(i=1,2,…,m)。

会议餐厅共有 n 张餐桌,每张餐桌可容纳 ci(i=1,2,…,n) 个代表就餐。

为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。

试设计一个算法,给出满足要求的代表就餐方案。

输入格式
第 1 行有 2 个正整数 m 和 n,m 表示单位数,n 表示餐桌数。

第 2 行有 m 个正整数,分别表示每个单位的代表数 ri。

第 3 行有 n 个正整数,分别表示每个餐桌的容量 ci。

输出格式
如果问题有解,在第 1 行输出 1,否则输出 0。

接下来的 m 行给出每个单位代表的就餐桌号。

如果有多个满足要求的方案,只要求输出 1 个方案。

数据范围
1≤m≤150,
1≤n≤270,
1≤ri,ci≤100

输入样例:
4 5
4 5 3 5
3 5 2 6 4
输出样例:
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
#include<bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10;
const int M = 3e2 + 10;
const int INF = 0x3f3f3f3f;
int n,m,s,e;
int r[N + M],c[N + M];
int head[N + M],cnt;
struct Edge{ 

int v,next,w;
}edge[2 * (M * N + 400)];
void add(int u,int v,int w){ 

edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
int q[N + M],tt = 0,hh = 0;
int d[N + M],cur[N + M];
bool bfs(){ 

tt = 0,hh = 0;
memset(d,-1,sizeof d);
d[s] = 0,cur[s] = head[s],q[tt ++] = s;
while(hh < tt){ 

int t = q[hh ++];
for(int i = head[t];~i;i = edge[i].next){ 

int v = edge[i].v,w = edge[i].w;
if(d[v] == -1 && w > 0){ 

d[v] = d[t] + 1;
cur[v] = head[v];
if(v == e)return true;
q[tt ++] = v;
}
}
}
return false;
}
int dfs(int u,int limit){ 

if(u == e)return limit;
int flow = 0;
for(int i = cur[u];~i && flow < limit;i = edge[i].next){ 

int v = edge[i].v,w = edge[i].w;
cur[u] = i;
if(d[v] == d[u] + 1 && w > 0){ 

int t = dfs(v,min(w,limit - flow));
if(!t)d[v] = -1;
flow += t;
edge[i].w -= t,edge[i ^ 1].w += t;
}
}
return flow;
}
int dinic(){ 

int maxflow = 0,flow;
while(bfs())while(flow = dfs(s,INF))maxflow += flow;
return maxflow;
}
int main(){ 

ios::sync_with_stdio(false);
cin>>m>>n;
int tot = 0;
memset(head,-1,sizeof head);
for(int i = 1;i <= m;i ++)cin>>r[i],tot += r[i];
for(int i = 1;i <= n;i ++)cin>>c[i];
for(int i = 1;i <= m;i ++){ 

add(0,i,r[i]);
add(i,0,0);
}
for(int i = m + 1;i <= m + n;i ++){ 

add(i,n + m + 1,c[i - m]);
add(n + m + 1,i,0);
}
for(int i = 1;i <= m;i ++){ 

for(int j = m + 1;j <= m + n;j ++){ 

add(i,j,1);
add(j,i,0);
}
}
s = 0,e = n + m + 1;
if(tot != dinic())cout<<0<<endl;
else{ 

cout<<1<<endl;
vector<int>res;
for(int i = 1;i <= m;i ++){ 

res.clear();
for(int j = head[i];~j;j = edge[j].next){ 

if(!edge[j].w && edge[j].v >= m + 1 && edge[j].v <= n + m){ 

res.push_back(edge[j].v);
}
}
printf("%d",res[0] - m);
for(int i = 1;i < res.size();i ++)printf(" %d",res[i] - m);
printf("\n");
}
}
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169092.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Spring如何解决循环依赖问题

    Spring如何解决循环依赖问题

  • svn客户端的安装与使用教程(svn汉化教程)

    SVN服务端与客户端安装使用(客户端汉化包)客户端下载地址:https://tortoisesvn.net/downloads.zh.html下载64位SVN安装包和64位简体中文安装包安装SVN打开安装包,直接NextNext选择安装目录,如果是自定义目录要新建一个文件夹,否则会把安装文件散落在盘符(此处不安装命令行工具会导致在idea中无法使用subversio…

  • readprocessmemory函数库_read_csv函数

    readprocessmemory函数库_read_csv函数ReadProcessMemory函数ReadProcessMemory函数功能描述:该函数用来读取指定进程的空间的数据,此空间必须是可以访问的,否则读取操作会失败!函数原型BOOLReadProcessMemory(HANDLEhProcess,//目标进程句柄LPCVOIDlpBaseAddress,//读取数据的起始地址LPVOIDlpBuffer,//存放数据的缓存区地址DW…

  • idea2022.01激活码最新-激活码分享2022.01.18

    (idea2022.01激活码最新)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • 【哈佛幸福课笔记】【1】

    【哈佛幸福课笔记】【1】【哈佛幸福课笔记】【1】​​ 一个月的时间看完了哈佛幸福课,正如Tal所说课程的结束才是学习的开始。对于课程观点的思考,对于个人习惯的培养,对于思维模式的转变还需要花大量的时间去练习。这个系列的帖子将作为我个人的读书笔记,也欢迎机缘巧合点开这个帖子的网友一起讨论。(第一章思维导图)​ 课程在讲述的时候有时候并不是线性完整的逻辑,一个观点有时尚没讲完会进入到新的观点中,这样课程显得不是那么的死板不是单纯的说教而是有趣的互动和对实验数据的分析。课程整体的结构十分清晰,可以说干货很多。1.关于内部

  • 网页音乐播放器接口

    网页音乐播放器接口1、Dewplayer音乐播放器2、我的博客首页虾米播放器代码:<embedsrc=”http://www.xiami.com/widget/0_1769834090/singlePlayer.swf”type=”application/x-shockwave-flash”width=”257″height=”33″wmode=”tra…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号