poj3228最大流+拆点+二分

作者：旧梦半分_399 | 来源：互联网 | 2023-08-19 13:23

这道题与poj2391方法完全一样如果不会可以先看我写的poj2391的题解：http:blog.csdn.netfrozensmilearticledetails77045408然

这道题与poj2391方法完全一样

如果不会可以先看我写的poj2391的题解：http://blog.csdn.net/frozensmile/article/details/77045408 然后再用这道题练手

79ms过

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
const int MAXN=405;//jiedian de zui da zhi
const int MAXM=45000;//bian de zui da zhi
const int INF=0x3f3f3f3f;

struct Node
{
    int from,to,next;
    int cap;
}edge[MAXM];
int tol;
int head[MAXN];
int dep[MAXN];
int gap[MAXN];

int sto[205];
int stoh[205];
int bian[20005][3];
void init()  //remember write it in main function
{
    tol=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int w)
{
    edge[tol].from=u;
    edge[tol].to=v;
    edge[tol].cap=w;
    edge[tol].next=head[u];
    head[u]=tol++;
    edge[tol].from=v;
    edge[tol].to=u;
    edge[tol].cap=w;//wuxiangtu  this place change to w;
    edge[tol].next=head[v];
    head[v]=tol++;
}
void BFS(int start,int end)
{
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]=1;
    int que[MAXN];
    int front,rear;
    frOnt=rear=0;
    dep[end]=0;
    que[rear++]=end;
    while(front!=rear)
    {
        int u=que[front++];
        if(frOnt==MAXN)frOnt=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dep[v]!=-1)continue;
            que[rear++]=v;
            if(rear==MAXN)rear=0;
            dep[v]=dep[u]+1;
            ++gap[dep[v]];
        }
    }
}
int SAP(int start,int end,int n) //n shi jiedian de zui da ge shu ,including source and sink
{
    int res=0;
    BFS(start,end);
    int cur[MAXN];
    int S[MAXN];
    int top=0;
    memcpy(cur,head,sizeof(head));
    int u=start;
    int i;
    while(dep[start]    {
        if(u==end)
        {
            int temp=INF;
            int inser;
            for(i=0;i                if(temp>edge[S[i]].cap)
                {
                    temp=edge[S[i]].cap;
                    inser=i;
                }
            for(i=0;i            {
                edge[S[i]].cap-=temp;
                edge[S[i]^1].cap+=temp;
            }
            res+=temp;
            top=inser;
            u=edge[S[top]].from;
        }
        if(u!=end&&gap[dep[u]-1]==0)
            break;
        for(i=cur[u];i!=-1;i=edge[i].next)
            if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1)
                break;
        if(i!=-1)
        {
            cur[u]=i;
            S[top++]=i;
            u=edge[i].to;
        }
        else
        {
            int min=n;
            for(i=head[u];i!=-1;i=edge[i].next)
            {
                if(edge[i].cap==0)continue;
                if(min>dep[edge[i].to])
                {
                    min=dep[edge[i].to];
                    cur[u]=i;
                }
            }
            --gap[dep[u]];
            dep[u]=min+1;
            ++gap[dep[u]];
            if(u!=start)u=edge[S[--top]].from;
        }
    }
    return res;
}
void getmap(int mid,int m,int n)
{
    init();
    int i;
    for(i=1;i<=n;i++)
    {
        addedge(0, i, sto[i]);
        addedge(i+n, 2*n+1, stoh[i]);
        addedge(i, i+n, INF);
    }
    for(i=1;i<=m;i++)
    {
        if(bian[i][2]<=mid)
        {
            addedge(bian[i][0], bian[i][1]+n, INF);
        }
    }
    
    
}
int main()
{
    int i,j,k,n,m;
    while(scanf("%d",&n)==1)
    {
        if(n==0)break;
       
        int sum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&sto[i]);//i点现在有多少矿物
            sum+=sto[i];//二分时求得的最大流必须大于等于sum才符合题意
        }
        for(i=1;i<=n;i++)
        {
            scanf("%d",&stoh[i]);//i点的最大存储量

        }
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&bian[i][0],&bian[i][1],&bian[i][2]);//记录边
            
        }
        int l=0,r=0x3f3f3f3f,mid,ans=-1;
        while(l<=r)
        {
            mid=(l+r)/2;
            getmap(mid,m,n);
            if(SAP(0,2*n+1,2*n+2)>=sum)
            {
                ans=mid;
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
            
        }
        if(ans==-1)printf("No Solution\n");
        else printf("%d\n",ans);
    }
    return 0;
}

推荐阅读

int
如何撰写适应变化的高效代码：策略与实践

编写高质量且适应变化的代码是每位程序员的追求。优质代码的关键在于其可维护性和可扩展性。本文将从面向对象编程的角度出发，探讨实现这一目标的具体策略与实践方法，帮助开发者提升代码效率和灵活性。 ... [详细]

蜡笔小新 2024-11-09 10:20:32
int
2018 HDU 多校联合第五场 G题：Glad You Game（线段树优化解法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6356在《Glad You Game》中，Steve 面临一个复杂的区间操作问题。该题可以通过线段树进行高效优化。具体来说，线段树能够快速处理区间更新和查询操作，从而大大提高了算法的效率。本文详细介绍了线段树的构建和维护方法，并给出了具体的代码实现，帮助读者更好地理解和应用这一数据结构。 ... [详细]

蜡笔小新 2024-11-08 19:17:23
int
使用 QT 实现 YUV420 图像渲染技术

在使用 Qt 进行 YUV420 图像渲染时，由于 Qt 本身不支持直接绘制 YUV 数据，因此需要借助 QOpenGLWidget 和 OpenGL 技术来实现。通过继承 QOpenGLWidget 类并重写其绘图方法，可以利用 GPU 的高效渲染能力，实现高质量的 YUV420 图像显示。此外，这种方法还能显著提高图像处理的性能和流畅性。 ... [详细]

蜡笔小新 2024-11-09 15:02:41
int
C++ 编程指南：第16条——在对应的新建和删除操作中使用相同的形式

当使用 `new` 表达式（即通过 `new` 动态创建对象）时，会发生两件事：首先，内存被分配用于存储新对象；其次，该对象的构造函数被调用以初始化对象。为了确保资源管理的一致性和避免内存泄漏，建议在使用 `new` 和 `delete` 时保持形式一致。例如，如果使用 `new[]` 分配数组，则应使用 `delete[]` 来释放内存；同样，如果使用 `new` 分配单个对象，则应使用 `delete` 来释放内存。这种一致性有助于防止常见的编程错误，提高代码的健壮性和可维护性。 ... [详细]

蜡笔小新 2024-11-09 12:21:19
web
ESP8266 01S Web 服务器成功启动：详细解决方案与实践指南

本文详细介绍了一种利用 ESP8266 01S 模块构建 Web 服务器的成功实践方案。通过具体的代码示例和详细的步骤说明，帮助读者快速掌握该模块的使用方法。在疫情期间，作者重新审视并研究了这一未被充分利用的模块，最终成功实现了 Web 服务器的功能。本文不仅提供了完整的代码实现，还涵盖了调试过程中遇到的常见问题及其解决方法，为初学者提供了宝贵的参考。 ... [详细]

蜡笔小新 2024-11-08 19:12:49
jsp
NOIP2000单词接龙题目解析与学习心得

NOIP2000的单词接龙问题与常见的成语接龙游戏有异曲同工之妙。题目要求在给定的一组单词中，从指定的起始字母开始，构建最长的“单词链”。每个单词在链中最多可出现两次。本文将详细解析该题目的解法，并分享学习过程中的心得体会。 ... [详细]

蜡笔小新 2024-11-08 14:01:31
jsp
Linux 环境下多线程编程实战案例分析

在 Linux 环境下，多线程编程是实现高效并发处理的重要技术。本文通过具体的实战案例，详细分析了多线程编程的关键技术和常见问题。文章首先介绍了多线程的基本概念和创建方法，然后通过实例代码展示了如何使用 pthreads 库进行线程同步和通信。此外，还探讨了多线程程序中的性能优化技巧和调试方法，为开发者提供了宝贵的实践经验。 ... [详细]

蜡笔小新 2024-11-08 13:02:21
jsp
Java中不同类型的常量池（字符串常量池、Class常量池和运行时常量池）的对比与关联分析

在研究Java虚拟机的过程中，笔者发现存在多种类型的常量池，包括字符串常量池、Class常量池和运行时常量池。通过查阅CSDN、博客园等相关资料，对这些常量池的特性、用途及其相互关系进行了详细探讨。本文将深入分析这三种常量池的差异与联系，帮助读者更好地理解Java虚拟机的内部机制。 ... [详细]

蜡笔小新 2024-11-08 10:38:37
jsp
洛谷 P1344 坏牛奶追踪问题（最小割算法应用）

在洛谷 P1344 的坏牛奶追踪问题中，第一问要求计算最小割，而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值，可以在求解最小割时优先选择边数较少的方案，从而同时解决两个问题。这种策略不仅简化了问题的求解过程，还确保了结果的最优性。 ... [详细]

蜡笔小新 2024-11-07 14:50:22
jsp
C#中实例化后，对象如何重新调用其构造函数以实现特定功能

在C#中，一旦对象被实例化后，直接重新调用构造函数是不可行的。与C++不同，C#不支持在对象实例化后强制调用构造函数。为了实现类似的功能，可以通过定义一个重置方法或使用工厂模式来重新初始化对象的状态。例如，可以创建一个 `Reset` 方法，在该方法中重新设置对象的属性和状态，从而达到类似于重新调用构造函数的效果。这样不仅保持了代码的清晰性和可维护性，还避免了潜在的副作用。 ... [详细]

蜡笔小新 2024-11-10 13:32:07
jsp
iOS中基于HTTPS协议的安全网络请求实现

在iOS开发中，基于HTTPS协议的安全网络请求实现至关重要。HTTPS（全称：HyperText Transfer Protocol over Secure Socket Layer）是一种旨在提供安全通信的HTTP扩展，通过SSL/TLS加密技术确保数据传输的安全性和隐私性。本文将详细介绍如何在iOS应用中实现安全的HTTPS网络请求，包括证书验证、SSL握手过程以及常见安全问题的解决方法。 ... [详细]

蜡笔小新 2024-11-08 17:13:51
jsp
暑假强化训练：计算几何深度探索

经过两天的努力，终于成功解决了半平面交模板题POJ3335的问题。原来是在`OnLeft`函数中漏掉了关键的等于号。通过这次训练，不仅加深了对半平面交算法的理解，还提升了调试和代码实现的能力。未来将继续深入研究计算几何的其他核心问题，进一步巩固和拓展相关知识。 ... [详细]

蜡笔小新 2024-11-08 16:20:55
jsp
Kafka 版本不兼容引发 TaskExecutor 启动故障分析与解决

在本地环境中部署了两个不同版本的 Flink 集群，分别为 1.9.1 和 1.9.2。近期在尝试启动 1.9.1 版本的 Flink 任务时，遇到了 TaskExecutor 启动失败的问题。尽管 TaskManager 日志显示正常，但任务仍无法成功启动。经过详细分析，发现该问题是由 Kafka 版本不兼容引起的。通过调整 Kafka 客户端配置并升级相关依赖，最终成功解决了这一故障。 ... [详细]

蜡笔小新 2024-11-08 14:13:56
js
洛谷 P4035 [JSOI2008] 球形空间生成器（高斯消元法 / 模拟退火算法）

本文介绍了洛谷 P4035 [JSOI2008] 球形空间生成器问题的解决方案，主要使用了高斯消元法和模拟退火算法。通过这两种方法，可以高效地求解多维空间中的球心位置。文章提供了详细的算法模板和实现代码，适用于 ACM 竞赛和其他相关应用场景。数据范围限制在 10 以内，确保了算法的高效性和准确性。 ... [详细]

蜡笔小新 2024-11-08 13:55:00
import
开发日志：201521044091 《Java编程基础》第11周学习心得与总结

开发日志：201521044091 《Java编程基础》第11周学习心得与总结 ... [详细]

蜡笔小新 2024-11-08 11:15:11

旧梦半分_399

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章