注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1339/1163][Baltic2008]Mafia  

2015-03-16 21:15:46|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1339: [Baltic2008]Mafia

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 259  Solved: 155
[Submit][Status][Discuss]

Description

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

Input

第一行输入N,M代表车站的总个数,及有多少条双向边连接它们. 2<=n<=200 , 1 <=m<=20000. 第二行给出两个数a,b,代表匪徒的出发点及目标点.1<=a,b<=N,a<>b. 再下来有N行,给出对第i个车站进行布控所需要的Money,其不超过10 000 000 再下来M行,用于描述图的结构.

Output

最少需要多少Money

Sample Input

5 6 5 3 2 4 8 3 10 1 5 1 2 2 4 4 5 2 3 3 4

Sample Output

5

Solution

第一眼还以为是树DP,然后仔细想想这TM不是直接流吗。。。
题目中给出了源点和汇点。
对于每个点,拆成入点和出点,中间连一条容量为控制该点价值的边,当这条边为割边就意味着要控制这个点。
对于原图中的点,连一条双向边,容量为正无穷,这就意味着这条边怎么也不会被割掉。
然后直接流,流出来的就是答案。

Code

/**************************************************************
    Problem: 1339
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:444 ms
    Memory:3284 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
const int N=500,M=100000;
int cur[N],d[N],s,t,l,r,q[1<<15],la[N],et=1;
struct E{int to,v,nxt;}e[M<<1];
void add(int x,int y,int v){
    e[++et]=(E){y,v,la[x]},la[x]=et;
    e[++et]=(E){x,0,la[y]},la[y]=et;
}
int bfs(){
    memset(d,0,sizeof(d));
    for(q[l=r=0]=t,d[t]=1;l<=r;l++)
    for(int i=la[q[l]];i;i=e[i].nxt)
    if(e[i^1].v&&d[e[i].to]==0)d[q[++r]=e[i].to]=d[q[l]]+1;
    return d[s];
}
#define min(a,b) (a<b?a:b)
int dfs(int x,int flow){
    if(x==t)return flow;
    int now=0,tmp;
    for(int&i=cur[x];i;i=e[i].nxt)
    if(d[x]==d[e[i].to]+1&&e[i].v){
        tmp=dfs(e[i].to,min(e[i].v,flow-now));
        e[i].v-=tmp,e[i^1].v+=tmp,now+=tmp;
        if(now==tmp)return now;
    }
    return now;
}
int maxflow(){
    int flow=0;
    while(bfs())memcpy(cur,la,sizeof(la)),flow+=dfs(s,1<<30);
    return flow;
}
int n,m,i,x,y;
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);t+=n;
    for(i=1;i<=n;i++)scanf("%d",&x),add(i,i+n,x);
    for(i=1;i<=m;i++)scanf("%d%d",&x,&y),add(x+n,y,1<<20),add(y+n,x,1<<20);
    printf("%d\n",maxflow());
}

  评论这张
 
阅读(136)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018