匈牙利算法

Bfs判断是否为二分图

二分图建模多种算法

先来一发定理(再也不用担心我搞混最小路径覆盖点和最小路径覆盖边,做题也要注意问的是点还是边!!):

柯尼希定理:二分图最小点覆盖的点数=最大匹配数。
最小路径覆盖的边数=顶点数n-最大匹配数

最大独立集=最小路径覆盖=顶点数n-最大匹配数

二分图最小顶点覆盖=双向二分图最大匹配/2

匈牙利算法:

csdn上看到一个海贼王找对象的例子,太好理解了,,,一辈子都忘不了。。。不解释了。。。

模板:

二分图最大匹配
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int maxn=100+10;

int n,m;
int g[maxn][maxn];
int linker[maxn];
int vis[maxn];

bool dfs(int u)
{
    for (int v=0 ;v<m ;v++)
    {
        if (g[u][v] && !vis[v])
        {
            vis[v]=1;
            if (linker[v]==-1 || dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int ret=0;
    memset(linker,-1,sizeof(linker));
    for (int u=0 ;u<n ;u++)
    {
        memset(vis,0,sizeof(vis));
        if (dfs(u)) ret ++ ;
    }
    return ret;
}

int main()
{
    return 0;
}

hdu2819(匈牙利算法模板 + 建图思维)

思路:如果两行或者两列交换后不能得到对角线为1的话,那么对应的交换两列 + 一行一列 或 两行 + 一行一列 也不可能

match[j] 表示第 j 行的1在第几列,枚举行数i

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#define INF 99999999;
using namespace std;

int n;
int a[110][110];
int match[110];
int vis[110];

int dfs(int u)
{
    for (int v = 1; v <= n; v++)
    {
        if (a[u][v] && !vis[v])
        {
            vis[v] = 1;
            if (match[v] == -1 || dfs(match[v]))
            {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int hungarian()
{
    int ans = 0;
    memset(match, -1, sizeof(match));

    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(dfs(i))
        ans++;
    }
    return ans;
}

int main()
{
    while (~scanf("%d", &n))
    {
        memset(a, 0, sizeof(a));

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &a[i][j]);

        if (hungarian() != n)
            printf("-1\n");
        else
        {
            int num = 0;
            int L[110], R[110];
            for (int i = 1; i <= n; i++)
            {
                if (i != match[i])
                {
                    for (int j = 1; j <= n; j++)
                    {
                        if (i == match[j])
                        {
                            L[num] = i;
                            R[num] = j;
                            num++;
                            swap(match[i], match[j]);   //交换列 
                            break;
                        }
                    }
                }
            }

            printf("%d\n", num);
            for (int i = 0; i < num; i++)
                printf("C %d %d\n", L[i], R[i]);
        }
    }
    return 0;
}
View Code

hdu2444(匈牙利最小覆盖点 + BFS判圈)

思路:先判断是否为二分图,再匈牙利,又因为关系数求得的是相互的,所以最后sum / 2(双向)

#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
int map[205][205],vist[205],match[205],n;
int find(int i)
{
    for(int j=1;j<=n;j++)
    if(!vist[j]&&map[i][j])
    {
        vist[j]=1;
        if(match[j]==0||find(match[j]))
        {
            match[j]=i; return 1;
        }
    }
    return 0;
}
int bfs()//判断是否为二分图
{
    queue<int>q;
    memset(vist,0,sizeof(vist));
        q.push(1); vist[1]=1;
        while(!q.empty())
        {
            int p=q.front(); q.pop();
            for(int j=1;j<=n;j++)
            if(map[p][j])
            {
                if(vist[j]==0)
                {
                    if(vist[p]==1)vist[j]=2;else vist[j]=1;
                    q.push(j);
                }
                else if(vist[j]==vist[p])
                    return 0;
            }
        }
    return 1;
}
int main()
{
    int m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(map,0,sizeof(map));
        while(m--)
        {
            scanf("%d %d",&a,&b);
            map[a][b]=map[b][a]=1;
        }
        if(!bfs()||n==1)
        {
            printf("No\n"); continue;
        }
        memset(match,0,sizeof(match));
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vist,0,sizeof(vist));
            ans+=find(i);
        }
        printf("%d\n",ans/2);//除2是因为对称,1认识2 与 2认识1 属同一情况
    }
}
View Code

【二分图最小覆盖】

公式:DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数.

即选择尽量少的点,使每条边至少有一个端点被选中。

首先将每个节点分成两个 ,有一条有向边l-r,则在图上有l到r为1 。

同时对拆分成两个结点的图进行二分图匹配。

因为每匹配一条边,证明有一个点被加到了 一条路径上,则节点总数减去最大匹配数就是最小路径。

由König定理定理可知,二分图的最小顶点覆盖数等于二分图的最大匹配数。

关于König定理的证明网上也比较多。大家可以百度找一找。题目中的这棵树之所以可以当成二分图,是因为如果从一个点出发,那么可以将整棵树分成奇数点层和偶数点层。由于树是一种特殊的图。n个点由(n-1)条边连接起来。这样假定一个点为树的根,假设各点间的边权值为1。那么从树根出发遍历整棵树,根据各点到根的路径的奇偶性即可将所有点分成两个集合。奇数点与偶数点交替出现。假设奇数点与偶数点连边,偶数点则继续和下一层的奇数点连边。这就与二分图中同类集合点间无边,不同类集合点间有边相连吻合起来了。所以满足二分图的性质。也可以用二分图最大匹配进行求解。这个对点分成奇数点偶数点的方法与搜索剪枝中的奇偶剪枝很像。奇偶剪枝中对点的分类与该方法相同。

可以证明,最小覆盖等于最大匹配数。

hdu1151  ( 最小覆盖边模板题 )

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXN 220
#define MAXM 220
using namespace std;

int map[MAXN][MAXN];
int vis[MAXN], use[MAXN];
int n, m, t, v;

int find(int x)
{
    for(int j = 1; j <= n; j++)
    {
        if(map[x][j] && !vis[j])
        {
            vis[j] = 1;
            if(use[j] == 0 || find(use[j]) == 1)
            {
                use[j] = x;
                return 1;
            }
        }
    }
    return 0;
}

int maxP()
{
    int sum = 0;
    memset(use, 0, sizeof(use));
    for(int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(find(i)) sum++;
    }
    return sum;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        memset(map, 0, sizeof(map));
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d", &t, &v);
            map[t][v] = 1;
        }
        printf("%d\n", n - maxP());
    }
    return 0;
}
View Code

hdu1054  ( 最小覆盖点模板题 )

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include <vector>
#include<algorithm>
using namespace std;

const int maxn=1510;
int n;
int pre[maxn];//保存各点的匹配点
int vis[maxn];
vector<int> e[maxn];
int find(int u)//判断是否存在增广路,存在返回1
{
    int i,v;
    for(i=0;i<e[u].size();i++)
    {
        v=e[u][i];
        if(vis[v])continue;
        vis[v]=1;
        if(pre[v]==-1||find(pre[v]))//找到未盖点,或者是增广路。
        {
            pre[v]=u;//匹配边和非匹配边交换
            return 1;
        }
    }
    return 0;
}

int check(){
    int ans=0;

    for(int i=0;i<n;i++)
    {
        memset(vis,0,sizeof(vis));
        ans+=find(i);
    }

    return ans;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int i,j,k,a,b,c,m;
        memset(pre,-1,sizeof(pre));
        for(i=0;i<n;i++)e[i].clear();
        for(i=0;i<n;i++)
        {
            scanf("%d:(%d)",&a,&m);
            for(j=0;j<m;j++)
            {
                scanf("%d",&b);
                e[a].push_back(b);
                e[b].push_back(a);
            }
        }

        int ans = check();
        printf("%d\n",ans/2);
    }
    return 0;
}
View Code

【二分图最大独立集】

即选择尽量多的点,使得任意两个结点不相邻(即任意一条边的两个端点不能同时被选中)。

最大独立集和最小覆盖集是互补的,因此答案为结点数减去最小覆盖数。

【二分图最小点权覆盖集】

设有无向图G(V,E),对于任意结点u,都对应一个非负权值w,称为结点的点权。点权之和最小的点覆盖集为最小点权覆盖集。

二分图最小点权覆盖集=最小割

将原问题的图G构造为网络为N=(V,E)的最小割模型:

1,新增源点s和汇点t。

2,将图中每条边u->v加上容量为正无穷大。

3,对于出点集中每个点u,新增有向边s->u,边权为结点u的权值。

4,对于入点集中每个点v,新增有向边v->t,边权为结点v的权值。

【二分图最大点权独立集】

给出一个二分图,每个结点有一个权值,要求选出一些结点,使得这些点之间没有边相连,并且权值和最大。

刚才讲到二分图最大独立集和最小覆盖集是互补的,二分图最大点权独立集和最小点权覆盖集也是互补的。所以我们只要知道所有点权和以及最小点权覆盖集,那么最大点权独立集也就知道了。

【DAG的最少路径覆盖】

有向无环图G(V,E)的一个路径覆盖是指一个路径集合P,满足图中的每点属于且仅属于集合中的一条路径,求一个包含路径条数最少的路径覆盖。

二分图模型:

1,把每个点i拆成两点 i' 和 i'' 。

2,把边集中的弧(i,j)改为无向边(i'' , j' )。

01-13 04:14