传送门

一道良心啊……没那么多麻烦了……

从$S$向所有单位连边,容量为单位人数,从所有桌子向$T$连边,容量为桌子能坐的人数,从每一个单位向所有桌子连边,容量为$1$,然后跑一个最大流,看一看$S$到单位这一边流满了没,如果没有就无解。方案的话,就看单位到哪一个桌子有流就行

因为手写队列然后两个$t$弄混了结果死都不知道哪里错……

 //minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(int x){
if(C><<)Ot();
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);
}
const int N=,M=;
int head[N],Next[M],ver[M],edge[M],cur[N],tot=;
int dep[N],n,m,u,v,e,vis[N],s,t,sum=;
queue<int> q;
inline void add(int u,int v,int e){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;
ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=;
}
bool bfs(){
memset(dep,-,sizeof(dep));
while(!q.empty()) q.pop();
for(int i=;i<=n+m+;++i) cur[i]=head[i];
q.push(s),dep[s]=;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
if(dep[v]<&&edge[i])
dep[v]=dep[u]+,q.push(v);
}
}
return ~dep[t];
}
int dfs(int u,int limit){
if(!limit||u==t) return limit;
int flow=,f;
for(int i=cur[u];i;i=Next[i]){
int v=ver[i];cur[u]=i;
if(dep[v]==dep[u]+&&(f=dfs(v,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^]+=f;
if(!limit) break;
}
}
return flow;
}
int dinic(){
int flow=;
while(bfs()) flow+=dfs(s,inf);
return flow;
}
int main(){
m=read(),n=read();
s=,t=n+m+;
for(int i=;i<=m;++i){
e=read(),add(s,i,e),sum+=e;
for(int j=;j<=n;++j)
add(i,j+m,);
}
for(int i=;i<=n;++i){
e=read();add(i+m,t,e);
}
if(dinic()!=sum) return puts(""),;
print(),sr[++C]='\n';
for(int i=;i<=m;++i){
for(int j=head[i];j;j=Next[j]){
if(!edge[j]&&ver[j]>m&&ver[j]<=n+m)
print(ver[j]-m),sr[++C]=' ';
}
sr[++C]='\n';
}
Ot();
return ;
}

最新文章

  1. Model Validation in ASP.NET Web API
  2. web项目中,视图层中关于相对路径和绝对路径
  3. canvas判断边距,反弹和拖拽的综合实例
  4. AutoIt3(AU3)开发的驱动备份工具
  5. MyEclipse取消验证Js的两种方法
  6. poj 1416 Shredding Company( dfs )
  7. vue指令v-else示例解析
  8. 解决前端开发sublime text 3编辑器无法安装插件的问题
  9. 一名Java架构师分享自己的从业心得,从码农到架构师我用了八年
  10. zabbix目录
  11. golang二进制bit位的常用操作
  12. laravel-重定向携带自定义消息
  13. POJ 3020 -Antenna Placement-二分图匹配
  14. 二层环路保护,RRPP多环的配置
  15. Swift闭包(I) @autoclosure和@escaping的区别
  16. REPL
  17. ORACLE ERP consolidation流程(一)
  18. 第40章 CAN—通讯实验—零死角玩转STM32-F429系列
  19. android4.0 中关于内外置sd卡的获取及读写权限问题
  20. GIT 如何合并另一个远程Git仓库的文件到本地仓库里某个指定子文件夹并不丢失远程提交记录?

热门文章

  1. vue-cli脚手架config目录下index.js配置文件详解
  2. Oracle 10g RAC 如何配置 VIP IPMP
  3. ffmpeg截取一段视频中一段视频
  4. asp.net js 存取cookie
  5. IE回车的一个怪异行为
  6. laravel框架容器管理的一些要点(转)
  7. mfs教程(四)
  8. SQL Server误区30日谈 第26天 SQL Server中存在真正的“事务嵌套”
  9. Spring 实例化bean的三种方式
  10. VMware下Ubuntu虚拟机NAT模式 连接Xshell