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

圆桌排序公式_大圆桌怎么坐假设有来自 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)


相关推荐

  • RabbitMQ使用教程(超详细)

    推荐springCloud教程:https://blog.csdn.net/hellozpc/article/details/83692496推荐Springboot2.0教程:https://blog.csdn.net/hellozpc/article/details/82531834文章目录RabbitMQ实战教程1.什么是MQ2.RabbitMQ2.1.RabbitMQ的简介2.2.官…

  • plsql 中文乱码 字符集解决方案「建议收藏」

    plsql 中文乱码 字符集解决方案「建议收藏」1.环境变量,NLS_LANG:SIMPLIFIEDCHINESE_CHINA.ZHS16GBK2.如果想转换为UTF8字符集,可以赋予“NLS_LANG”为“AMERICAN_AMERICA.UTF8”3.oracle查看数据库字符集select*fromnls_database_parameters,其来源于props$,是表示数据库的字符集。客户端字符集环境

  • springmvc过滤器和拦截器的区别_拦截器和过滤器的区别面试

    springmvc过滤器和拦截器的区别_拦截器和过滤器的区别面试SpringMVC中的过滤器和拦截器文章目录SpringMVC中的过滤器和拦截器一、过滤器二、拦截器三、小结一、过滤器​ 过滤器Filter是通过实现java.servlet.filter接口实现过滤器功能,作用是用于对传入的request和响应的response进行一些处理,比如对请求参数进行校验,或者设置、检验头部信息,再或者对一些非法行为进行校验。由实现的接口可知,过滤器是依赖于servlet容器。所以由于过滤器不依赖于spring容器,它也就无法获取到容器中的对象。创建一个过滤器类继承j

  • navigator.appName

    navigator.appName找了很多的参考,无外乎两句话,兼容性和缅怀网景我就很好奇,到底在兼容什么然后翻到一篇外文的提问,里面提及了DOM0然后去了解了一下DOM0…看了介绍之后,就是不太推荐使用的标签监听属性on事件名,不过这文章有提到DOM0具有极好的跨浏览器优势,所以可能appName就是在这方面的支持吧,如果有知道的大佬请留个言,解释一下吧,老纠结了….

  • 磁盘分区类型和分区表的区别[通俗易懂]

    磁盘分区类型和分区表的区别[通俗易懂]任务1罗列磁盘分区的类型并做比较性介绍分类:FAT16、FAT32、NTFS、EXT2、EXT3、EXT4FAT16:磁盘分区最大只能到2GB、使用簇的大小不恰当、FAT16使用了16位的空间来表示每个扇区文件名长度有限制FAT32:相比FAT16会拥有更多的簇,更大空间容量上限为16TB根目录区(ROOT区)不再是固定区域、固定大小速度和FAT16一样快,对大磁盘利用率比FAT16好文件名长度有限制NTFS:备3个功能:错误预警功能、磁盘自我修复功能和日志功能安全性,

  • 数据库二级映射是什么_内存映射技术

    数据库二级映射是什么_内存映射技术1.     概述LMDBiscompact(紧凑的),fast,powerful,androbustandimplementsasimplifiedvariantoftheBerkeleyDB(BDB)API.(BDBisalsoverypowerful,andverboselydocumentedinitsownright.)Afterre…

发表回复

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

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