bzoj1339[Baltic2008]Mafia*
2024-10-09 09:07:47
题意:
匪徒准备从一个车站转移毒品到另一个车站,警方准备进行布控。对于每个车站进行布控都需要一定的代价,现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后,匪徒无法从原定的初始点到达目标点。n≤200。
题解:
每个点拆成两个点,边权为点权,原图中的边边权为正无穷,然后跑最小割。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 60010
#define INF 0x3fffffff
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
struct e{int t,c,n;}es[maxn*]; int g[maxn],ess;
void pe(int f,int t,int c){
es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,,g[t]}; g[t]=ess;
}
int h[maxn]; queue<int>q;
bool bfs(int s,int t){
memset(h,-,sizeof(h)); while(!q.empty())q.pop(); h[s]=; q.push(s);
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i;i=es[i].n)if(es[i].c&&h[es[i].t]==-)h[es[i].t]=h[x]+,q.push(es[i].t);
}
return h[t]!=-;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=,w;
for(int i=g[x];i;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+){
w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^].c+=w; if(!f)return u;
}
if(!u)h[x]=-; return u;
}
int dinic(int s,int t){int f=; while(bfs(s,t))f+=dfs(s,t,INF); return f;}
int n,m,s,t;
int main(){
n=read(); m=read(); s=read(); t=n+read(); ess=; inc(i,,n){int x=read(); pe(i,n+i,x);}
inc(i,,m){int x=read(),y=read(); pe(n+x,y,INF); pe(n+y,x,INF);} printf("%d",dinic(s,t)); return ;
}
20161111
最新文章
- Unity3D框架插件uFrame实践记录(一)
- 2016 windows安装phing:安装成功
- 团队项目——编写项目的Spec
- C#实现对Windows 服务安装
- ContentProvider备份短信,以xml文件存储
- unity 全屏乱影 BlitMultiTap
- 开发一个struts2的实例
- GWT 中日期格式化 ,处置Date
- JVM工作原理和特点(一些二逼的逼神面试官会问的问题)
- Action3D
- CodeForces 703D Mishka and Interesting sum
- PostgreSQL查询优化之子查询优化
- jquery的done和then区别
- Python基础学习篇章三
- 视频当道的时代,这些珍藏的优质 Python 播客值得推荐
- Java并发编程面试题 Top 50 整理版
- editormd实现文章详情页面预览
- (转)Maven之自定义archetype生成项目骨架
- Centos7部署ntp服务器同步时间以及直接将本地时间同步为北京时间
- 学习笔记 | Set
热门文章
- Springboot打包后,获取不到resource目录下资源文件的报错
- matplotlib添加子图(拼图功能)
- cb45a_c++_STL_算法_删除_(3)_unique(唯一的意思)删除连续性的重复的数据
- TopK问题,数组中第K大(小)个元素问题总结
- Meteva——让预报检验不再重复造轮子
- JavaWeb网上图书商城完整项目--25.注册页面之隐藏没有内容的错误信息实现
- junit配合catubuter统计单元测试的代码覆盖率
- 近期Java高级开发岗面试总结
- Asp.net Core AOP实现(采用Autofac)
- 想做时间管理大师?你可以试试Mybatis Plus代码生成器