loj6004「网络流 24 题」圆桌聚餐

loj6004「网络流 24 题」圆桌聚餐

(​​ 题目描述

假设有来自 n n n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri r_i r​i​​。会议餐厅共有 m m m 张餐桌，每张餐桌可容纳 ci c_i c​i​​ 个代表就餐。 为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。

试设计一个算法，给出满足要求的代表就餐方案。 输入格式

文件第 1 1 1 行有 2 2 2 个正整数 m m m 和 n n n，m m m 表示单位数，n n n 表示餐桌数。 文件第 2 2 2 行有 m m m 个正整数，分别表示每个单位的代表数。 文件第 3 3 3 行有 n n n 个正整数，分别表示每个餐桌的容量。 输出格式

如果问题有解，在文件第 1 1 1 行输出 1 1 1，否则输出 0 0 0。 接下来的 m m m 行给出每个单位代表的就餐桌号。如果有多个满足要求的方案，只要输出一个方案。 样例 样例输入

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

数据范围与提示

1≤m≤150,1≤n≤270 1 \leq m \leq 150, 1 \leq n \leq 270 1≤m≤150,1≤n≤270

这题我竟然想了很久怕不是个傻x

从源点向每个团队建团队数的边 然后因为每个团队在每桌只可以有一个人

那么所以从每个团队向每桌连容量为1的边

然后从每个桌向汇点连容量为桌子坐的数量的边 最后跑最大流看是否满流

如果满流输出方案数即可

#include#include#include#include#define inf 0x3f3f3f3f#define N 500using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}int num=1,h[N],level[N],n,m,T;struct node{ int y,z,next;}data[110000];inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;}inline bool bfs(){ memset(level,0,sizeof(level));queueq;q.push(0);level[0]=1; while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[y]||!z) continue;level[y]=level[x]+1;q.push(y);if(y==T) return 1; } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(s,z));if (!xx) level[y]=0;s-=xx; data[i].z-=xx;data[i^1].z+=xx;if(!s) return ss; } }return ss-s;}int main(){ freopen("loj.in","r",stdin); m=read();n=read();T=n+m+1;int sum=0,tmp=0; for (int i=1;i<=m;++i) tmp=read(),sum+=tmp,insert1(0,i,tmp); for (int i=1;i<=n;++i) insert1(i+m,T,read()); for (int i=1;i<=m;++i) for (int j=1;j<=n;++j) insert1(i,j+m,1); int ans=0;while(bfs()) ans+=dfs(0,inf); if (ans!=sum) printf("0");else{ printf("1\n"); for (int i=1;i<=m;++i){ for (int j=h[i];j;j=data[j].next) if (!data[j].z&&data[j].y>=m+1&&data[j].y<=m+n) printf("%d ",data[j].y-m);puts(""); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。