二分图

二分图

作为网络流的“前置知识”，先学习了二分图

算法列表如下：

1.匈牙利算法

2.km算法

3.Gale-shapley (稳定婚姻)

匈牙利算法

三个算法中最简单的一个。用于解决的问题为：找到二分图的一个最大匹配（顾名思义，即连了最多的情况）

为解决这个问题，引用了如下定义：

1.匹配边： 即当前边出现在当前已匹配的边集中

2.非匹配便： 即不是匹配边喽

3.匹配点： 即当前点出现在当前已匹配的点集中

4.非匹配点： 即不是匹配点喽

5.最大匹配： 就是一个图符合“匹配”条件下，安排合理时，可以安排下的最大边数

6.完美匹配： 即所有点都是匹配点

好，我们休息一会儿，接着胡诌下去

7.交替路： 从一个非匹配点开始，沿着非匹配边、匹配边、非匹配边...的顺序走下去的路径

8.增广路： 从一个非匹配点开始，走交替路，停止在一个非匹配点上

好了，到此为止，所有的定义都编完了，其实故名思意就ok了。

然后要解决问题嘛

注意到增广路的一条性质：总是走交替路，直到非匹配点。也就是说假如走了n条匹配边，必定会走n+1条非匹配边！而匹配边与非匹配边同样的满足匹配的性质。就是说假如把增广路中的所有匹配边“替换”为非匹配边，就可以使匹配边的数目++，即答案更优！

那么思路就出来了，从二分图每一部分的非匹配边出发，尝试为每一个非匹配点寻找一个增广路，每找到一条，就可以ans++

那么就把样例偷下来(^_)：

#include<bits/stdc++.h>
#define MAXN 9999
using namespace std;
int nx,ny;//nx表示二分图左边顶点的个数，ny表示二分图右边顶点的个数
int m;//m代表边的条数
int cx[MAXN],cy[MAXN];//如果有cx[i]=j，则必有cy[j]=i，说明i点和j点能够匹配
int x,y;//x点到y点有边
int e[MAXN][MAXN];//邻接矩阵
int visited[MAXN];//标记数组，标记的永远是二分图右边的顶点
int ret;//最后结果
int point(int u)//这个函数的作用是寻找增广路和更新cx，xy数组，如果找到了增广路，函数返回1，找不到，函数返回0。
{
    for(int v=1;v<=ny;v++)//依次遍历右边的所有顶点
    {
        if(e[u][v]&&!visited[v])//条件一：左边的u顶点和右边的v顶点有连通边，条件二：右边的v顶点在没有被访问过，这两个条件必须同时满足
        {
            visited[v]=1;//将v顶点标记为访问过的
            if(cy[v]==-1||point(cy[v]))//条件一：右边的v顶点没有左边对应的匹配的点，条件二：以v顶点在左边的匹配点为起点能够找到一条增广路（如果能够到达条件二，说明v顶点在左边一定有对应的匹配点）。
            {
                cx[u]=v;//更新cx，cy数组
                cy[v]=u;
                return 1;
            }
        }
    }
    return 0;//如果程序到达了这里，说明对右边所有的顶点都访问完了，没有满足条件的。
}
int main()
{
    while (cin>>m>>nx>>ny)
    {
        memset(cx,-1,sizeof(cx));//初始化cx，cy数组的值为-1
        memset(cy,-1,sizeof(cy));
        memset(e,0,sizeof(e));//初始化邻接矩阵
        ret=0;
        while (m--)//输入边的信息和更新邻接矩阵
        {
            cin>>x>>y;
            e[x][y]=1;
        }
        for(int i=1;i<=nx;i++)//对二分图左边的所有顶点进行遍历
        {
            if(cx[i]==-1)//如果左边的i顶点还没有匹配的点，就对i顶点进行匹配
            {
                memset(visited,0,sizeof(visited));//每次进行point时，都要对visited数组进行初始化
                ret+=point(i);//point函数传入的参数永远是二分图左边的点
            }
        }
        cout<<ret<<endl;
    }

一个值得注意的是，在每一轮匹配中，对面的点只有一次被访问到的机会。这个貌似是符合什么二分图树的，不会影响到答案。但是原理不造...

km算法

km算法指的是假如二分图中的边多了一个边权，求解变成了要求最大比边权和。这个模型使用类似“分配工作”，“cp满意度”之类的问题...

话说这一部分的例题完全不顾忌单身狗的心态

为了方便说，把二分图一侧记为u，另一侧记为v，其实早该这么分了，只是忘了(o゜▽゜)o☆

km算法其实是建立在匈牙利算法的基础上的。具体为：一个u找到v，那个v应为已经找到了一个u，故那个v的匹配对象u应该再新换一个v...听起来就非常匈牙利。事实就是。这里的匈牙利依旧用于找增广路。

很明显，当两个u的最佳v都是同一个v时，总会有u无法被满足，即ans!=最佳对象的权值之和。为每一个u和v都建一个期望值：u的期望值为所有于u相连的边的权值中的最大值，即u最开始希望取到最好的那一个，但是v的ex值init=0，即萝卜白菜不挑剔。

找对象遵循一个重要的原则：“u和v的期望值之和必定等于边权”

开始km()，会发现到了某一阶段，导致不再存在符合该原则的边，无法继续进行下去。怎么办？就需要调整某些点的期望值。怎么调整？好问题。

考虑当前的状况，已经匹配了一些边，想多匹配一条边，那么就需要以前匹配过的点做让步。

设k为u中匹配过的点中可以匹配到出当前已匹配的点外，其余的所需要降低期望值的最小值。（最小值是为了保证答案的正确性）

那么令所以当前匹配中经过点，u的ex+=k，v的ex-=k。这么做保证了以前可以匹配的边依旧是合法的，同时又存在了更多的合法但为采纳的新边，可能性便得到了扩展。

如此一来，为每一个u点重复如下操作：

1.判增广路，若存在break

2.否则降低ex，增加更多的可能，返回1

最后将u的所有ex加起来即为ans

推荐博客：

https://www.cnblogs.com/wenruo/p/5264235.html

https://www.cnblogs.com/logosG/p/logos.html?tdsourcetag=s_pcqq_aiomsg

代码：

#include<algorithm>
#include<iostream>
#include<limits.h>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#define INT 9654234
#define mod 1000000007
typedef long long ll;
using namespace std;
const int MAXN = 305;
int N;
int ex_gir[MAXN];//每个妹子的期望值
int ex_boy[MAXN];//每个男生的期望值
bool vis_gir[MAXN];//记录每一轮匹配过的女生
bool vis_boy[MAXN];//记录每一轮匹配过的男生    每进行新的一轮，都要重新初始化这两个数组
int match[MAXN];//match[i]代表和i男生匹配的女生的编号
int slack[MAXN];//slack[i]代表i男生如果要获得女生的芳心，至少需要增加的期待值
int love[MAXN][MAXN];//记录每个妹子和男生的好感度
bool dfs(int gir)//dfs函数求的是编号为gir的女孩能否匹配到男生，如果能，返回true，否则，返回false
{
    vis_gir[gir]=true;//标记
    for(int i=1;i<=N;i++)
    {
        if(vis_boy[i])//我们规定每次匹配对于某个男生只访问一遍，如果先前访问过了，就换个男生
            continue ;
        int gap=ex_gir[gir]+ex_boy[i]-love[gir][i];
        if(gap==0)//如果这个条件满足，说明编号为gir女孩和编号为i的男孩可能能够匹配成功
        {
            vis_boy[i]=true;//标记
            if(match[i]==-1||dfs(match[i]))//如果这两个条件满足其中一个，说明编号为gir女孩和编号为i的男孩匹配成功
            {
                match[i]=gir;
                return true;
            }
        }
        else
            slack[i]=min(slack[i],gap);//如果gap不等于0，说明当前状态编号为gir女孩和编号为i的男孩不可能匹配成功，更新slack[i]。
    }
    return false;
}
int km()
{
    memset(match,-1,sizeof(match));
    memset(ex_boy,0,sizeof(ex_boy));
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            ex_gir[i]=max(love[i][j],ex_gir[i]);//初始化ex_gir数组
    for(int i=1;i<=N;i++)
    {
        fill(slack,slack+N+1,INT);
        while (1)//这个while循环结束的条件是直到让编号为i的女生找到可以匹配的男生后
        {
            memset(vis_gir,false,sizeof(vis_gir));
            memset(vis_boy,false,sizeof(vis_gir));
            if(dfs(i))//如果这个条件满足，说明编号为i的女生找到了匹配的男生，换下一个女生,如果这个条件不满足，说明这个女生没有匹配到男生，让这个女生降低期望值后继续匹配
                break ;
            int t=INT;
            for(int j=1;j<=N;j++)//寻找在这一轮匹配中没有匹配到的男生如果要获得女生芳心所需要增加的期待值的最小值
                if(!vis_boy[j])
                    t=min(t,slack[j]);
            for(int i=1;i<=N;i++)//让在这一轮匹配中匹配过的女生的期待值减小，匹配过的男生的期待值增加
            {
                if(vis_gir[i])
                    ex_gir[i]-=t;
                if(vis_boy[i])
                    ex_boy[i]+=t;
                else
                    slack[i]-=t;//因为有些女生的期待值减小了，所以这一轮没有被匹配过的男生得到女生的芳心所需要增加的期待值就变小了，所以slack数组中的相应的值要变小
            }
        }
    }
    int res=0;//计算好感和
    for(int i=1;i<=N;i++)
        res+=love[match[i]][i];
    return res;
}
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin>>love[i][j];
    cout<<km()<<endl;
}

Gale-shapley

有N男N女，每个人都按照他对异性的喜欢程度排名。现在需要写出一个算法安排这N个男的、N个女的结婚，要求两个人的婚姻应该是稳定的。

何为稳定？

有两对夫妻M1 F2，M2 F1。M1心目中更喜欢F1，但是他和F2结婚了，M2心目中更喜欢F2，但是命运却让他和F1结婚了，显然这样的婚姻是不稳定的，随时都可能发生M1和F1私奔或者M2和F2私奔的情况。所以在做出匹配选择的时候（也就是结婚的时候），我们需要做出稳定的选择，以防这种情况的发生。

算法中采用了男生主动追求女孩的形式。

算法步骤描述：

第一轮，每个男人都选择自己名单上排在首位的女人，并向她表白。这种时候会出现两种情况：（1）该女士还没有被男生追求过，则该女士接受该男生的请求。（2）若该女生已经接受过其他男生的追求，那么该女生会将该男士与她的现任男友进行比较，若更喜欢她的男友，那么拒绝这个人的追求，否则，抛弃其男友（囧）……

第一轮结束后，有些男人已经有女朋友了，有些男人仍然是单身。

在第二轮追女行动中，每个单身男都从所有还没拒绝过他的女孩中选出自己最中意的那一个，并向她表白，不管她现在是否是单身。这种时候还是会遇到上面所说的两种情况，还是同样的解决方案。直到所有人都不在是单身。

算法非常质朴，简单的模拟便可以实现，代码懒得不贴了..

最后总结

二分图中的三个算法都是明白算法，但没有阐明原理的。但好在算法足够清晰，所以就罢了吧...

还有，感觉二分图算法的复杂度普遍好高好高好高！估计做题的时候应该能通过数据明显区分吧

至此，打字累死了