给出一些点, 每个点有一个权值, 给出一些边, 起点以及终点, 去掉一些点使得起点和终点不连通, 求最小的val。
拆点, 把一个点s拆成s和s', 之间建一条边, 权值为点权。 对于一条边, <u, v> 建边<u, v'>, <v, u'> 权值为inf, 跑一遍最大流。
#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ull unsigned long long
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxx = ;
const int maxn = ;
int head[maxn*], s, t, num, q[maxn*], dis[maxn];
struct node
{
int to, nextt, c;
}e[maxn*];
void init() {
mem1(head);
num = ;
}
void add(int u, int v, int c) {
e[num].to = v; e[num].nextt = head[u]; e[num].c = c; head[u] = num++;
e[num].to = u; e[num].nextt = head[v]; e[num].c = ; head[v] = num++;
}
int bfs() {
int u, v, st = , ed = ;
mem(dis);
dis[s] = ;
q[ed++] = s;
while(st<ed) {
u = q[st++];
for(int i = head[u]; ~i; i = e[i].nextt) {
v = e[i].to;
if(e[i].c&&!dis[v]) {
dis[v] = dis[u]+;
if(v == t)
return ;
q[ed++] = v;
}
}
}
return ;
}
int dfs(int u, int limit) {
if(u == t)
return limit;
int cost = ;
for(int i = head[u]; ~i; i = e[i].nextt) {
int v = e[i].to;
if(e[i].c&&dis[u] == dis[v]-) {
int tmp = dfs(v, min(limit-cost, e[i].c));
if(tmp>) {
e[i].c -= tmp;
e[i^].c += tmp;
cost += tmp;
if(cost == limit)
break;
} else {
dis[v] = -;
}
}
}
return cost;
}
int dinic() {
int ans = ;
while(bfs()) {
ans += dfs(s, inf);
}
return ans;
}
int main()
{
int n, m, val, x, y;
while(cin>>n>>m) {
cin>>s>>t;
t+=n;
init();
for(int i = ; i<=n; i++) {
scanf("%d", &val);
add(i, i+n, val);
}
while(m--) {
scanf("%d%d", &x, &y);
add(x+n, y, inf);
add(y+n, x, inf);
}
int ans = dinic();
cout<<ans<<endl;
}
}
hdu 4289 Control 网络流的更多相关文章
-
HDU 4289 Control (网络流,最大流)
HDU 4289 Control (网络流,最大流) Description You, the head of Department of Security, recently received a ...
-
hdu 4289 Control(最小割 + 拆点)
http://acm.hdu.edu.cn/showproblem.php?pid=4289 Control Time Limit: 2000/1000 MS (Java/Others) Mem ...
-
HDU 4289 Control (最小割 拆点)
Control Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Su ...
-
HDU 4289 Control 最小割
Control 题意:有一个犯罪集团要贩卖大规模杀伤武器,从s城运输到t城,现在你是一个特殊部门的长官,可以在城市中布置眼线,但是布施眼线需要花钱,现在问至少要花费多少能使得你及时阻止他们的运输. 题 ...
-
HDU 4289 Control
最小割 一个点拆成两个 AddEdge(i,i+N,x); 原图中的每条边这样连 AddEdge(u+N,v,INF); AddEdge(v+N,u,INF); S是源点,t+N是汇点.最大流就是答案 ...
-
HDU - 4289 Control (Dinic)
You, the head of Department of Security, recently received a top-secret information that a group of ...
-
HDU 4289 Control(最大流+拆点,最小割点)
题意: 有一群*要从起点st到en城市集合,你要在路程中的城市阻止他们,使得他们全部都被抓到(当然st城市,en城市也可以抓捕).在每一个城市抓捕都有一个花费,你要找到花费最少是多少. 题解: ...
-
hdu 4289 最大流拆点
大致题意: 给出一个又n个点,m条边组成的无向图.给出两个点s,t.对于图中的每个点,去掉这个点都需要一定的花费.求至少多少花费才能使得s和t之间不连通. 大致思路: 最基础的拆点最大 ...
-
(网络流 最大流 Dinic || SAP)Control -- hdu --4289
链接: http://acm.hdu.edu.cn/showproblem.php?pid=4289 http://acm.hust.edu.cn/vjudge/contest/view.action ...
随机推荐
-
css3中的颜色
1颜色.color:rgba(R,G,B,A) R,G,B是分别代笔红,绿,蓝值是在0到255之间的数也可以是0.0% - 100.0%,A代表的是透明度0到1之间. 2.渐变.background- ...
-
container error log
learn from error- Error: org.apache.hadoop.mapreduce.task.reduce.Shuffle$ShuffleError: error in shuf ...
-
AspectJ 出现错误::0 can&#39;t find referenced pointcut 的解决之道
使用AspectJ注解开发AOP应用时,会遇到以下问题: ::0 can't find referenced pointcut 这个问题,与你所在的开发环境有关,如下表 jdk version spr ...
-
你需要知道的九大排序算法【Python实现】之快速排序
五.快速排序 基本思想: 通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则分别对这两部分继续进行排序,直到整个序列有序. 算法实现: #coding: ...
-
Spring Boot 系列(四)静态资源处理
在web开发中,静态资源的访问是必不可少的,如:图片.js.css 等资源的访问. spring Boot 对静态资源访问提供了很好的支持,基本使用默认配置就能满足开发需求. 一.默认静态资源映射 S ...
-
Openfire注册流程代码分析
Openfire注册流程代码分析 一.客户端/服务端注册用户流程 经过主机连接消息确认后,客户端共发送俩条XML完成注册过程.服务器返回两条XML. 注:IQ消息节点用于处理用户的注册.好友.分组.获 ...
-
chroot的用法
chroot命令用来在指定的根目录下运行指令.chroot,即 change root directory (更改 root 目录).在 linux 系统中,系统默认的目录结构都是以/,即是以根 (r ...
-
kworker内核工作队列详解
工作队列是另一种将工作推后执行的形式,它可以把工作交给一个内核线程去执行,这个下半部是在进程上下文中执行的,因此,它可以重新调度还有睡眠. 区分使用软中断/tasklet还是工作队列比较简单,如 ...
-
java比较字符串相等
java中String是对象类型,不能使用"=="比较.正确的用法如下: if(A.equals(B)){ //相等 }
-
PAT——1070. 结绳
给定一段一段的绳子,你需要把它们串成一条绳.每次串连的时候,是把两段绳子对折,再如下图所示套接在一起.这样得到的绳子又被当成是另一段绳子,可以再次对折去跟另一段绳子串连.每次串连后,原来两段绳子的长度 ...