精华内容
下载资源
问答
  • 重定向和管道

    2013-11-09 01:13:05
    要了解重定向和管道规则,我们需要引入一个前文并未引入的概念。绝大部分 UNIX® 进程(包括图形应用程序,但不包括绝大多数守护程序)至少使用三个文件描述符:标准输入、标准输出和标准错误输出。它们相应序号...
    
    

    重定向和管道

    关于进程的一些补充

    要了解重定向和管道的规则,我们需要引入一个前文并未引入的概念。绝大部分 UNIX® 进程(包括图形应用程序,但不包括绝大多数守护程序)至少使用三个文件描述符:标准输入、标准输出和标准错误输出。它们相应的序号是 0、1 和 2。一般来说,这三个描述符与该进程启动的终端相关联,其中输入为键盘。重定向和管道的目的是重定向这些描述符。本节中的实例将帮助您更好地了解这些概念。

    重定向

    假设您想要一张 images 目录中所有以 .png 结尾的文件[6]列表。该列表非常长,因此您会想把它先放到一个文件中,然后在有空的时候查看。您可以输入下述命令:

    $ ls images/*.png 1>file_list

    这表示把该命令的标准输出(1)重定向到(>)file_list 文件。其中的 > 操作符是输出重定向符。如果要重定向到的文件不存在,它将被创建;不过如果它已经存在,那么它先前的内容将被覆盖。不过,该操作符默认的描述符就是标准输出,因此就不用在命令行上特意指出。所以,上述命令可以简化为:

    $ ls images/*.png >file_list

    其结果是一样的。然后您就可以用某个文本文件查看器(比如 less)来查看。

    现在,假定您想要知道这样的文件有多少。不用手工计数,您可以使用 wc (单词计数(Word Count))这个工具。使用其 -l 选项将在标准输出上显示文件的行数。所以,您可以:

    wc -l 0<file_list

    就可以得到期望的结果。其中的 < 操作符是输入重定向符,并且其默认重定向描述符是标准输入(即 0)。因此您只需:

    wc -l <file_list

    假定您又想去掉其中所有文件的“扩展名”,并将结果保存到另一个文件。要完成这一功能可以使用 sed (流编辑器(Stream EDitor))。您只要将 sed 的标准输入重定向为 file_list,并将其输出重定向到结果文件 the_list

    sed -e 's/\.png$//g' <file_list >the_list

    您所需要的就已被创建,并等待您在有空的时候用任何查看器查看。

    重定向标准错误输出也很有用。例如:您会想要知道在 /shared 中有哪些目录您不能够访问。一个办法是递归地列出该目录并重定向错误输出到某个文件,并且不要显示标准输出:

    ls -R /shared >/dev/null 2>errors

    这表示标准输出将被重定向到(>)/dev/null(所有输出到此特殊文件的东西都将被丢弃,即不显示标准输出),并将标准错误输出(2)重定向到(>)errors 文件。

    管道

    管道在某种程度上是输入和输出重定向的结合。其原理同物理管道类似:一个进程向管道的一端发送数据,而另一个进程从该管道的另一端读取数据。管道符是 |。让我们再来看看上述文件列表的例子。假设您想直接找出有多少对应的文件,而不想先将它们保存到一个临时文件,您可以:

    ls images/*.png | wc -l

    这表示将 ls 命令的标准输出(即文件列表)重定向到 wc 命令的输入。这样您就直接得到了想要的结果。

    您也可以使用下述命令得到“除去扩展名”的文件列表:

    ls images/*.png | sed -e 's/\.png$//g' >the_list

    或者,如果您想要直接查看结果而不想保存到某个文件:

    ls images/*.png | sed -e 's/\.png$//g' | less

    管道和重定向不仅仅只能用于人类可以阅读的文本文件。例如下述来自 终端 的命令:

    xwd -root | convert - ~/my_desktop.png

    将把您桌面的截屏保存到您个人目录中的 my_desktop.png 文件[7]



    [6您可能会觉得奇怪:为什么不直接说“PNG 图片”,而要说“以 .png 结尾的文件”呢?再提醒一次,在 UNIX® 下的扩展名惯例是:扩展名并不表示文件的类型。以 .png 结尾的文件很可能是一个 JPEG 图像、一个应用程序、一个文本文件或者任何什么别的类型的文件。在 Windows® 下也一样!

    [7它确实会是一个 PNG 图片(不过您需要事先安装了 ImageMagick 应用程序包)。

    展开全文
  • hibernate设计者为了更好维护对象,以便生成恰当SQL语句,引入了对象状态这个概念.hibernate文档里面描述hibernate状态分为三种: 瞬时(Transient),又称临时状态 持久(Persistent) 脱(Detached)又称...

    hibernate的设计者为了更好的维护对象,以便生成恰当的SQL语句,引入了对象的状态这个概念.hibernate文档里面描述hibernate的状态分为三种:

    瞬时(Transient),又称临时状态 持久(Persistent) 脱管(Detached)又称游离状态

    其实我也觉得如果按照Hibernate的关于对象的状态定义,状态应该分为四种才对:

    多了一个删除状态,因为游离状态本身也是有对象引用,只是没有被session管理起来,不会被gc回收.四种对象状态的完整定义:

    临时:一般是新new的对象 持久:有OID,对对象的操作都会同步到数据库中 游离:对象有OID,并且与数据中的某条记录对应,修改对象不会同步到数据库 删除:session调用了delete()方法把对象从数据库中删除后状态

    对象状态虽然不多,但是在使用中要格外小心,只有持久状态的对象才能同步到数据库中.管理对象状态的常用方法:

    save():使临时对象持久对象(把对象交给Session管理) update():把游离对象变为持久对象(把对象交给Session管理) saveOrUpdate():把临时对象或游离对象变为持久对象,通过OID判断对象为什么对象 delete():把持久或游离状态变为删除状态(只要是数据库中有记录,就能删除,没有就报错) get():立即加载,如果指定ID的数据不存在,则返回null load():延迟加载,但实体类不能是final的,否则延迟加载失效,如果指定id的数据不存在,则抛异常

    上面这些方法中需要特意说下的是load()方法.load()方法是基于类的懒加载,也就是class标签的lazy属性,默认值为true.在为true的情况下调用load()方法会返回一个代理类,且是一个没有初始化的代理类,只有当使用这个类的某个方法时才会去真正的加载记录;如果没有在数据库中找到对应的记录,则抛出异常.如果类的修饰符是fianl,由于hibernate是使用的继承创建的代理类,所以在这种情况下就不能创建代理类,将立即加载.

    Hibernate中有二级缓存的概念,既然有二级缓存,那也自然就有"一级缓存"了,实际上,一级缓存就是session的缓存,Session 接口是Hibernate向应用程序提供的操纵对数据库的最主要的接口,它提供了基本的保存,更新,删除和加载Java对象的方法.Session接口的实现中包含了一系列的集合,这些集合构成了Session缓存,只要Session实例的生命周期没有结束,存放在它缓存里的对象也不会结束生命周期,因为还有这些集合在引用这些对象.所以如果有对象已经不需要了,就要即时的清除.把对象变为游离状态或者删除状态.

    Session提供了一系列对缓存进行操作的方法:

    clear():清空Session(把Session的缓存中所有的对象全部清除出去) evict(Object):把指定的对象从Session缓存中驱逐出去 flush():把Session缓存中的状态马上同步到数据库.默认情况下,生成的update语句、delete语句都是在flush()执行的时候执行,
              在事务提交的时候会自动的先flush()一下.但是insert语句在什么时候执行,是跟主键生成策略有关的.如果是由数据库生成主
              键,则遇到insert()语句会马上执行,因为需要得到主要值,以便之后使用;如果生成策略是assigned,则会在flush()执行的时候
              执行,因为主键值是由你提供的,所以Hibernate不用问数据库也知道.但是调用flush()方法可以让缓存里面的语句马上执行,以同步状态. refresh(Object):让缓存中的对象与数据库中的数据状态一致.假如我要把一个对象变成持久状态,我先把它从数据库从拿出来(从
               数据库中取出就是持久状态),然后把它的数据进行更新,存储到某个地方,如果在更新---存储的过程之间,数据被另一个人修
               改了,我存储的时候也无法获取最新的数据,因为Hibernate已经查询过一次,已经有了这个对象的持久状态,它便不会再进行
               查询,这个时候如果想要获取最新的数据,就要使用refresh(Object)方法,把想要更新的对象传入进去,Hibernate就会进行再次查询. 

    展开全文
  • 但是宽带的引入开辟了一系列新可靠连接选项,并且随着用于交付它们技术成熟,它们多年来也变得越来越快。 但是,关于如何衡量互联网连接性能仍然存在很多困惑。当我们看各种互联网连接优点时,标题数字...

    在互联网的早期,关于如何连接没有太多选择,有的只是拨号上网。
    但是宽带的引入开辟了一系列新的可靠连接选项,并且随着用于交付它们的技术的成熟,它们多年来也变得越来越快。
    但是,关于如何衡量互联网连接的性能仍然存在很多困惑。当我们看各种互联网连接的优点时,标题数字通常是可用的每秒兆位或千兆位。虽然我们认为这是连接的速度,但将其描述为带宽更为准确。
    在这里插入图片描述
    带宽是什么意思?
    在继续进行之前,让我们看一下“
    Internet带宽”的含义。带宽是在任何给定时间可以通过连接传输多少信息的度量。将其视为管道,比方宽管道比窄管道允许更多的液体通过。
    互联网也会发生同样的事情,因此20 Mbps的连接允许每秒通过的数据量是5
    Mbps的四倍。这并不意味着连接速度更快,而是连接具有更大的容量,允许在同一时间段内提供更多的信息流。
    为什么这么重要?简单来说,这意味着连接更加可靠,因为它减轻了下载网页的任何延迟。这也使诸如流视频之类的应用程序的性能更加流畅,因为无需等待缓冲区来赶上传入的数据。
    带宽从何而来?
    那么,什么决定了连接上有多少可用带宽?有几件事会影响到这一点。
    首先是电路使用的物理技术。光纤电路将比铜缆提供更大的带宽,因为每秒允许更多的数据通过。
    就您实际可以使用的带宽量而言,重要的是用于传输电路的技术。
    例如,宽带使用到网络主干的共享连接,因此可用的总带宽在使用它的所有人员之间共享。这就是为什么您经常会发现家庭宽带在高峰时间变慢的原因。
    此外,带宽是一条双向路。数据正在发送到互联网以及从互联网返回。因此,带宽在两个方向上都被消耗。通过宽带连接,可用于输入数据的带宽远大于用于出站传输的带宽。
    什么消耗带宽?
    让我们看一下带宽在实用性方面的含义。如果您只是收发电子邮件或浏览网络,则带宽不足不一定会影响您。但是,某些用途需要更大的带宽。
    例如,视频需要大量带宽,因此,进行流媒体播放将比网络购物消耗更多带宽。
    用业务术语来说,如果您正在使用视频会议等应用程序,那么带宽消耗将会很高。我们回到了双向路概念,视频会议和即服务型业务应用程序之类的活动对数据流回Internet的需求更大。因此,您需要确保两个方向都有足够的带宽供应。
    带宽和服务
    如您所料,可用的带宽量将根据您的Internet连接类型而有所不同。普通的光纤宽带连接将为您提供大约20或30
    Mbps,但这仅适用于传入数据,上载或传出带宽要少得多。
    在家庭使用中,您可能没有注意到这种差异,但是,正如我们已经指出的,某些业务应用程序在传出方向上消耗更多带宽。宽带具有异步速度,可能会引起问题。这就是为什么许多企业转而使用企业专线连接的原因。
    企业专线是完全同步的,这意味着双向都有相同数量的可用带宽,因此云应用程序将运行得更加流畅。随着实时云应用程序在企业中变得越来越普遍,组织的带宽需求也增加了,使企业专线选项成为更具吸引力的选择。
    尽管许多企业专线都使用光纤技术,但是在光纤不可用的地区,仍然可以从同步连接中受益。这要归功于以太网第一公里(EFM)技术的使用,该技术将铜电路与信号处理技术结合使用,无需光纤即可提供同步带宽。
    带宽和应用
    那么带宽对业务应用意味着什么?从传统的现场安装服务器模型来看,企业越来越多地迁移到云中。就节省基础结构和软件许可证而言,这具有明显的好处。它也更容易扩展,随着业务的发展具有更大的灵活性。
    为了使企业充分利用云所提供的这些优势,他们需要可以依靠其提供所需带宽的Internet连接。包括ERP和CRM在内的系统是企业的核心,可靠的访问至关重要。
    通过选择企业专线连接,企业不仅可以受益于额外的带宽,而且还可以确保可靠性。
    更重要的是,商业用户受益于将此服务包含在SLA(服务级别协议)中。这不仅可以确保连接提供可靠的连接速度,而且可以将可能出现的任何问题固定在可接受的时间范围内。
    Vecloud是一家面向企业提供云交换网络服务为核心业务的技术创新企业,公司有24*7专业运维团队支撑,可以快速定位客户使用中遇到的问题,最快解决问题。http://www.vecloud.com

    展开全文
  • 引入了以FPGA 为目标虚拟仪器,当其与LiveDesign-enabled 硬 件平台NanoBoard 结合时,用户可以快速、交互地实现和调试基于FPGA 设 计,可以更换各种FPGA 子板,支持更多FPGA 器件。 2.2.2 单片机程序设计开发...
  • 网络流小全

    2019-08-01 15:57:00
    这篇文章介绍了关于网络流一些基本知识点,限于个人水平,本文可能存在谬误,希望发现读者指正。 问题引入 因为一些不可描述的原因,一些水管从$Kirino$家通向了$Ayase$家,现已知每条水管能承受水流量,问...

    简介

    这篇文章介绍了关于网络流的一些基本知识点,限于个人水平,本文可能存在谬误,希望发现的读者指正。

    问题引入

    因为一些不可描述的原因,一些水管从$Kirino$家通向了$Ayase$家,现已知每条水管能承受的水流量,问如果$Kirino$源源不断地从源头注水,$Ayase$这边会得到的最大流量是多少。

    概念

    首先介绍一下必要的概念。

    源点:仅有流量流出的点。

    汇点:仅有流量流入的点。

    容量:一条有向边最多可以承载的流量大小。

    流量:一条有向边已经承载的流量大小。

    增广路:一条从源点到汇点上各条边的剩余流量都大于$0$的路径。

    残量网络:任意时刻,网络中所有节点以及剩余容量大于$0$的边构成的子图。

    性质

    容量限制:一条边的流量不大于容量。

    流量守恒:除了源点和汇点,任何点不存储流,其流入总量等于流出总量。

    反对称性:每条反向边的流量是正向边的流量的相反数。

    对于这张图显然有$1-2-3-4$和$1-2-4,1-3-4$这两种流法,但是后者明显优于前者,建反边就是为了在最大流算法中解决这个问题。当我们走了$1-2-3-4$这条路之后,由于反向边的存在,我们会在下一次计算中走出$1-3-2-4$将这两条路线重叠在一起得到的结果即针对这张图的最优解。接下来我们讨论如何用成体系的方法求解最大流。

    $EK$增广路算法

    $EK$的基本思想就是用$bfs$不断地在网络上寻找增广路,得到该增广路上的最小剩余容量$minf$,答案加上$minf$。

    每次寻找的时候只考虑容量大于当前流量的边,当一条边$i$被考虑时根据反对称性显然有其反边$i\oplus1$满足这个条件,所以寻找过程中会考虑反向边。由于建图过程中边的编号是从$0$开始的,所以第$i$条正向边对应的反向边显然为$i\oplus1$。更新增广路信息的同时需要记录前驱结点的点编号与边编号方便统计当前增广路对答案的贡献。时间复杂度$O(nm^{2})$。

    参考代码:

    #include <bits/stdc++.h>
    #define DBG(x) cerr << #x << " = " << x << endl
    
    using namespace std;
    typedef long long LL;
    
    const int N = 1e5 + 5;
    const int M = 2e5 + 5;
    const int inf = 0x3f3f3f3f;
    
    int head[N], tot;
    bool vis[N];
    
    struct Enode {
        int to, next, flow;
    } edge[M];
    
    struct Pnode {
        int pid, eid;
    } pre[N];
    
    void addedge(int u, int v, int f) {
        edge[tot].to = v;
        edge[tot].flow = f;
        edge[tot].next = head[u];
        head[u] = tot++;
    }
    
    bool bfs(int s, int t) {
        memset(vis, false, sizeof vis);
        queue<int> q;
        q.push(s), vis[s] = 1;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int i = head[x]; i != -1; i = edge[i].next) {
                int v = edge[i].to;
                if (!vis[v] && edge[i].flow) {
                    pre[v].pid = x;
                    pre[v].eid = i;
                    vis[v] = 1;
                    if (v == t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }
    
    LL EK(int s, int t) {
        LL res = 0;
        while (bfs(s, t)) {
            LL minv = inf;
            for (int i = t; i != s; i = pre[i].pid) minv = min(minv, 1LL * edge[pre[i].eid].flow);
            for (int i = t; i != s; i = pre[i].pid) {
                edge[pre[i].eid].flow -= (int)minv;
                edge[pre[i].eid ^ 1].flow += (int)minv;
            }
            res += minv;
        }
        return res;
    }
    
    int main() {
        memset(head, -1, sizeof head);
        int n, m, s, t;
        scanf("%d%d%d%d", &n, &m, &s, &t);
        for (int i = 1, u, v, w; i <= m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, 0);
        }
        printf("%lld\n", EK(s, t));
        return 0;
    }

    $Dinic$算法

    $EK$算法每次只能找出一条增广路,效率还有待提高。我们看看$Dinic$的过程。

    $Dinic$不断重复以下步骤,直到不存在$S$到$T$的增广路:

    $1$.在残量网络上$bfs$构造分层图。

    $2$.在分层图上$dfs$寻找增广路,更新路径信息,答案加上得到的流量。

    $Dinic$有两个优化:

    $1$.当前弧优化,即每次考虑某个点的出边时只考虑那些还没被增广的,因为如果一条边已经被增广过,那么它就没有可能被增广第二次。

    $2$.多路增广,每次找到一条增广路的时候,如果残余流量没有用完怎么办呢?我们可以利用残余部分流量,再找出一条增广路。这样就可以在一次 $dfs$ 中找出多条增广路。

    时间复杂度$O(n^{2}m)$在求解二分图最大匹配时可以达到$O(m\sqrt{n})$。

    $ps:$由于我自己在写题过程中没有因为没加多路增广优化而被卡掉过,所以给出的代码是单路增广的版本,有需要的同学可以自行探索或生产。

    参考代码:

    struct Dinic {
        static const int maxn = 1e6+5;
        static const int maxm = 4e6+5;
    
        struct Edge {
            int u, v, next, flow, cap;
        } edge[maxm];
    
        int head[maxn], level[maxn], cur[maxn], eg;
    
        void addedge(int u, int v, int cap) {
            edge[eg]={u,v,head[u],0,cap},head[u]=eg++;
            edge[eg]={v,u,head[v],0,  0},head[v]=eg++;
        }
    
        void init() {
            eg = 0;
            memset(head, -1, sizeof head);
        }
    
        bool makeLevel(int s, int t, int n) {
            for(int i = 0; i < n; i++) level[i] = 0, cur[i] = head[i];
            queue<int> q; q.push(s);
            level[s] = 1;
            while(!q.empty()) {
                int u = q.front();
                q.pop();
                for(int i = head[u]; ~i; i = edge[i].next) {
                    Edge &e = edge[i];
                    if(e.flow < e.cap && level[e.v] == 0) {
                        level[e.v] = level[u] + 1;
                        if(e.v == t) return 1;
                        q.push(e.v);  
                    }
                }
            }
            return 0;
        }
    
        int findpath(int s, int t, int limit = INT_MAX) {
            if(s == t || limit == 0) return limit;
            for(int i = cur[s]; ~i; i = edge[i].next) {
                cur[edge[i].u] = i;
                Edge &e = edge[i], &rev = edge[i^1];
                if(e.flow < e.cap && level[e.v] == level[s] + 1) {
                    int flow = findpath(e.v, t, min(limit, e.cap - e.flow));
                    if(flow > 0) {
                        e.flow += flow;
                        rev.flow -= flow;
                        return flow;
                    }
                }
            }
            return 0;
        }
    
        int max_flow(int s, int t, int n) {
            int ans = 0;
            while(makeLevel(s, t, n)) {
                int flow;
                while((flow = findpath(s, t)) > 0) ans += flow;
            }
            return ans;
        }
    } di;

    最小割定理

    给定一个网络$G=(V,E)$,源点为$S$,汇点为$T$。若一个边集$E^{'}\subseteq E$被删去后,$S$和$T$不再联通,则称该边集为网络的割。边容量之和的最小的割称为网络的最小割。

    一个网络的最小割等于它的最大流。

    费用流

    问题引入

    由于$Kirino$家的水全排到了$Ayase$家,她为了补偿$Ayase$决定给每条水管都附一个价值$c$,当$f$数量的流量流过时$Kirino$会补偿给$Ayase$的钱为$c*f$。问在流量最大的前提下$Kirino$最少要补偿多少钱。

    基于$EK$的费用流算法

    在最大流的$EK$算法求解最大流的基础上,把用$bfs$求解任意增广路改为用$spfa$求解费用之和最小的增广路即可,相当于把花费$w(x,y)$作为边权,在残存网络上求最短路。需要注意的是,一条反向边$(y, x)$的费用应该设置为$-w(x, y)$。

    容易想到,如果问题要求我们考虑的时最大费用,我们只需在$spfa$的过程中维护最大费用,做法是建边时使用负边权,做完最短路处理之后得到的答案取反。

    代码参考(poj2135):

    int t, pre[maxn], dis[maxn], head[maxn], vis[maxn];
    
    struct node{
        int u, v, c, f, next;
    }e[maxn * 40];
    
    void add1(int u, int v, int c, int f){
        e[t].u = u;
        e[t].v = v;
        e[t].c = c;
        e[t].f = f;
        e[t].next = head[u];
        head[u] = t++;
    }
    
    void add(int u, int v, int c, int f){
        add1(u, v, c, f);
        add1(v, u, -c, 0);
    }
    
    int spfa(int s,int t){
        int i, u, v;
        queue<int> q;
        q.push(s);
        memset(vis, 0, sizeof vis);
        memset(pre, -1, sizeof pre);
        for(int i = s; i <=t ; i++) dis[i] = inf;
        dis[s] = 0;
        while(!q.empty()){
            u = q.front();
            q.pop();
            for(i = head[u]; i != -1; i = e[i].next){
                v = e[i].v;
                if(e[i].f && dis[v] > dis[u] + e[i].c){
                    dis[v] = dis[u] + e[i].c;
                    pre[v] = i;
                    if(!vis[v]){
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
            vis[u] = 0;
        }
        if(dis[t] != inf) return 1;
        return 0;
    }
    
    void solve(int s,int t){
        int ans = 0, i, j, flow = 0, cost = 0;
        while(spfa(s, t)) {
            int minf = inf;
            for(i = pre[t]; i != -1; i = pre[e[i].u]){
                if(e[i].f < minf){
                    minf = e[i].f;
                }
            }
            flow += minf;
            for(i = pre[t]; i != -1; i = pre[e[i].u]){
                j = i ^ 1;
                e[i].f -= minf;
                e[j].f += minf;
            }
            cost += dis[t] * minf;
        }
        printf("%d\n", cost);
    }
    
    void init(){
        t=0;
        memset(head, -1, sizeof head);
    }
    
    int main(){
        int i, u, v, c, n, m;
        scanf("%d%d", &n, &m);
    	init();
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &u, &v, &c);
            add(u, v, c, 1);
            add(v, u, c, 1);
        }
        add(0, 1, 0, 2);
        add(n, n + 1, 0, 2);
        solve(0, n + 1);
        return 0;
    }

    上下界网络流

    无源汇上下界可行流

    一张网络中没有源点和汇点,每条边的流量都被限制在区间$[L_i,R_i]$中,问该网络中达到可行流量下每条边的流量。

    首先每条边必然要满足下界,我们称此时的流量为初始流,显然此时的网络不一定满足流量守恒,为了满足流量守恒,我们建立超级源点$SS$和超级汇点$TT$,为每个可能不满足流量守恒的点提供附加流,显然对于一条流量下限为$L_i$的有向边$(u, v)$,需要为$u$点的附加流减去$L_i$贡献,为$v$加上$L_i$贡献。之后求解最大流,如果最大流满流,即$maxflow=sum$其中$sum$为所有超源所连向的点的附加流,那么这个当前方案是可行的。

    有源汇上下界可行流

    一张网络中有源点和汇点$S,T$,每条边的流量都被限制在区间$[L_i,R_i]$中,问该网络中达到可行流量下每条边的流量以及$S$到$T$的流量。

    将$T$到$S$连一条流量为$inf$的边,此时就转化成了无源汇的情况。

    由于流量守恒对于$S$和$T$依然成立且流入$S$的边仅有$(T,S)$一条,所以根据流量守恒可知边$(T,S)$上的流量即原图上的可行流,根据反向边的性质,这个信息正好被记录在了$(T,S)$的反向边上的流量。

    有源汇上下界最大流

    当条件变成求最大流之后,我们首先考虑求出可行流,如果可行,我们只需要再在残量网络上以初始的源点和汇点$S,T$求一次最大流,答案显然就是可行流的流量加上残量网络上最大流的流量

    有源汇上下界最小流

    先给做法:

    $1$.根据附加流建立加入超源超汇$SS,TT$的图,对$(SS,TT)$做一次最大流。

    $2$.原图连一条$(T,S)$流量为$inf$的边,对$(SS,TT)$做一次最大流。

    $3$.当附加边都满流时,答案为$(T,S)$反向边上的流量。

    粗略证明:不加$(T,S)$时求过一次最大流,此时尽可能使能流的流量流入了不会增大答案的边,此时再连上$(T,S)$后跑最大流,如果附加流满流,那么就可以达到减小最终答案的目的。

    最大权闭合子图

    闭合图是什么?在一个图中,我们选取一些点构成集合,若集合中任意点连接的任意出弧,所指向的终点也在该点集中,则这个集合以及所有这些边构成闭合图。最大权闭合子图即点权之和最大的闭合图。求一张图的最大权闭合子图的步骤如下:

    $1$.建立源点$S$连向正权点,流量为点的权值。建立汇点$T$,令所有负权点连向$T$,流量为点权值的绝对值。点与点之间根据原来的方向顺序连流量为$inf$的边。

    $2$.图$G$的最大权闭合子图$G^{'}$的权值和为所有$G$中的正点权和$sum$减去$S$到$T$的最大流$flow$。

     

     

    转载于:https://www.cnblogs.com/DuskOB/p/11216861.html

    展开全文
  • kobject&kset

    2011-05-12 09:57:00
    简介:关于kobject和...Kobject 是Linux 2.6 引入的设备管理机制,在内核中由struct kobject数据结构 进行描述通过这个数据结构使所有设备在底层都具有统一接口,kobject提供基本对象 理,是构成Linux2...
  • 首先,以一个问题来引入算法: 最大流问题,该问题描述如下: 管道网络中每条边最大通过能力(容量)是有限,实际流量不超过容量。 最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论...
  • 6、下列几种关于进程叙述,( A )最不符合操作系统对进程理解? A.进程是在多程序并行环境中完整程序。 B.进程可以由程序、数据和进程控制块描述。 C.线程是一种特殊进程。 D.进程是程序在一个数据集合上...
  • 软件工程知识点

    2012-12-02 21:34:25
    需求分析要求以用户需求为基本依据,从功能、性能、数据、操作等多个方面,对软件系统给出完整、准确、具体的描述,用于确定软件规格。其结果将以“软件需求规格说明书”的形式提交。 在软件项目进行过程中,需求...
  • 要想学习和掌握它的诸多新特性,只能从Oracle手册入手,而数万页的11g手册不免让人心存畏惧,从中挑出对新特性的描述更需要一双“火眼金睛”。  好消息!在本书第1版出版时隔4年后,Thomas Kyte及时了解了大家的这...
  • C#微软培训教材(高清PDF)

    千次下载 热门讨论 2009-07-30 08:51:17
    14.4 继承中关于属性一些问题.169 14.5 小 结 .172 第四部分 深入了解 C#.174 第十五章 接 口 .174 15.1 组件编程技术 .174 15.2 接 口 定 义 .177 15.3 接口成员 .178 15.4 接口实现 .182 ...
  • C#微软培训资料

    2014-01-22 14:10:17
    14.4 继承中关于属性一些问题.169 14.5 小 结 .172 第四部分 深入了解 C#.174 第十五章 接 口 .174 15.1 组件编程技术 .174 15.2 接 口 定 义 .177 15.3 接口成员 .178 15.4 接口实现 .182 ...
  • 通常在工作中设计师一般是不会什么dp,px通常只会给你一种标准尺寸,可能是720x1280或者直接按照IOS尺寸750x1334来给设计图标注,如果按不同分辨率给不同图片,素材这种方式不太现实,工作量大不说...
  • (3)引入进程意义是描述多道程序设计系统中程序动态执行过程。 2、进程定义及特征 (1)程序和进程区别 (2)进程五个基本特征:动态性、并发性、独立性、制约性、结构性 3、进程...
  • 关于知识图谱概念性介绍就不在此赘述。目前知识图谱在各个领域全面开花,如教育、医疗、司法、金融等。本项目立足医药领域,以垂直型医药网站为数据来源,以疾病为核心,构建起一个包含7类规模为4.4万知识实体,...
  • Python核心编程第二版(中文)

    热门讨论 2015-04-23 16:40:13
    12.5.5 关于__future__ 12.5.6 警告框架 12.5.7 从ZIP文件中导入模块 12.5.8 “新”导入钩子 12.6 模块内建函数 12.6.1 __import__() 12.6.2 globals()和locals() 12.6.3 reload() 12.7 包 ...
  • 深入理解Python中文版高清PDF

    热门讨论 2012-09-04 19:37:04
     1.3.10 高效快速原型开发工具   1.3.11 内存管理器   1.3.12 解释性和(字节)编译性   1.4 下载和安装Python   1.5 运行Python   1.5.1 命令行上交互式解释器   1.5.2 从命令行启动...
  • Python核心编程(中文第二版)

    热门讨论 2009-10-02 12:08:14
     1.3.10 高效快速原型开发工具   1.3.11 内存管理器   1.3.12 解释性和(字节)编译性   1.4 下载和安装Python   1.5 运行Python   1.5.1 命令行上交互式解释器   1.5.2 从命令行启动脚本 ...
  • Python核心编程第二版

    热门讨论 2009-07-30 17:07:20
    很不错python书 第1部分 Python核心  第1章 欢迎来到Python世界   1.1 什么是Python   1.2 起源   1.3 特点   1.3.1 高级   1.3.2 面向对象   1.3.3 可升级   1.3.4 可扩展   1.3.5 可...

空空如也

空空如也

1 2
收藏数 23
精华内容 9
关键字:

关于引入管的描述