分类 算法导论 下的文章

无法再多项式时间内解决的问题叫NP完全性问题

问题类型有:

  • P(Polynomial)类问题 可在多项式时间内解决 n^k
  • NP(Nondeterministic Polynomial)类问题 多项式时间内 可以判定所给的解是否正确
  • NPC类问题(NP完全) 可在NP时间内判定 但是P时间内无法解决的问题

线段的性质
（1）叉积
p1×p2=x1y2-x2y1=-p2×p1

（2）确定连续线段是向左转还是向右转
p0p1、p1p2
(p1-p0)×(p2-p0)>0，向左转；
(p1-p0)×(p2-p0)<0，向右转；
(p1-p0)×(p2-p0)=0，p0、p1、p2三点共线。

struct point
{
    int x,y;
};

int direction(point pi,point pj,point pk)
{
    //(pk-pi)×(pj-pi)
    return (pk.x-pi.x)*(pj.y-pi.y)-(pj.x-pi.x)*(pk.y-pi.y);
}

bool onSegment(point pi,point pj,point pk)
{
    if(min(pi.x,pj.x)<=pk.x&&pk.x<=max(pi.x,pj.x)&&min(pi.y,pj.y)<=pk.y&&pk.y<=max(pi.y,pj.y))return true;
    else return false;
}

bool segmentsIntersect(point p1,point p2,point p3,point p4)
{
    int d1=direction(p3,p4,p1);
    int d2=direction(p3,p4,p2);
    int d3=direction(p1,p2,p3);
    int d4=direction(p1,p2,p4);
    if((d1>0&&d2<0)||(d1<0&&d2>0)||(d3>0&&d4<0)||(d3<0&&d4>0))return true;
    else if(d1==0&&onSegment(p3,p4,p1))return true;
    else if(d2==0&&onSegment(p3,p4,p2))return true;
    else if(d3==0&&onSegment(p1,p2,p3))return true;
    else if(d4==0&&onSegment(p1,p2,p4))return true;
    else return false;
}

Graham扫描法 --求凸包
https://www.cnblogs.com/LGJC1314/p/6843641.html

Jarvis 步进法
https://blog.csdn.net/m0_37846371/article/details/76229526

分治法求最近点对
https://blog.csdn.net/ideaqjx/article/details/78903757

在有限的资源和竞争约束下，很多问题都可以表述为最大化或最小化某个目标，如果可以把目标描述为某些变量的一个线性函数，而且可以将资源的约束指定为这些变量的等式或不等式，那么我们得到一个线性规划问题。

线性规划求解方法

  • 椭球算法
  • 内点法
  • 单纯行算法

动态多线程编程模型具有的优点:

  • 串行编程模型的一个简单拓展
  • 从理论上提供了一种基于 工作量 和 持续时间 概念的简洁方式来量化并行性
  • 嵌套并行的多线程算法都比较自然的服从分治模式

对于递归函数可以画出其依赖有向无环图 分析其依赖关系 决定哪些递归函数可以并行

性能度量

  • 工作量
  • 持续时间

如果有一个算法在P个处理器上 则时间复杂度下界是:
一个时间单位可以做P个工作量所以
则在Tp时间内最多能做P*Tp 那么就有PTp>=T1 两边除去P后就得
Tp>=T1/P
Tp>= T无限 因为既然有无限个处理器那肯定也有P个处理器

当T1/Tp = P 时候则说明是线性加速度

并行度=T1/Tp

竞争条件(临界资源)
并行化的关键在于关键路径和并行度

网络流的相关定义：

源点：有n个点，有m条有向边，有一个点很特殊，只出不进，叫做源点。
汇点：另一个点也很特殊，只进不出，叫做汇点。
容量和流量：每条有向边上有两个量，容量和流量，从i到j的容量通常用c[i,j]表示,流量则通常是f[i,j].
通常可以把这些边想象成道路，流量就是这条道路的车流量，容量就是道路可承受的最大的车流量。很显然的，流量<=容量。而对于每个不是源点和汇点的点来说，可以类比的想象成没有存储功能的货物的中转站，所有“进入”他们的流量和等于所有从他本身“出去”的流量。

最大流：把源点比作工厂的话，问题就是求从工厂最大可以发出多少货物，是不至于超过道路的容量限制，也就是，最大流。

求解思路：

首先，假如所有边上的流量都没有超过容量(不大于容量)，那么就把这一组流量，或者说，这个流，称为一个可行流。

一个最简单的例子就是，零流，即所有的流量都是0的流。

(1).我们就从这个零流开始考虑，假如有这么一条路，这条路从源点开始一直一段一段的连到了汇点，并且，这条路上的每一段都满足流量<容量，注意，是严格的<,而不是<=。
(2).那么，我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值delta。我们把这条路上每一段的流量都加上这个delta，一定可以保证这个流依然是可行流，这是显然的。
(3).这样我们就得到了一个更大的流，他的流量是之前的流量+delta，而这条路就叫做增广路。我们不断地从起点开始寻找增广路，每次都对其进行增广，直到源点和汇点不连通，也就是找不到增广路为止。
(4).当找不到增广路的时候，当前的流量就是最大流，这个结论非常重要。
补充：

(1).寻找增广路的时候我们可以简单的从源点开始做BFS，并不断修改这条路上的delta 量，直到找到源点或者找不到增广路。
(2).在程序实现的时候，我们通常只是用一个c 数组来记录容量，而不记录流量，当流量+delta 的时候，我们可以通过容量-delta 来实现，以方便程序的实现。

为什么要增加反向边？

在做增广路时可能会阻塞后面的增广路，或者说，做增广路本来是有个顺序才能找完最大流的。

但我们是任意找的，为了修正，就每次将流量加在了反向弧上，让后面的流能够进行自我调整。
举例：

比如说下面这个网络流模型

我们第一次找到了1-2-3-4这条增广路，这条路上的delta值显然是1。

于是我们修改后得到了下面这个流。（图中的数字是容量）

这时候(1,2)和(3,4)边上的流量都等于容量了，我们再也找不到其他的增广路了，当前的流量是1。

但是，

这个答案明显不是最大流，因为我们可以同时走1-2-4和1-3-4，这样可以得到流量为2的流。

Ford-Fulkerson 方法——最大流问题

算法过程：

开始，对于所有结点 u, v ∈ V， f(u, v) = 0，给出的初始流值为0。

在每一次迭代中，将 G 的流值增加，方法就是在残留网络　Gf 中寻找一条增广路径（一般用 BFS 算法遍历残留网络中各个结点，以此寻找增广路径），然后在增广路径中的每条边都增加等量的流值，这个流值的大小就是增广路径上的最大残余流量。

虽然 Ford-Fulkerson 方法每次迭代都增加流值，但是对于某条特定边来说，其流量可能增加，也可能减小，这是必要的，详情见下文的“反向边”。

重复这一过程，直到残余网络中不再存在增广路径为止。最大流最小切割定理将说明在算法终结时，改算法获得一个最大流。

伪代码：

FORD-FULKERSON（G，t，s）
for each edge(u,v) 属于 E（G）
    do f[u,v]=0
        f[v,u]=0
while there exists a path p from s to t in the residual network Gf // 根据最大流最小切割定理，当不再有增广路径时，流 f 就是最大流
    do cf(p)=min{cf(u,v):(u,v)is in p}  // cf(p)为该路径的残余容量
    for each edge (u,v) in p
        do f[u,v]=f[u,v]+cf(p)  //为该路径中的每条边中注入刚才找到到的残余容量
            f[v,u]=-f[u,v]   //反向边注入反向流量

Edmonds-Karp算法

利用BFS来改善FORDFULKERSON算法的效率 其主要变化就是找到最短的路径(通过BFS即可)然后对此路径进行缩减

package com.company;

import java.util.LinkedList;
import java.util.Queue;
class EdmodKarp{
    int[][] capacity;
    int[] pre;
    int[] flow;
    int maxData=Integer.MAX_VALUE;
    Queue<Integer> queue;
    int n;
    public EdmodKarp(int[][] capacity){
        this.capacity = capacity;
        this.n = capacity.length;
        this.pre = new int[n];
    }
    //广度优先遍历的查找一条src到des的最短路径
    int BFS(int src,int des){
        int i;
        this.queue = new LinkedList();
        flow = new int[n];
        for(i = 0;i<n;i++){
            pre[i] = -1;
        }
        pre[src] = -2;
        flow[src] = maxData;
        queue.add(src);//源节点加入
        while(!queue.isEmpty()){
            int index = queue.poll();
            if(index == des){//如果找到末尾节点 则中断BFS
                break;
            }
            for(i = 0;i<n;i++){
                //从index出发的遍历一遍 且目的地不是出发地 且是一个增光路经(流量>0) 且此i节点没走过 没被赋值
                if(i!=src && capacity[index][i] > 0 && pre[i] == -1){
                    pre[i] = index;
                    flow[i] = Math.min(capacity[index][i],flow[index]);//关键：迭代的找到增量 对此src出发的所有目的地比较节点最小的flow值
                    queue.add(i);
                }
            }
        }
        if(pre[des] == -1){
            return -1;
        }else{
            return flow[des];
        }
    }
    int maxFlow(int src,int des){
        int increasement = 0;
        int sumflow = 0;
        while ((increasement = BFS(src,des)) != -1){ //如果找到了增广路径 和最小权重值
            int k = des;
            while (k != src){
                int last = pre[k];
                capacity[last][k] -= increasement;//对每个前驱进行相减
                capacity[k][last] += increasement;//反方向 相加
                k = last;
            }
            System.out.println("-------改变后---------");
            for(int j=0;j<n;j++) {
                for(int x=0;x<n;x++){
                    System.out.print("---"+capacity[j][x]);
                }
                System.out.println();
            }
            sumflow += increasement;//加上此流量值
        }
        return sumflow;
    }
}
public class Main {

    public static void main(String[] args) {
        int[][] matrix = new int[4][4];
        matrix[0][1] = 4;
        matrix[0][3] = 2;
        matrix[1][2] = 3;
        matrix[1][3] = 2;
        matrix[2][3] = 1;
        EdmodKarp edm=new EdmodKarp(matrix);
        for(int j = 0;j<edm.n;j++){
            for(int k = 0;k<edm.n;k++){
                System.out.print("---"+edm.capacity[j][k]);
            }
            System.out.println();
        }
        int actual = edm.maxFlow(0,3);
        int expected = 5;
        System.out.println("-------最终结果---------");
        for(int j = 0;j<edm.n;j++){
            for(int k = 0;k<edm.n;k++){
                System.out.print("---"+edm.capacity[j][k]);
            }
            System.out.println();
        }
        System.out.println(actual);
    // write your code here
    }
}

最大二分匹配:

最大二分匹配问题在现实生活中比较普遍，常常出现在任务分配上。例如，有5个员工，4个不同的任务，而不同员工能够完成不同或相同的任务。也就是说，有的员工只会做这个任务，有的员工会做那个任务，有的员工会做一些任务。图解如下：左边代表员工，右边代表任务，连线代表有能力完成。

我们的问题是合理安排员工，尽可能地完成最多的任务数。上图中阴影部分为一种最好的分配方式。前一篇文章中，我们介绍了最大流问题，在这里我们可以将最大二分匹配问题转变成最大流问题。具体如下图所示：

其中每条边的最大流量限制为1，因此要求能完成的最大任务数，相当于求转变后的网络的最大流，而最大流问题在前面已经提及。

正题
经过 Frocean 的努力 2018.8.8 通过拼凑和各种理解优化代码 高标推进successfully被弄出来了~~

然而普通模板那题的高标推进比ISAP要慢了5倍 刚好5倍......貌似是常数大的缘故? 不过随机数据ISAP的确快得多 =-=

来随便说说高标推进的概念 (专业的就自己去搜其他的吧......)

我们首先给源点一大堆流 大概有 INF 那么多 通常 INF 定义为 0x7fffffff 等于 2147483647 不过那毒瘤模板里这个还小了......

当然根据理论 要把每个点的流推完 这里可以设他能流到其他点的所有流量 当然会慢点~

最高标号是把点高度用优先队列存起来的 每次取出队列里最高的点 然后这里用手打大根堆 来实现 (死不用STL的Frocean)

定义数组
e[MAXM] 和 st[MAXN] 邻接表存边

h[MAXN] 某节点高度

heap[MAXN] 同字面意思 (大根) 堆

o[MAXN] 判断某节点是否在堆里面 0 即没有 1 即有

gap[MAXN] 网上的dalao们说HLPP可以用gap优化~不过gap这里不是找断层而是找断的高度~

ans[MAXN] 流到某节点时的最大流

步骤

  1. 首先把源点丢进去啦~ 源点高度要最高 俗话说水往低处流 源点高度低怎么流嘛
  2. 然后都丢了点了 肯定要处理对吧

    直接找出来处理~ 利用大根堆 找到heap[1] 就是堆里最大的数 (Tip:堆存的虽然是节点编号 但是要根据节点的深度来排序)

    堆的寻常操作——pop~ (自带音效) 弹出heap[1] 当然别忘了弹出之前把该节点编号存下来 在这次更新要用到

2*.但在更新之前 我们要从ans数组里面看看该点有没有流量呀=w= 没有还流什么呢 当然要初始化源点的流量

    如果没有 就直接 continue 当然这步不要也可以 不过会慢那么一点的说

  1. 开始更新 由邻接表把当前节点能到的点都遍历一遍 但要根据高度和两点间剩余流量来判断(开始流量是满的)

    之前说了水往低处流嘛......于是要判断高度 源点要特判一下 如果能把流推走 就把当前点流量减去相应数值 (不一定是边流量 可能只剩下其中的一部分 因此要 min 判断余流) 当然反向边要相应地加上

  1. 之后别忘了要把推到的点加入堆里 当然堆里如果有了就不用加了 至此 一次循环完毕
  2. 最后还有个判断 如果当前点流量还有剩余 就要把他的高度提高 让他的流能到一些原本到不了的高度的点

    举个例子 如图 此处的 y 点的流 把8单位的流推给z后 还有剩余

因此要把 y 抬高一点 通过 y 到 x 的弧把盈余推给 x (这里是通过反向弧推 你看箭头) 如图


  引用原文 : 一次必须把赢余全部推光.所以y被重标号,当前弧指针从头开始查找,找到(y,x)这条可行弧之后进行推进.实际上是把多推的赢余还给了x.因为h(u)<=h(v)+1的保证,它没有把赢余错推给s

    然而他还是有盈余 =-=

    因此我们再把他抬高 (因为中间断层 这里有个gap优化 直接跳到 s 上 某高度没点就直接跳上去 可加可不加 不加会慢些) 如图

![](https://yoho.ac.cn/usr/uploads/2018/10/3716920576.png)
推到 s 或者 t 还有盈余的话 就可以不推了 t 就不说了 s的话 概念里 s 流量都是 INF 多的流量都剩在这里 因此...... 

就这么愉快地推完了 然后处理到堆里面没数了 (就是没有能增广的流了) 就退出 输出 ans[t] 即可
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5