bzoj1339[Baltic2008]Mafia

题意:

匪徒准备从一个车站转移毒品到另一个车站,警方准备进行布控。对于每个车站进行布控都需要一定的代价,现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后,匪徒无法从原定的初始点到达目标点。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

最新文章

  1. Unity3D框架插件uFrame实践记录(一)
  2. 2016 windows安装phing:安装成功
  3. 团队项目——编写项目的Spec
  4. C#实现对Windows 服务安装
  5. ContentProvider备份短信,以xml文件存储
  6. unity 全屏乱影 BlitMultiTap
  7. 开发一个struts2的实例
  8. GWT 中日期格式化 ,处置Date
  9. JVM工作原理和特点(一些二逼的逼神面试官会问的问题)
  10. Action3D
  11. CodeForces 703D Mishka and Interesting sum
  12. PostgreSQL查询优化之子查询优化
  13. jquery的done和then区别
  14. Python基础学习篇章三
  15. 视频当道的时代,这些珍藏的优质 Python 播客值得推荐
  16. Java并发编程面试题 Top 50 整理版
  17. editormd实现文章详情页面预览
  18. (转)Maven之自定义archetype生成项目骨架
  19. Centos7部署ntp服务器同步时间以及直接将本地时间同步为北京时间
  20. 学习笔记 | Set

热门文章

  1. Springboot打包后,获取不到resource目录下资源文件的报错
  2. matplotlib添加子图(拼图功能)
  3. cb45a_c++_STL_算法_删除_(3)_unique(唯一的意思)删除连续性的重复的数据
  4. TopK问题,数组中第K大(小)个元素问题总结
  5. Meteva——让预报检验不再重复造轮子
  6. JavaWeb网上图书商城完整项目--25.注册页面之隐藏没有内容的错误信息实现
  7. junit配合catubuter统计单元测试的代码覆盖率
  8. 近期Java高级开发岗面试总结
  9. Asp.net Core AOP实现(采用Autofac)
  10. 想做时间管理大师?你可以试试Mybatis Plus代码生成器