最大流——hdu4292(类似poj3281 带间隔的流)
2024-08-26 20:03:58
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define inf 0x3f3f3f3f
struct Edge{int to,nxt,w;}e[maxn<<];
int head[maxn],tot,N,F,D,s,t;
void init(){memset(head,-,sizeof head);tot=;}
void add(int u,int v,int w){
e[tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot++;
e[tot].to=u;e[tot].w=;e[tot].nxt=head[v];head[v]=tot++;
} int d[maxn];
int bfs(){
memset(d,,sizeof d);
queue<int>q;
q.push(s);d[s]=; while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i!=-;i=e[i].nxt){
int y=e[i].to;
if(e[i].w== || d[y])continue;
d[y]=d[x]+;
q.push(y);
if(y==t)return ;
}
}
return ;
}
int dfs(int x,int flow){
if(x==t)return flow;
int rest=flow;
for(int i=head[x];i!=- && rest;i=e[i].nxt){
int y=e[i].to;
if(e[i].w== || d[y]!=d[x]+)continue;
int k=dfs(y,min(rest,e[i].w));
rest-=k;e[i].w-=k;e[i^].w+=k;
}
return flow-rest;
}
int dinic(){
int ans=;
while(bfs())
while(int flow=dfs(s,inf))
ans+=flow;
return ans;
} char buf[maxn];
int main(){
while(scanf("%d%d%d",&N,&F,&D)!=EOF){
init();
s=;t=N*+F+D+;int x;
for(int i=;i<=F;i++){
scanf("%d",&x);
add(s,i+*N,x);
}
for(int i=;i<=D;i++){
scanf("%d",&x);
add(i+*N+F,t,x);
}
for(int i=;i<=N;i++){
scanf("%s",buf+);
for(int j=;j<=F;j++)
if(buf[j]=='Y')
add(j+*N,i,inf);
}
for(int i=;i<=N;i++){
scanf("%s",buf+);
for(int j=;j<=D;j++)
if(buf[j]=='Y')
add(i+N,j+F+*N,inf);
}
for(int i=;i<=N;i++)//拆点
add(i,i+N,); cout<<dinic()<<'\n';
}
}
最新文章
- Java
- [django]django xlrd处理xls中日期转换问题
- G将军的敢死队——树状DP
- 第六百一十二、三、四、五天 how can I 坚持
- Oracle工具之DBNEWID
- 【python】密码生成器
- Office 365 - SharePoint Tips &; Tricks
- jQuery插件:用于获取元素自身的HTML内容
- [错误代码:0x80070002]IIS7及以上伪静态报错404
- 通过Web Deploy方式部署WCF
- Quartz框架的使用
- strstr 的使用
- Python中安装模块的方法
- 第八节: EF的性能篇(一) 之 EF自有方法的性能测试
- Mac Mojave(10.14.1)执行Matlab的mex报错
- 剑指offer(49)把字符串转换成整数。
- C# 创建多级文件夹示例
- Mybatis中dao接口和mapper 的加载过程
- 如何将Skyline66嵌入WPF中
- InstallShield卸载不彻底,残留大量dll文件