洛谷 [P3254] 圆桌问题

简单最大流建图

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN=600,MAXM=2000005;
int head[MAXN],cur[MAXN],n,m,s,t,nume,num1[MAXN],num2[MAXN],maxflow,dep[MAXN];
queue<int> q;
struct edge{
int to,nxt,flow,cap;
}e[MAXM];
void adde(int from,int to,int cap){
e[++nume].to=to;
e[nume].nxt=head[from];
head[from]=nume;
e[nume].cap=cap;
}
bool bfs(){
memset(dep,0,sizeof(dep));
q.push(s);dep[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dep[v]&&e[i].flow<e[i].cap){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t];
}
int dfs(int u,int flow){
if(u==t) return flow;
int tot=0;
for(int &i=cur[u];i&&tot<flow;i=e[i].nxt){
int v=e[i].to;
if(dep[v]==dep[u]+1&&e[i].flow<e[i].cap){
if(int t=dfs(v,min(flow-tot,e[i].cap-e[i].flow))){
e[i].flow+=t;
e[((i-1)^1)+1].flow-=t;
tot+=t;
}
}
}
return tot;
}
void dinic(){
while(bfs()){
for(int i=s;i<=t;i++) cur[i]=head[i];
maxflow+=dfs(s,0x3f3f3f3f);
}
}
int main(){
cin>>m>>n;
int tot=0;
for(int i=1;i<=m;i++){
cin>>num1[i];
if(num1[i]>n){
cout<<0<<endl;
return 0;
}
tot+=num1[i];
}
for(int i=1;i<=n;i++) cin>>num2[i];
s=0;t=m+n+1;
for(int i=1;i<=m;i++) adde(s,i,num1[i]),adde(i,s,0);
for(int i=1;i<=n;i++) adde(i+m,t,num2[i]),adde(t,i+m,0);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++) adde(i,j+m,1),adde(j+m,i,0);
}
dinic();
if(maxflow!=tot) cout<<0<<endl;
else{
cout<<1<<endl;
for(int i=1;i<=m;i++){
for(int j=head[i];j;j=e[j].nxt){
if(e[j].flow&&e[j].to) printf("%d ",e[j].to-m);
}
printf("\n");
}
}
return 0;
}
上一篇:HTML 09 web 内容与攻击技术


下一篇:vue项目使用html5+ barcode扫码在苹果遇到的问题以及自己的解决方法