学了二分图，整个人都不好了，赶紧趁热打铁敲个日志巩固下记忆。

二分图，就是将一个图分为2个点集后，每个点集内部任意两点之间不存在边，即每一条边都连接在不同点集中的两个点。

匹配，是一个边集，且任两条边不相邻，即不存在公共点。

相关算法：

    ①最大匹配问题：

        顾名思义，就是找到给定图中边数最多的匹配。解决这一问题，可以采用网络流进行构图，或者利用匈牙利算法构造匈牙利树，这

    里讨论后一种做法。

        显然，空集也是一种匹配，那么我们可以从空集开始，对当前解一步步进行优化，使在满足匹配的前提下，边集尽可能大，或说进行

    增广。对于当前匹配，我们可以从一个未覆盖点开始，从这个点的连边进行搜索，直到找到另一个未覆盖点。因起点和终点都是未覆盖

    点，所以起始边和终边都是未匹配边，中继点一定是已覆盖点，然后易得知此路径上的边一定是已匹配边和未匹配边交错。要让边集仍

    满足匹配，且将起点和终点都被覆盖，只需要把路径上各边都取反，即舍去所有已匹配边，取用所有未匹配边，这时我们便可得到一个

    更优解。

        考虑对此算法进行优化，假如已某一点为起点无法找到增广路，那么在以后的查找中也不需要考虑该点的增广路，证明的话自己画个

    图大概就明白了。

 ②二分图最大点独立集：

    独立集：一个点集，满足其中所以点之间都没有边相邻。

    可以证明，二分图最大点独立集点数=总点数-最大匹配边数。证明如下：

        对于任意未被匹配的点，假如它们之间有连线，必定存在更优匹配，矛盾。对于已匹配点，由于减去的是边数，我们可以考虑只留下

    每条边的其中一个端点，这是可以保证独立。对于一个组未匹配点和已匹配点，如果他们之间存在连线，我们可以把这个已匹配点转为

    其匹配点，若该匹配点仍与未匹配点相连，易得到一个更优的匹配解，矛盾，得证。

    ③最优匹配问题：

        原最大匹配问题的变种，所有边都有一个权值，求边权和最大的匹配解。这时需要用到KM算法（全称是Kuhn-Munkras）。

        我们可以设二分图中两个点集中的每个点各有一个标记A[i]和B[i]，在整个过程中保证对于边w(i,j)满足A[i]+B[i]≥w(i,j)。假如把所有

    A[i]+B[i]=w(i,j)的边组合为一个导出子图，假如这个子图存在完美匹配（即点完全覆盖），那么这个完美匹配一定是原图的最优匹配，但

    假如不存在完美匹配，我们需要改变点标记，使更多边进入子图，慢慢使子图存在完美匹配。我们可以设A[i]=maximine(w(i,j)) j∈V，

    B[i]=0。当我们找不到完美匹配时，便得到一棵交错树，可以取一个值lack，将A[i]减去lack,B[i]加上lack。此时，对于本已在树中的边或

    两顶点都不在树上时，A[i]+B[i]值不变，仍在树中或仍不在树中。对于有一个点在树上，其A[i]+B[i]值增大或减小，那么该边就有可能进

    入相等子图，于是子图得到扩大。这个lack就取能让新边进入的最小值就行。不断进行该操作，最后可得到一个完美匹配。

updata at 2017.4.13

　　补了一波最大权匹配的KM算法，这里有个模版：

#include
      
       #include
       
        #include
        
         #define MN 1001#define ll long long#define INF 1e7using namespace std;int read_p,read_ca,read_f;inline int read(){    read_p=0;read_ca=getchar();read_f=1;    while(read_ca<'0'||read_ca>'9') read_f=read_ca=='-'?-1:read_f,read_ca=getchar();    while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();    return read_p*read_f;}int m,n,nl,nr,dis[MN][MN],A[MN],B[MN],la,li[MN],sla[MN],t=0;ll mmh;bool va[MN],vb[MN];char s[MN];inline int abs(int x){
    return x<0?-x:x;}inline int max(int a,int b){
    return a>b?a:b;}inline int min(int a,int b){
    return a
        
       
      

#include
      
       #include
       
        #include
        
         #include
         
          #define MN 401#define ll long longusing namespace std;ll read_p,read_ca,read_f;inline ll read(){    read_p=0;read_ca=getchar();read_f=1;    while(read_ca<'0'||read_ca>'9') read_f=read_ca=='-'?-1:read_f,read_ca=getchar();    while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();    return read_p*read_f;}queue
          
            q;ll n,nl,m,li[MN],x,y,num=0,to[MN],pre[MN];bool va[MN],vb[MN];ll A[MN],B[MN],sla[MN],z,dis[MN][MN],mmh=0;inline ll max(ll a,ll b){
     return a>b?a:b;}inline ll min(ll a,ll b){
     return a
           
            sla[i]) continue; pre[i]=k; if (!t) if (vb[i]=1,!li[i]){Connect(i);return;}else va[li[i]]=1,q.push(li[i]);else sla[i]=t; } } ll t=1e18; for (ll i=1;i<=n;i++) if (!vb[i]) t=min(t,sla[i]); for (ll i=1;i<=n;i++){ if (va[i]) A[i]-=t; if (vb[i]) B[i]+=t;else sla[i]-=t; } for (ll i=1;i<=n;i++) if (!vb[i]&&!sla[i]) if (vb[i]=1,!li[i]){Connect(i);return;}else va[li[i]]=1,q.push(li[i]); }}int main(){ register ll i,j;nl=read(); n=max(nl,read());m=read(); while (m--) x=read(),y=read(),z=read(),dis[x][y]=max(dis[x][y],z),A[x]=max(A[x],z); for (i=1;i<=n;i++) memset(va,0,sizeof(va)),memset(vb,0,sizeof(vb)),memset(sla,63,sizeof(sla)),bfs(i); for (i=1;i<=n;i++) mmh+=A[i]+B[i]; printf("%lld\n",mmh); for (i=1;i<=nl;i++) if (!dis[i][to[i]]) printf("0 ");else printf("%d ",to[i]);}
           
          
         
        
       
      

听说bfs会比dfs快，但是我的bfs还是在uoj上T掉了。