POJ–2391–Ombrophobic Bovines【分割点+Floyd+Dinic优化+二分法答案】最大网络流量

POJ–2391–Ombrophobic Bovines【分割点+Floyd+Dinic优化+二分法答案】最大网络流量

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

联系:http://poj.org/problem?id=2391

题意:有f个草场,每一个草场当前有一定数目的牛在吃草,下雨时它能够让一定数量的牛在这里避雨,f个草场间有m条路连接,每头牛通过一条路从一点到还有一点有一定的时间花费,如今要下雨了,农场主发出警报牛就会马上去避雨。

如今告诉每一个草场的情况。以及m条边的信息。农场主至少须要提前多久发出警报才干保证全部牛都能避雨?假设不是全部牛都能成功避雨输出-1。

思路:这道题须要拆点,是看到魏神的博客才知道的。我们把原图拆成一个二分图,避免突破最大距离限制的情况,每一个点变成两个点,即i变为i‘和i’‘,建立一个源点连接每一个i’,容量为初始每一个草场牛的数目。建立一个汇点,全部的i‘’指向汇点,容量为每一个草场能容纳的牛的数目。假设两个点i和j连接。则在i’和j‘’以及j‘和i’‘之间建一条路径。容量为INF,能够走无限多的牛。然后这道题就和之前做的一道POJ2112一样了,POJ2112不用拆点,由于它本身就是一个二分图。

接下来就是Floyd处理出随意两点间最短路径。然后二分答案。

可是这道题还没有完,我套之前的Dinic模板,TLE了。这道题最大可能的边数比POJ2112大,而Case时限一样,我手写队列。还是TLE,我再把vis数组去掉用dist取代vis功能,还是TLE,我在网上搜AC的Dinic代码,看到一个和我的差点儿相同。粘贴交了一发。TLE,无力吐槽。。。

找到了一个看上去有些修改的代码,依照它修改的地方改我自己的。219MS AC。

我看了一下。我认为基本的优化地方是这样:

1. 我之前的模板,是从源点起找遍每一条增广路进行松弛,优化算法是找到一条增广路松弛、退出,更新最大流值,再找下一条,直到更新值返回0说明已更新到头,避免了多余的搜索。

2. 假设此时的顶点已不存在增广路,将它从当前的层次网络中删除。回溯后不会再搜。

我认为这是两个优化到的地方,这么进行了优化之后效率提升非常明显!

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 200100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define mod 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct node{
    int u,w,next;
}edge[100010];
int head[410],dist[410],q[410];
int aa[410],bb[410];
ll e[410][410];
int n,m,cnt,src,sink,f,p;
void add_edge(int a,int b,int c){
    edge[cnt].u = b;
    edge[cnt].w = c;
    edge[cnt].next = head[a];
    head[a] = cnt++;
}
void floyd(){
    int i,j,k;
    for(k=1;k<=f;k++){
        for(i=1;i<=f;i++){
            if(e[i][k]==LLINF)  continue;
            for(j=1;j<=f;j++){
                if(e[i][k]+e[k][j]<e[i][j]&&e[i][k]!=LLINF&&e[k][j]!=LLINF)
                    e[i][j] = e[i][k] + e[k][j];
            }
        }
    }
}
void build_graph(ll minm){
    int i,j;
    cnt = 0;
    memset(head,-1,sizeof(head));
    for(i=1;i<=f;i++){
        add_edge(src,i,aa[i]);
        add_edge(i,src,0);
        add_edge(i+f,sink,bb[i]);
        add_edge(sink,i+f,0);
        for(j=1;j<=f;j++){
            if(e[i][j]<=minm){
                add_edge(i,j+f,INF);
                add_edge(j+f,i,0);
            }
        }
    }
}
bool bfs(){
    int i,j;
    memset(dist,-1,sizeof(dist));
    int f = 0, t = 1;
    q[0] = src;
    dist[src] = 1;
    while(f<t){
        int u = q[f++];
        for(i=head[u];i!=-1;i=edge[i].next){
            int v = edge[i].u;
            if(dist[v]==-1&&edge[i].w){
                dist[v] = dist[u] + 1;
                q[t++] = v;
            }
        }
    }
    if(dist[sink]!=-1)  return true;
    return false;
}
int dfs(int u,int delta){
    int i,j;
    int dd;
    if(u==sink) return delta;
    for(i=head[u];i!=-1;i=edge[i].next){
        if(dist[edge[i].u]==dist[u]+1&&edge[i].w&&(dd = dfs(edge[i].u,min(delta,edge[i].w)))){
            edge[i].w -= dd;
            edge[i^1].w += dd;
            return dd;
        }
    }
    dist[u] = -1;
    return 0;
}
int main(){
    int i,j;
    int ta,tb,tc;
    int cow;
    scanf("%d%d",&f,&p);
    n = 2 * f + 2;
    src = 0;
    sink = 2 * f + 1;
    cow = 0;
    for(i=1;i<=f;i++){
        scanf("%d%d",&aa[i],&bb[i]);
        cow += aa[i];
    }
    for(i=0;i<=f;i++){
        for(j=0;j<=f;j++)
            e[i][j] = LLINF;
        e[i][i] = 0;
    }
    for(i=0;i<p;i++){
        scanf("%d%d%d",&ta,&tb,&tc);
        if(tc<e[ta][tb])    e[ta][tb] = e[tb][ta] = tc;
    }
    floyd();
    ll mid,l = 0,r = 0;
    for(i=1;i<=f;i++){
        for(j=1;j<=f;j++){
            if(e[i][j]!=LLINF)  r = max(e[i][j],r);
        }
    }
    int sum;
    ll ans = -1;
    while(l<=r){
        mid = (l+r)>>1LL;
        //cout<<l<<" "<<r<<endl;
        sum = 0;
        build_graph(mid);
        while(bfs()){
            while(1){
                int ttt = dfs(src,INF);
                if(!ttt)    break;
                sum += ttt;
            }
        }
        if(sum==cow){
            ans = mid;
            r = mid-1;
        }
        else    l = mid + 1;
    }
    printf("%I64d\n",ans);
    return 0;
}

版权声明:本文博主原创文章。博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117083.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • A 股历年三大财务报表 API 接口「建议收藏」

    A股历年三大财务报表历年所有财报数据,全量A股数据,最全三大财报数据。1.产品功能支持所有A股全量三大财报数据查询;分别包括资产负债表、利润表、现金流量表数据;返回70多项财务指标;多数据源清洗整合,百万级数据毫秒级返回;全接口支持HTTPS(TLSv1.0/v1.1/v1.2/v1.3);全面兼容AppleATS;全国多节点CDN部署;接口极速响应,多台服务器构建API接口负载均衡。2.API文档接口详情:https://www.

  • 《自然语言处理实战入门》 —- 第4课 :中文分词原理及相关组件简介 之 语言学与分词技术简介…

    《自然语言处理实战入门》—-第4课:中文分词原理及相关组件简介之语言学与分词技术简介https://edu.csdn.net/course/play/20769/25954…

  • python转换函数使用_python进制转换函数代码的使用

    python转换函数使用_python进制转换函数代码的使用python进制转换函数代码的使用发布时间:2020-04-2310:23:22来源:亿速云阅读:188作者:小新以上就是python进制转换函数代码的使用的详细内容了,看完之后是否有所收获呢?如果想了解更多相关内容,欢迎来亿速云行业资讯!python如何进行进制转换1、十进制转二进制(bin)首先我们看看怎么把一个十进制转化成二进制,我们可以使用python的内置方法bindec=10pri…

  • navicat for mysql如何导入sql文件_excel怎么把0显示出来

    navicat for mysql如何导入sql文件_excel怎么把0显示出来NavicatforMySQL导入excel文件_水里的鱼不会羡慕陆地爬行的动物-CSDN博客NavicatforMySQL是连接数据库的工具,可以更好地管理数据库。1.先连接连接名和主机名都是IP,本地连接名和主机名是localhost或127.0.0.1。-2.创建数据库及表表已经创建好了接下来就将含有学生信息的class.xls表导入到message表中2.1点击导入向导2.2表中我的数据放在sheet12.3这里我从第二行…

  • pycharm哪个版本_pycharm版本选择

    pycharm哪个版本_pycharm版本选择Pycharm各大版本Pycharm作为python最常见的IDE,常见的有三种版本专业版:功能强大,适合开发者,需要通过付费或学生认证才能使用社区版:可以供广大python爱好者免费使用,具备常用的python库,可以实现基本的python用法,用于试验在工作中出现的错误教育版:基于社区版发展而来,也是免费使用,其功能与社区版相似,但是更适合学生,新人学习,由教师可以创建工程、教学…

  • db2codepage作用_dbcc checktable

    db2codepage作用_dbcc checktable1、db2变量查看  db2set-all  (connecttodbanme)getdbcfg  db2pd-osinfo这个命令很强大哦  2、db2c变量的设置用命令  db2set变量=value  可以参考一下:  客户端:  db2codepage=1386(简体中文)  db2country

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号