二分图最大匹配——匈牙利算法，网络流初步——最大流问题+最小费用最大流+常用建图

今天药忘吃喽~ 2021-11-17 06:36 520阅读 0赞

二分图最大匹配——匈牙利算法

对不起 懒得粘 图太多 但是真的好秀 人家创作的确实好，真丶看一遍就懂了  
作者：Dark\_Scope  
来源：CSDN  
原文：[https://blog.csdn.net/dark\_scope/article/details/8880547][https_blog.csdn.net_dark_scope_article_details_8880547]

板子错误已经改好了，一个是反向边没建好，一个是重边没去，一个是爆int，0.0

写这个博客 主要还不是不喜欢书上的板子，自己理解后按照自己的理解写出最适合自己的板子多好

留个匈牙利算法的板子

hdu 1068

//#include<bits/stdc++.h>
    #include<iostream>
    #include<vector>
    #include<string.h>
    #include<stdio.h>
    using namespace std;
    const int N=3e3+7;
    vector<int>son[N];
    bool vis[N];
    int gx[N],gy[N];
    bool dfs(int x)
    {
        for(int i=0;i<son[x].size();i++)
        {
            if(vis[son[x][i]]) continue;
            vis[son[x][i]]=1;
            if(!gy[son[x][i]]||dfs(gy[son[x][i]]))
            {
                gx[x]=son[x][i];
                gy[son[x][i]]=x;
                return true;
            }
        }
        return false;
    }
    int main()
    {
        //ios::sync_with_stdio(false);
        int zs;
        scanf("%d",&zs);
        while(zs--)
        {
            int n,m; scanf("%d%d",&n,&m);
            for(int i=1;i<=m;i++) gy[i]=0;
            for(int i=1;i<=n;i++)
            {
                gx[i]=0;
                int k1;scanf("%d",&k1);
                son[i].clear();
                while(k1--) {int k2;scanf("%d",&k2);son[i].push_back(k2);}
            }
            int ans=0;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                    vis[j]=0;
                if(dfs(i))
                    ans++;
            }
            if(ans==n)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }

**2.6 网络流建图方式**

**2.6.1 二分图最小点权覆盖**

**含义** ：以最少的点权覆盖所有边的点集

**建图方式** ：

S 连向 X 集合的点，容量为 x 的点权。

Y 集合的点连向 T，容量为 y 的点权。

X 集合的点向 Y 集合的点连上原图边，容量为 INF。

**结果** ：二分图最小点权覆盖=最大流。二分图最大点权独立集=总权值-最大流

**2.6.2 最大权闭合子图**

**含义** ：有向图 G=(E,V)，任取点集中的点 u，点 u 的出边所对应的另一个点也属于点集 V，则为闭合图。

MAX\{所选闭合图点集 V 的点权和\}即为最大权闭合子图

建图方式：

所有点权为正数的点 i，建边 S->i，容量为点权。

所有点权为负数的点 i，建边 i->T，容量为点权绝对值。

连接原图的边，容量为 INF。

割左边表示不要这个正权点，割右边表示选了正权点后带来的负权点的代价

**结果** ：最大权闭合图的权值=正权点之和-最大流

**2.6.3 最大密度子图**

**含义** ：

![20200805135400369.png][]

**建图方式：**

（1）转为最大权闭合子图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Blcm1pX3lheGlsZW5p_size_16_color_FFFFFF_t_70][]

***h(g)=m-最小割，m 为边数，注意(u/v,T)连边时容量是 g 不是-g***

（2）导出子图最小割

二分范围为

1/V~|E| （ |V| 为点数， |E| 为 边 数 ）， 当 二 分 值 为 g 时 。 连 边

(S,u/v,m),(u/v,T,m+2g−du/v),(u,v,1),(v,u,1)。其中 m 为边的数量，du/v 为 u 或 v 的度。每二分一个 g 值

就重新建图再跑最大流并判断 h(g)即可。

时间复杂度为 O(logn\*maxflow(n,n+m))

***h(g)=(n\*m-最小割)/2，n 为点数，m 为边数***

(3)推广（带边权，带点权）

建图时修改对应边的容量即可，如求 SUM(E)/SUM(V)最大，SUM 为求边权和或点权和，那就相当于将第

一种改为 h(g)=max(SUM(E)-g\*SUM(V))，原来的可以看成边权为 1 和点权均为-g\*1 的类型。

**结果** ：找到最小的 g 使 h(g)=0，g 即为答案。

最大流问题就是一张带权有向图，权值代表流量，问起点到终点的最大流

后续会更新啦，目前只是初步学习，就是当个笔记记下来啦

第一份是BFS，就是利用bfs每次找一条最短路，记录路径和路径所有边最小权值，然后所有边都减去该值，直到无通路（其实就是个bfs+记录路径+修改权值）是我太菜了理解了半天，此处留下第一个板子

(这是EK算法)（板子不放了，复杂度不优秀）

还有优化后的dinic算法和弧优化后的。（没有弧优化的没摸出来，摸出来再放，因为学长说网络流的题都是玄学优化的，所以任何一点优化都不要放过的好）

剪枝+弧优化的Dinic算法（终于在同学的帮助下，修好了邻接表，改好了弧优化，改吐了）

#include<bits/stdc++.h>
    using namespace std;
    const double pi = acos(-1.0);
    typedef long long ll;
    const ll N=1e5+7;
    const ll inf=1e18;
    const ll mod=1e9+7;
    struct node
    {
        int to,rev;
        ll w;
    };
    vector<node>son[207];
    ll dep[207],now[207];
    ll n,m,s,t;
    void add(int from,int to,ll cap)
    {
        node temp{to,son[to].size(),cap};
        son[from].push_back(temp);
        node temp2{from,son[from].size()-1,0};
        son[to].push_back(temp2);
    }
    bool bfs()
    {
        for(int i=1;i<=n;i++) dep[i]=-1,now[i]=0;
        dep[s]=0;
        queue<ll>q;
        q.push(s);
        while(q.size())
        {
            ll x=q.front();
            q.pop();
            for(ll i=0;i<son[x].size();i++)
            {
                if(dep[son[x][i].to]==-1&&son[x][i].w)
                {
                    dep[son[x][i].to]=dep[x]+1;
                    q.push(son[x][i].to);
                }
            }
        }
        return dep[t]!=-1;
    }
    ll dfs(ll x,ll exp)
    {
        if(x==t) return exp;
        ll d=0,ans=0;
        for(ll i=now[x];i<son[x].size();i++)
        {
            now[x]=i;
            if(dep[son[x][i].to]==dep[x]+1&&son[x][i].w)
            {
                d=dfs(son[x][i].to,min(exp,son[x][i].w));
                if(!d) continue;
                son[x][i].w-=d;
                son[son[x][i].to][son[x][i].rev].w+=d;
                ans+=d;
                exp-=d;
            }
            if (!exp) break;
        }
        if(!ans) dep[x]=-1;
        return ans;
    }
    int main()
    {
     cin>>n>>m>>s>>t;
       while(m--)
       {
           ll a1,a2,a3;
           cin>>a1>>a2>>a3;
           add(a1,a2,a3);
       }
       ll ans=0;
       while(bfs()) ans+=dfs(s,inf);
       cout<<ans<<endl;
    }

匈牙利算法跑二分图时间复杂度是nm，如果用dinic的话时间是msprt（n）

例题 多校hdu第四场 H go running

题目大意 有n个点表示时间t时x点有人，要用最少的学生覆盖这些点，每个学生只能选一个起点和方向然后以1m/s的时间跑

做一个超级原点和汇点就是二分图求最大流就好

#include<iostream>
    #include<vector>
    #include<string.h>
    #include<cmath>
    #include<queue>
    #include<bits/stdc++.h>
    using namespace std;
    const double pi = acos(-1.0);
    typedef long long ll;
    const ll N=1e5+7;
    const ll inf=1e18;
    const ll mod=1e9+7;
    struct node
    {
        int to,rev;
        ll w;
    };
    struct pppp
    {
        int t,x;
    }a[N];
    vector<node>son[N*2];
    ll dep[N*2],now[N*2];
    ll n,m,s,t;
    void add(int from,int to,ll cap)
    {
        node temp{to,son[to].size(),cap};
        son[from].push_back(temp);
        node temp2{from,son[from].size()-1,0};
        son[to].push_back(temp2);
    }
    bool bfs()
    {
        for(int i=1;i<=n;i++) dep[i]=-1,now[i]=0;
        dep[s]=0;
        queue<ll>q;
        q.push(s);
        while(q.size())
        {
            ll x=q.front();
            q.pop();
            for(ll i=0;i<son[x].size();i++)
            {
                if(dep[son[x][i].to]==-1&&son[x][i].w)
                {
                    dep[son[x][i].to]=dep[x]+1;
                    q.push(son[x][i].to);
                }
            }
        }
        return dep[t]!=-1;
    }
    ll dfs(ll x,ll exp)
    {
        //cout<<x<<endl;
        if(x==t) return exp;
        ll d=0,ans=0;
        for(ll i=now[x];i<son[x].size();i++)
        {
            now[x]=i;
            if(dep[son[x][i].to]==dep[x]+1&&son[x][i].w)
            {
                d=dfs(son[x][i].to,min(exp,son[x][i].w));
                if(!d) continue;
                son[x][i].w-=d;
                son[son[x][i].to][son[x][i].rev].w+=d;
                ans+=d;
                exp-=d;
            }
            if (!exp) break;
        }
        if(!ans) dep[x]=-1;
        return ans;
    }
    int main()
    {
        ios::sync_with_stdio(false);
     int zs;
     cin>>zs;
     while(zs--)
     {
         int nn;
         cin>>nn;
         int t1=0,t2=0;
         unordered_map<int,int>mp1,mp2;
         for(int i=1;i<=nn;i++)
         {
             cin>>a[i].t>>a[i].x;
             if(!mp1[a[i].x-a[i].t]) mp1[a[i].x-a[i].t]=++t1;
             if(!mp2[a[i].x+a[i].t]) mp2[a[i].x+a[i].t]=++t2;
         }
         s=t1+t2+1;
         t=s+1;
         //cout<<t1<<' '<<t2<<' '<<s<<' '<<t<<endl;
         for(int i=1;i<=t;i++) son[i].clear();
         for(int i=1;i<=t1;i++) //{
             add(s,i,1);//cout<<s<<' '<<i<<' '<<'?'<<endl;}
         for(int i=t1+1;i<=t1+t2;i++) //{
                add(i,t,1);//cout<<i<<' '<<t<<' '<<'?'<<endl;}
         for(int i=1;i<=nn;i++)
         {
             add(mp1[a[i].x-a[i].t],mp2[a[i].x+a[i].t]+t1,1);
             //cout<<mp1[a[i].x-a[i].t]<<' '<<mp2[a[i].x+a[i].t]+t1<<' '<<'!'<<endl;
         }
         n=t;
         ll ans=0;
       //cout<<"!!!"<<endl;
       while(bfs()) ans+=dfs(s,inf);
       cout<<ans<<endl;
     }
    
    
    
    
    }
    /*
    8 10 7 8
    7 1 1
    7 2 1
    7 3 1
    1 4 1
    1 6 1
    2 5 1
    3 5 1
    4 8 1
    6 8 1
    5 8 1
    */

最小费用最大流问题

在最大流问题的基础上每条边多了个权值，在完成最大流的基础上使费用最少

跑dijkstra算法每次跑出最短路，然后进行和最大流一样的做法，然后再跑最短路直到跑出最大流

留个板子，下一个是最小割

SPFA+dinic 其实就是把dinic里面的bfs改为spfa 标记进去过的点，和存下最短距离（说的简单，改了半天的板子）

#include<bits/stdc++.h>
    using namespace std;
    const double pi = acos(-1.0);
    typedef long long ll;
    #define FOPEN freopen("C:\\Users\\l\\P3381_8.in","r",stdin)
    const ll N=5e3+7;
    const ll inf=1e18;
    const ll mod=1e9+7;
    struct node
    {
        int to,rev;
        ll w,cost;
    };
    vector<node>son[N];
    ll dep[N],now[N],vis[N];
    ll n,m,s,t;
    ll maxflow,mincost;
    void add(int from,int to,ll w,ll cost)
    {
        node temp{to,son[to].size(),w,cost};
        son[from].push_back(temp);
        node temp2{from,son[from].size()-1,0,-cost};
        son[to].push_back(temp2);
    }
    bool bfs()
    {
        for(int i=1;i<=n;i++) dep[i]=inf,now[i]=0,vis[i]=0;
        dep[s]=0;
        queue<ll>q;
        q.push(s);
        vis[s]=1;
        while(q.size())
        {
            ll x=q.front();
            q.pop();
            vis[x]=0;
            for(ll i=0;i<son[x].size();i++)
            {
                int d=son[x][i].to;
                if(dep[d]>dep[x]+son[x][i].cost&&son[x][i].w)
                {
                    dep[d]=dep[x]+son[x][i].cost;
                    if(!vis[d])q.push(d),vis[d]=1;
                }
            }
        }
        //for(int i=1;i<=n;i++ )cout<<dep[i]<<' ';cout<<endl;
        return dep[t]!=inf;
    }
    ll dfs(ll x,ll exp)
    {
        if(x==t) {maxflow+=exp;return exp;}
        ll d=0,ans=0;
       // cout<<x<<"???"<<endl;
        vis[x]=1;
        for(ll i=now[x];i<son[x].size();i++)
        {
             now[x]=i;
            if(!vis[son[x][i].to]&&dep[son[x][i].to]==dep[x]+son[x][i].cost&&son[x][i].w)
            {
               
                d=dfs(son[x][i].to,min(exp,son[x][i].w));
                if(!d) continue;
                son[x][i].w-=d;
                son[son[x][i].to][son[x][i].rev].w+=d;
                ans+=d;
                mincost+=d*son[x][i].cost;
               
            }
        if (exp==ans) break;
        }
        if(!ans) dep[x]=inf;
        vis[x]=0;
        return ans;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        //FOPEN;
        cin>>n>>m>>s>>t;
     //cout<<n<<m<<s<<t;
       while(m--)
       {
           ll a1,a2,a3,a4;
           cin>>a1>>a2>>a3>>a4;
           add(a1,a2,a3,a4);
       }
       while(bfs()) dfs(s,inf);
       cout<<maxflow<<' '<<mincost<<endl;
    }

EK+Dijkstra（等我摸出来放）

#include<bits/stdc++.h>
    using namespace std;
    const double pi = acos(-1.0);
    typedef long long ll;
    #define FOPEN freopen("C:\\Users\\l\\P3381_8.in","r",stdin)
    #define P pair<ll,ll>
    const ll N=5e3+7;
    const ll inf=1e18;
    const ll mod=1e9+7;
    struct node
    {
        ll to,rev;
        ll w,cost;
    };
    vector<node>son[N];
    ll dep[N];
    ll h[N],pre[N],prei[N];
    ll n,m,s,t;
    ll maxflow,mincost;
    ll f=inf;
    void add(ll from,ll to,ll w,ll cost)
    {
        node temp{to,son[to].size(),w,cost};
        son[from].push_back(temp);
        node temp2{from,son[from].size()-1,0,-cost};
        son[to].push_back(temp2);
    }
    inline void Dijk()
    {
       for(int i=1;i<=n;i++) h[i]=0;
        while(f)
        {
            priority_queue<P,vector<P>,greater<P> >p;
            for(int i=1;i<=n;i++) dep[i]=inf;
            dep[s]=0;
            p.push(P(0,s));
            while(p.size())
            {
                P x=p.top();
                p.pop();
                if(x.second==t) break;
                if(dep[x.second]<x.first) continue;
    
                ll d=x.second;
                //cout<<x.second<<endl;
                for(int i=0;i<son[d].size();i++)
                {
                    node dd=son[d][i];
                    //cout<<dep[dd.to]<<endl;
                    if(dd.w&&dep[dd.to]>dep[d]+dd.cost+h[d]-h[dd.to])
                    {//cout<<dd.to<<'?'<<endl;
                        dep[dd.to]=dep[d]+dd.cost+h[d]-h[dd.to];
                        pre[dd.to]=d;
                        prei[dd.to]=i;
                        p.push(P(dep[dd.to],dd.to));
                    }
                }
            }
            //cout<<"!!!"<<endl;
            if(dep[t]==inf) break;
            for(int i=1;i<=n;i++) h[i]+=dep[i];
            ll flow=inf;
            for(int i=t;i!=s;i=pre[i])
                flow=min(flow,son[pre[i]][prei[i]].w);
            maxflow+=flow;
            mincost+=flow*h[t];
            f-=flow;
            for(int i=t;i!=s;i=pre[i])
            {
               node &dd=son[pre[i]][prei[i]];
               dd.w-=flow;
               son[i][dd.rev].w+=flow;
            }
        }
    }
    int main()
    {
        //ios::sync_with_stdio(false);
        //FOPEN;
        scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
        //cin>>n>>m>>s>>t;
     //cout<<n<<m<<s<<t;
       while(m--)
       {
           ll a1,a2,a3,a4;
           scanf("%lld%lld%lld%lld",&a1,&a2,&a3,&a4);
           add(a1,a2,a3,a4);
       }
      Dijk();
      printf("%lld %lld\n",maxflow,mincost);
       //cout<<maxflow<<' '<<mincost<<endl;
    }

上面这个板子的时间复杂度已经很可以了

dijkstra+EK的我也摸出来了 可是时间复杂度很是不理想（emmm）都差不多一样的为什么比别人的慢这么多

#include<bits/stdc++.h>
    using namespace std;
    const double pi = acos(-1.0);
    typedef long long ll;
    #define FOPEN freopen("C:\\Users\\l\\P3381_8.in","r",stdin)
    #define P pair<ll,ll>
    const ll N=5e3+7;
    const ll inf=1e18;
    const ll mod=1e9+7;
    struct node
    {
        ll to,rev;
        ll w,cost;
    };
    vector<node>son[N];
    ll dep[N];
    ll h[N],pre[N],prei[N];
    ll n,m,s,t;
    ll maxflow,mincost;
    ll f=inf;
    void add(ll from,ll to,ll w,ll cost)
    {
        node temp{to,son[to].size(),w,cost};
        son[from].push_back(temp);
        node temp2{from,son[from].size()-1,0,-cost};
        son[to].push_back(temp2);
    }
    inline void Dijk()
    {
        while(f)
        {
            priority_queue<P,vector<P>,greater<P> >p;
            for(int i=1;i<=n;i++) dep[i]=inf;
            dep[s]=0;
            p.push(P(0,s));
            while(p.size())
            {
                P x=p.top();
                p.pop();
                if(x.second==t) break;
                if(dep[x.second]<x.first) continue;
    
                ll d=x.second;
                //cout<<x.second<<endl;
                for(int i=0;i<son[d].size();i++)
                {
                    node dd=son[d][i];
                    //cout<<dep[dd.to]<<endl;
                    if(dd.w&&dep[dd.to]>dep[d]+dd.cost+h[d]-h[dd.to])
                    {//cout<<dd.to<<'?'<<endl;
                        dep[dd.to]=dep[d]+dd.cost+h[d]-h[dd.to];
                        pre[dd.to]=d;
                        prei[dd.to]=i;
                        p.push(P(dep[dd.to],dd.to));
                    }
                }
            }
            //cout<<"!!!"<<endl;
            if(dep[t]==inf) break;
            for(int i=1;i<=n;i++) h[i]+=dep[i];
            ll flow=inf;
            for(int i=t;i!=s;i=pre[i])
                flow=min(flow,son[pre[i]][prei[i]].w);
            maxflow+=flow;
            mincost+=flow*h[t];
            f-=flow;
            for(int i=t;i!=s;i=pre[i])
            {
               node &dd=son[pre[i]][prei[i]];
               dd.w-=flow;
               son[i][dd.rev].w+=flow;
            }
        }
    }
    int main()
    {
        //ios::sync_with_stdio(false);
        //FOPEN;
        scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
        //cin>>n>>m>>s>>t;
     //cout<<n<<m<<s<<t;
       while(m--)
       {
           ll a1,a2,a3,a4;
           scanf("%lld%lld%lld%lld",&a1,&a2,&a3,&a4);
           add(a1,a2,a3,a4);
       }
      Dijk();
      printf("%lld %lld\n",maxflow,mincost);
       //cout<<maxflow<<' '<<mincost<<endl;
    }

[https_blog.csdn.net_dark_scope_article_details_8880547]: https://blog.csdn.net/dark_scope/article/details/8880547
[20200805135400369.png]: /images/20211116/1e3687c422264c75a127e2251b43ba1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Blcm1pX3lheGlsZW5p_size_16_color_FFFFFF_t_70]: /images/20211116/581ff736d7954ee9a02505c0fc11ce89.png