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

n+e

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

 
 
 

日志

 
 

[BZOJ3789]扫雪车  

2015-06-20 19:31:39|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3789: 扫雪车

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 64  Solved: 26
[Submit][Status][Discuss]

Description

n个城市和m条单向道路构成一个有向图,每条道路e上有整数积雪量We。一辆扫雪车每天从城市s开到t,经过一条道路一次就将其雪量减1(不能走雪量为0的道路)。有些道路(称为重要道路)必须清空积雪,这些道路的导出子图是包含s的弱连通图。求扫雪车工作天数的最大值。或判断无解。
弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

Input

第一行四个数n,m,s,t。
下面m行,每行四个数x,y,w,t。表示这条道路连接的两个城市,积雪量,和道路种类。若t为0则是普通道理,t为1则是重要道路。

Output

扫雪车工作天数的最大值。或判断无解,输出0。

Sample Input

4 7 1 4 1 2 3 1 2 1 100 0 2 4 1 0 1 3 1 0 3 4 4 0 2 3 2 1 1 4 2 0

Sample Output

6

HINT

2 ≤ n ≤ 100; 0 ≤ m ≤ 5000; 1 ≤ s,t ≤ n; s ≠ t 
1 ≤ xi,yi ≤ n; xi ≠ yi; 0 ≤ wi ≤ 100; 0 ≤ ti ≤ 1 

Solution

强制走:下界为w,上界为w
不强制走:下界为0,上界为w
上下界网络流流一遍就好了
输出方案的话,t往s连ans-1条边,于是就变成了欧拉回路。

Code

/**************************************************************
    Problem: 3789
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:6140 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 110
int n,m,et,la[N],s,t,sp,tp,sum,x,y,v,c;
struct E{int to,v,nxt;}e[5010];
void add(int x,int y,int v){
    e[++et]=(E){y,v,la[x]},la[x]=et;
}
class NF{public:
    int et,la[N],d[N],cur[N],flow,q[N],l,r,s,t;
    struct E{int to,flow,nxt;}e[100000];
    NF(){et=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].flow&&!d[e[i].to])d[q[++r]=e[i].to]=d[q[l]]+1;
        return d[s];
    }
    int dfs(int x,int ret){
        if(x==t||ret==0)return ret;
        int flow=0,tmp;
        for(int&i=cur[x];i;i=e[i].nxt)
        if(d[x]==d[e[i].to]+1){
            tmp=dfs(e[i].to,e[i].flow<ret-flow?e[i].flow:ret-flow);
            e[i].flow-=tmp,e[i^1].flow+=tmp,flow+=tmp;
            if(flow==ret)return flow;
        }
        return flow;
    }
    int maxflow(int _s,int _t){
        s=_s,t=_t;flow=0;
        while(bfs())memcpy(cur,la,sizeof(la)),flow+=dfs(s,1<<30);
        return flow;
    }
    void clr(int x){
        for(int i=la[x];i;i=e[i].nxt)e[i].flow=e[i^1].flow=0;
    }
}G;
int ans[1<<20],tot;
void dfs(int x){
    for(int i=la[x];i;i=e[i].nxt)
    if(e[i].v){
        e[i].v--;dfs(e[i].to);ans[++tot]=e[i].to;
    }
     
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);sp=n+1,tp=n+2;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&x,&y,&v,&c);
        if(c==0)G.add(x,y,v);
        else{
            G.add(sp,y,v),G.add(x,tp,v);sum+=v;
            add(x,y,v);
        }
    }
    G.add(t,s,1<<20);
    if(G.maxflow(sp,tp)!=sum)return puts("0"),0;
    sum=G.e[et].flow;
    G.clr(sp),G.clr(tp);G.e[et].flow=G.e[et^1].flow=0;
    sum+=G.maxflow(s,t);
    printf("%d\n",sum);
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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