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