Week17 总结

新知识

最小树形图

1.基础

这就是有向图的最小生成树。
采用朱刘算法。

1.判断这张图是否联通。
2.找到除根节点点之外，每一个点的所有入边中权值最小的，用数组minin[]记录下这个最小权值，用pre[]记录到达该点的前驱；（若图中存在独立点，最小树形图是不存在的，所以在该步骤结束后，要判断一下）
3.找有向环，并用数组id[]记录节点所属环的编号。
4.找到环后，缩点，并更新权值。
5.以环数为下一次查找的点数，继续执行上述操作，直到没有环or判定出不存在最小树形图为止。

由于每次找到一个环后必定会使用一条边从外部连接压缩后的环，而环内又会断开一条边，所以最后一定有n-1条边。
复杂度是O(nm)。

2.例题 Hdu 4966

题意

总共有n门课，每门课有一个最高等级ai，一开始每门都是等级0。
有m个提升班，每个班级有a l1 b l2 w，表示只有第a门课程在l1及以上时才能上，花费代价w，可以讲第b门课程提升到l2等级。
现在问将所有的课程提升到最高等级需要付出的最小代价，若无法达到则输出-1。

解析

建一个有向图，将每门课分为0—a[i]个点。
但是若等级太高，这可能会炸。
因为最多2m个培训班，所以按照这个来分点。
每门课高等级指向低等级，权值为0。
对于每个培训班由b向a建边，权值为花费。
求最小树形图。

LCA

1.基础

最近公共祖先。
使用倍增/Tarjan/DFS+ST计算。
本来以为好简单的，结果仔细看后才发现自己太naive。
LCA算法详解:wendavidoi的博客 and JVxie的博客

2.例题 Cdoj 92

题意

给你一棵树，然后在树中加入了一条边
然后q次询问，问你加入了这条边之后询问的两个点距离变短了多少。

解析

一种情况变三种，对每个询问跑三次LCA即可。

Tarjan

1.基础

Tarjan算法详解:mengxiang000000的博客
模板

void Tarjan(int u){  
    vis[u]=1;  
    low[u]=dfn[u]=cnt++;  
    for(int i=0;i<mp[u].size();i++){  
        int v=mp[u][i];  
        if(vis[v]==0)Tarjan(v);  
        if(vis[v]==1)low[u]=min(low[u],low[v]);  
    }  
    if(dfn[u]==low[u]){  
        sig++;  
    }
}  

2.例题 Poj 1144

题意

一个电话线公司（简称TLC）正在建立一个新的电话线缆网络。
他们连接了若干个地点分别从1到N编号。没有两个地点有相同的号码。
这些线是双向的并且能使两个地点保持通讯。每个地点都有一个电话交换机。
从每个地点都能通过线缆到达其他任意的地点，然而它并不需要直接连接，它可以通过若干个交换机来到达目的地。
有时候某个地点供电出问题时，交换机就会停止工作。有时它还会导致一些其它的地点不能互相通讯。在这种情况下我们会称这个地点（错误发生的地方）为critical。
现在工作人员想要写一个程序找到所有critical地点的数量。帮帮他们。

解析

割点裸题。

次短路

1.基础

第一种就是在更新的时候同时记录在这个点的最短和次短，最短只能由最短更新，但次短既可能由最短更新，又有可能由次短更新，有点类似于dp。

第二种就是记录每个点到起点和终点的最短距离，然后枚举每一条中间边，查看到两端的距离。

2.例题

不可用

二分图匹配

1.基础

一些定义

匹配边：
这个很好理解，就是被选择的边。

增广路：
一个未匹配边开始，交替匹配—未匹配—匹配。。。到另一条未匹配边结束的路。每次选择一条增广路将其取反可以将匹配数+1。

匹配：
可以做动词，选择一条边将两个点匹配到一起。
也可以作名词，表示一个匹配边集。

最大匹配：
最大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

最小路径覆盖：
在一个有向图当中，选取一些的路径，可以覆盖所有的点，并且每个点只和一条路径相关联。
可以理解为，在每条路径中，从起点走到终点，可以将图中的每一个点都经过一遍而不重复。
建图方式：每个点拆成两个点,a1,a2，如果有一条a-b的有向边，在新图中连一条a1-b2的边。
最小路径覆盖=点数-新图的最大匹配数。
证明：在新图中的每一条匹配可以理解为两个点可以建立一条路径，即路径数-1.

最小点覆盖：
二分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖），叫做最小点覆盖。
最小点覆盖=最大匹配数
证明：反证法，如果在当前匹配中存在一条边没有被覆盖，说明它的两个顶点都没有被选取，即存在一条可行的匹配边，将其匹配即可。在这种情况下，这个匹配也就不是最大匹配，一直进行下去，就会变成最大匹配，同时所有边也会被覆盖。

最优匹配:
最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。一般X和Y集合顶点个数相同，最优匹配也是一个完备匹配，即每个顶点都被匹配。如果个数不相等，可以通过补点加0边实现转化。一般使用KM算法解决该问题。

最大独立集:
最大独立集是指寻找一个点集，使得其中任意两点在图中无对应边。对于一般图来说，最大独立集是一个NP完全问题，对于二分图来说最大独立集=|V|-二分图的最大匹配数。如下图中黑色点即为一个最大独立集：

寻找最大匹配(最小点覆盖)使用匈牙利算法。
匈牙利算法详解:shenben的博客
模板

bool match(int u){  
    for(int i=0;i<g[u].size();i++){  
        int v=g[u][i];  
        if(!vis[v]){  
            vis[v]=true;  
            if(left[v]==-1||match(left[v])){  
                left[v]=u;  
                return true;  
            }  
        }  
    }  
    return false;  
}  
int xiongyali(){  
    int ans=0;  
    for(int i=1;i<=n;i++){  
        memset(vis,false,sizeof vis);  
        if(match(i))ans++; 
    }  
    return ans;  
}  

2.例题

A.春天来了

题意

春天来了！又到了交配的季节。
这里有n个男孩纸和n个女孩纸要组成n对好朋友。
每个人都有一个腼腆值，每当一个男孩纸和一个女孩纸成为好朋友，他们总是会有那么一点点尴尬，那么他们产生的尴尬值就是他们腼腆值的乘积。
为了让孩纸们都能找到好朋友，我们现在要帮助他们进行男女配对，目标是让他们所产生的尴尬值总和最小。
N<=1e5。

解析

并不是二分图匹配，贪心即可。
哈哈哈

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long long a[10001],b[10001];
    while(scanf("%lld",&n)!= EOF){
        for(int i=0;i<n;i++)
            scanf("%lld",&a[i]);
        for(int i=0;i<n;i++)
            scanf("%lld",&b[i]);
        sort(a,a+n);
        sort(b,b+n);
        for(int i=0;i<n/2;i++){
            int temp=b[i];
            b[i]=b[n-1-i];
            b[n-1-i]=temp;
        }
        long long sum=0;
        for(int i=0;i<n;i++)
            sum=sum+a[i]*b[i];
        printf("%lld\n",sum);
    }
    return 0;
}

B.Cdoj 1432

题意

给出一个n*m的矩形仓库，仓库里有的位置已经被占用，剩下的位置可以用来放东西。
问这个仓库还可以放下多少个1*2或者2*1的箱子。

解析

将格子染黑白两色，成为二分图，放箱子即为连一条边。完成。

代码

#include<bits/stdc++.h>  
#define MAXN 10005  
using namespace std;  
char s[105][105];  
vector<int> g[MAXN];  
int from[MAXN],tot;  
bool use[MAXN];int N;  
bool match(int x){  
    for(int i=0;i<g[x].size();i++){  
        if(!use[g[x][i]]){  
            use[g[x][i]]=1;  
            if(from[g[x][i]]==-1||match(from[g[x][i]])){  
                from[g[x][i]]=x;  
                return 1;  
            }  
        }  
    }  
    return 0;  
}  
int hungary(){  
    tot=0;  
    memset(from,-1,sizeof(from));  
    for(int i=0;i<N;i++){  
        memset(use,0,sizeof(use));  
        if(match(i)) tot++;  
    }  
    return tot;  
}  
void init(){  
    for(int i=0;i<N;i++) g[i].clear();  
}  
int main(){  
    int n,m;  
    while(scanf("%d%d",&n,&m)!=EOF){  
        N=n*m;  
        init();  
        for(int i=0;i<n;i++) scanf("%s",s[i]);  
        for(int i=0;i<n;i++){  
            for(int j=0;j<m-1;j++){  
                if(s[i][j]=='.'&&s[i][j+1]=='.'){  
                    int u=i*m+j;int v=u+1;  
                    g[u].push_back(v);  
                    g[v].push_back(u);  
                }  
            }  
        }  
        for(int i=0;i<m;i++){  
            for(int j=0;j<n-1;j++){  
                if(s[j][i]=='.'&&s[j+1][i]=='.'){  
                    int u=j*m+i;int v=(j+1)*m+i;  
                    g[u].push_back(v);  
                    g[v].push_back(u);  
                }  
            }  
        }  
        int ans=hungary();  
        printf("%d\n",ans/2);  
    }  
    return 0;  
}  

网络流

1.基础

再转载于:ZJUT-jiangnan的博客
特别易懂，简单上手。

A.网络流的相关定义：

1. 源点：有n个点，有m条有向边，有一个点很特殊，只出不进，叫做源点。
2. 汇点：另一个点也很特殊，只进不出，叫做汇点。
3. 容量和流量：每条有向边上有两个量，容量和流量，从i到j的容量通常用c[i,j]表示,流量则通常是f[i,j]。

通常可以把这些边想象成道路，流量就是这条道路的车流量，容量就是道路可承受的最大的车流量。很显然的，流量<=容量。而对于每个不是源点和汇点的点来说，可以类比的想象成没有存储功能的货物的中转站，所有“进入”他们的流量和等于所有从他本身“出去”的流量。

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

B.求解思路：

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

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

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

C.补充：

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

D.提问：

为什么要增加反向边？

在做增广路时可能会阻塞后面的增广路，或者说，做增广路本来是有个顺序才能找完最大流的。
但我们是任意找的，为了修正，就每次将流量加在了反向弧上，让后面的流能够进行自我调整。

E.举例：

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

我们第一次找到了1-2-3-4这条增广路，这条路上的delta值显然是1。
于是我们修改后得到了下面这个流。（图中的数字是容量）

这时候(1,2)和(3,4)边上的流量都等于容量了，我们再也找不到其他的增广路了，当前的流量是1。
但是，这个答案明显不是最大流，因为我们可以同时走1-2-4和1-3-4，这样可以得到流量为2的流。

F.最终

那么我们刚刚的算法问题在哪里呢？

问题就在于我们没有给程序一个“后悔”的机会，应该有一个不走(2-3-4)而改走(2-4)的机制。
那么如何解决这个问题呢？
我们利用一个叫做反向边的概念来解决这个问题。即每条边(i,j)都有一条反向边(j,i)，反向边也同样有它的容量。
我们直接来看它是如何解决的：
在第一次找到增广路之后，在把路上每一段的容量减少delta的同时，也把每一段上的反方向的容量增加delta。

    c[x,y]-=delta;
    c[y,x]+=delta;

我们来看刚才的例子，在找到1-2-3-4这条增广路之后，把容量修改成如下：

这时再找增广路的时候，就会找到1-3-2-4这条可增广量，即delta值为1的可增广路。将这条路增广之后，得到了最大流2。

那么，这么做为什么会是对的呢？
事实上，当我们第二次的增广路走3-2这条反向边的时候，就相当于把2-3这条正向边已经是用了的流量给“退”了回去，不走2-3这条路，而改走从2点出发的其他的路也就是2-4。
如果这里没有2-4怎么办？
这时假如没有2-4这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点。
同时本来在3-4上的流量由1-3-4这条路来“接管”。而最终2-3这条路正向流量1，反向流量1，等于没有流。

2.算法

Dinic算法：ouqingliang的博客
EdmondsKarp算法：时间囊的博客

3.例题

网络流例题大全：iwtwiioi的博客

A.Poj 1273

题意

现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的池塘和所能流过的水量,求水渠中所能流过的水的最大容量。

解析

最大流模板题。

B.UVALive 7264

题意

你现在在点一棵技能树（图），你想学会一个技能有三种方式
1，学会它所有的父技能，然后花费ai的代价学会它。
2，花费bi的代价，可以不学某个父技能。
3，花费ci的代价，直接氪掉这个技能。
现在问你，最少花多少钱，能学到某个技能。

解析

最小割。将每个点拆成 i 和 i'，设一个源点与汇点。
1.对于边i--->j，连边i'--->j，容量为对应边的费用。
2.源点到 i 连边，容量为满足条件后购买 i 的费用。
3.对于 i 和 i' 连边，容量为直接购买 i 的费用。
4.对于目标点向汇点连边，容量为inf。
因为图中每个割为一种获得目标技能的方案，所以求最小割即可。

代码

#include<bits/stdc++.h>
#define maxn 1007
using namespace std; 
const int INF=0x3f3f3f3f;  
struct Edge{  
    int from,to,cap,flow;  
    Edge(int a,int b,int c,int d):from(a),to(b),cap(c),flow(d){}
};  
int n,m,goal;  
struct Dinic{  
    int n,m,s,t;  
    vector<Edge> edges;vector<int> G[maxn];  
    bool vis[maxn];  
    int d[maxn];  
    int cur[maxn];  
    void init(int n){  
        this->n=n;  
        for(int i=0;i<=n;i++) G[i].clear();  
       edges.clear();  
   }  
    void addedge(int from,int to,int cap){  
        edges.push_back(Edge(from,to,cap,0));  
        edges.push_back(Edge(to,from,0,0));  
        int m=edges.size();  
        G[from].push_back(m-2);  
        G[to].push_back(m-1);  
    }  
    bool BFS(){  
        memset(vis,0,sizeof(vis));  
        queue<int> Q;  
        Q.push(s);  
        vis[s]=1;  
        d[s]=0;
        while(!Q.empty()){
            int x=Q.front();  
            Q.pop();  
            for(int i=0;i<G[x].size();i++){  
                Edge& e=edges[G[x][i]];  
                if(!vis[e.to]&&e.cap>e.flow){  
                    vis[e.to]=1;  
                    d[e.to]=d[x]+1;  
                    Q.push(e.to);  
                }  
            }  
        }  
        return vis[t];  
    }  
    int DFS(int x,int a){  
        if(x==t||a==0) return a;
        int flow=0,f;  
        for(int& i=cur[x];i<G[x].size();i++){  
            Edge& e=edges[G[x][i]];
            if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){  
                e.flow+=f;  
                edges[G[x][i]^1].flow-=f;  
                flow+=f;  
                a-=f;  
                if(a==0) break;  
            }  
        }  
        return flow;  
    }  
    int Maxflow(int s,int t){  
        this->s=s;  
        this->t=t;  
        int flow=0;  
        while(BFS()){  
            memset(cur,0,sizeof(cur));  
            flow+=DFS(s,INF);  
        }  
        return flow;  
    }  
};  
Dinic g;  
int main(){
    int t;  
    scanf("%d",&t);  
    while(t--){  
        scanf("%d%d%d",&n,&m,&goal);  
        g.init(2*n+1);  
        for(int i=0;i<m;i++){  
            int x,y,c;  
            scanf("%d%d%d",&x,&y,&c);  
            g.addedge(x+n,y,c);  
        }  
        for(int i=1;i<=n;i++){  
            int x;  
            scanf("%d",&x);  
            g.addedge(0,i,x);  
        }  
        for(int i=1; i<=n; i++){  
            int x;  
            scanf("%d",&x);  
            g.addedge(i,i+n,x);  
        }  
        g.addedge(goal,2*n+1,INF);  
        int ans=g.Maxflow(0,2*n+1);  
        printf("%d\n",ans);  
    }  
    return 0;  
}  

C.Hdu 3987

题意

就是给你一张图，让你求最小割，并且最小割的割边数量需要最小。
就是不仅要是最小割，割的边还得少

解析

这个实际上就是给一条边的边权赋予了两个含义。
一个是边的权值，一个是边的数量。
并且权值处理是优先的。
那么我们可以给权值乘一个值，来让他远远大于我们选择的边数，然后每条边加上1，就代表我们额外选择了一条边。
最后结果对我们乘的值取模即可。
可以思考一下这里这个通过乘一个数来完成优先级选择的过程。

费用流

1.基础

和最大流基本类似，不过引入了费用这个概念。
每条边产生的费用就是这条边的边权*这条边的流量。
大多数情况下是求最小费用最大流，就是先要满足满流，再满足费用小。
有的时候也是最大流最小费用，就是引入一个利益概念，你要利益最大。

2.算法

Ek算法变种

还记得EK算法嘛。。每次使用bfs进行增广
那么我们这里引入了费用，也就是距离的概念，就把EK算法的bfs换成spfa，遍历改成最短路，进行增广即可。
一直寻找当前能找到的最短路，进行增广，最后直到流量最大。
反向边怎么建？
费用取反即可。

Zkw费用流：jzq233jzq的博客

3.例题

A.Hdu 6118

题意

度度熊参与了喵哈哈村的商业大会，但是这次商业大会遇到了一个难题：
喵哈哈村以及周围的村庄可以看做是一共由 n 个片区， m 条公路组成的地区。
由于生产能力的区别，第 i 个片区能够花费 a[i] 元生产 1 个商品，但是最多生产 b[i] 个。
同样的，由于每个片区的购买能力的区别，第 i 个片区也能够以 c[i] 的价格出售最多 d[i] 个物品。
由于这些因素，度度熊觉得只有合理的调动物品，才能获得最大的利益。
据测算，每一个商品运输 1 公里，将会花费 1 元。
那么喵哈哈村最多能够实现多少盈利呢？

解析

最小费用最大流，首先建立超级源点 s ，与超级汇点 t 。
因为生产一个商品需要花费 a[i] 元，且上限为 b[i] ，所以我们从 s 向这些点之间连一条容量为 b[i] ，费用为 -a[i] 的边。
同样的道理，出售一个商品可以赚到 c[i] 元，最多出售 d[i] 个，于是我们从这些点向 t 连一条容量为 d[i] ，费用为 c[i] 的边。
最后所有的公路也是花费，从 u 到 v 连接一条双向边，容量为 INF ，费用为 -k ，然后跑一边模板即可。
注意：图中存在自环，当我们得到两点路径长度小于 0 时应终止计算。

B.Hdu 4494

题意

给你一些任务,每个任务有自己的开始时间和需要多久能干完,还有就是每个任务都需要一些人,这些人有最多五个种类,各种类之间的人不能相互替换,但是某些工人干完这个活后如果可以在另一个任务还没开始的时候赶过去,也可以帮那个任务干活,干的是自己的属性的活,还有一个关键的点就是所有的任务必须人齐了才能干,最后问你最少要多少个人能把活干完。

解析

先把每种工人分开来单独考虑，因为他们互不影响。每个点拆成两个点，一个用于自己消耗，一个用于给予他人。
每个消耗点先向汇点给一条边表示要完成这个任务的人数，帮助跑满流。费用0。
然后每个消耗点从源点连一条人数边费用1的边，这是真正从源点拿来的人。
然后每个人工作完以后产品流出去，人却可以继续工作，所以给予点会给出和该任务人数等量的人出去。这些相当于免费拿来了等量新人，从源点连费用0边。这些人可以发配到别的任务消耗点上消耗掉，连费用0无上限边。

最大权闭合图

1.基础

在一个图中，我们选取一些点构成集合，记为V，且集合中的出边(即集合中的点的向外连出的弧)，所指向的终点(弧头)也在V中，则我们称V为闭合图。最大权闭合图即在所有闭合图中，集合中点的权值之和最大的V，我们称V为最大权闭合图。

这种问题是转化为最小割进行操作的。
源点向所有权值为正的点连一条流量为权值的边，然后每个负权点向汇点连一条流量为权值绝对值的边，图中原先含有的边流量变为正无穷。
最后答案就是所有正权点的权值减去新图的最小割。

证明这个问题之前先证明两个定理。
一个是简单割，简单割就是这个割的所有边都和s以及t有关联。
在这个图中的最小割=简单割。
因为除了和st连的边剩下的边都是正无穷的了，最小割不会割正无穷的边。
第二就是，每个简单割都会和一个闭合子图有联系。
这个有一种比较通俗的解释方式，就是在产生的新图当中，每个源点连出边割开，表示在原图中的这个点不选，而每个汇点连向边割开，就表示这个点被选上了。所以每一个简单割就是一个闭合子图。

实际上每条路径能产生的价值就是你要么选择这条路径，那么就可以获得这条路径上的正权值以及负权值。要么就是不要这条路径，产生的结果是0.
而我们是用所有正权值之和减去这个答案，所以你每个路径如果选择就是减去连向汇点的边的权值，如果不选择就是减去源点连出的权值，意味抛弃这条边。

论文：《最小割模型在信息学竞赛中的应用》

2.例题

A.Hdu 5855

题意

M个商店，N个工厂，每个商店获利的条件是建设了指定的k个工厂。求总获利不小于L，工厂建设的时间最大值最小是多少。

解析

工厂到汇点建一条边pay[i]，源点到商店建一条边pro[i]，商店到需要的工厂建一条边INF，商店的总收益-最小割就是答案。

B.Hihocoder 1398

题意

周末，小Hi和小Ho所在的班级决定举行一些班级建设活动。
根据周内的调查结果，小Hi和小Ho一共列出了N项不同的活动(编号1..N)，第i项活动能够产生a[i]的活跃值。
班级一共有M名学生(编号1..M)，邀请编号为i的同学来参加班级建设活动需要消耗b[i]的活跃值。
每项活动都需要某些学生在场才能够进行，若其中有任意一个学生没有被邀请，这项活动就没有办法进行。
班级建设的活跃值是活动产生的总活跃值减去邀请学生所花费的活跃值。
小Hi和小Ho需要选择进行哪些活动，来保证班级建设的活跃值尽可能大。

解析

学生是产生负值，活动产生正值，比上一题还水。

二分图带权匹配与KM算法

不可用

带上下界限的网络流

不可用

结束

鸣谢：各位神犇的博客、老师的PPT。

其它

若文章有遗漏、错误，敬请指正。

无法正常阅读本文？（几率很小）
请移步Week17总结备份