hdu 2063 过山车 （匈牙利算法入门）

题目链接

题意：求二分图的最大匹配。

 

• 首先啥是二分图？

 

1. 二分图的定义：是可以把图中的点划分成两个集合，集合内部的点没有连边的图。
2. 二分图形成的条件是：图中没有奇环。

 

• 啥是匹配？

 

1. 匹配的定义：匹配是一对一的将两个集合中的点进行配对。
2. 最大匹配：指一个匹配方案使得二分图中的匹配数目最多。
3. 完美匹配：指两个集合中的点恰好匹配完，没有孤立点。完美匹配是一种特殊的最大匹配。

 

• 怎样求最大匹配？——用匈牙利算法呀。

 

1. 匈牙利算法：在二分图中不停的找增广路来增加匹配数目。
2. 时间复杂度：根据存图方式不同而不同。邻接表o（V*E）。

​​​​​​​

• 什么是增广路？

​​​​​​​

1. ​​​​​​​定义：一条 非匹配边->匹配边->非匹配边->......->非匹配边 的路径。
2. 性质：增广路中非匹配边永远比匹配边多一条。

 

• ​​​​​​​算法实现过程？（假设左边集合为a，右边集合为b）

​​​​​​​

1. ​​​​​​​首先：按顺序枚举a集合的点，与b中的点匹配，如果能发现可以匹配就直接匹配，。
2. 其次：如果不能匹配，尝试调整之前的匹配，相当于找一条增广路。

​​​​​​​

• 该算法可用于求解什么问题？

​​​​​​​

1. 最大匹配数：最大匹配的匹配边的数目
2. 最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择
3. 最大独立数：选取最多的点，使任意所选两点均不相连
4. 最小路径覆盖数：对于一个DAG (有向无环图)，选取最少条路径， 使得每个顶点属于且仅属于一条路径。路径长可以为0 (即单个点)。

​​​​​​​

• 如何求？

​​​​​​​

1. 定理1：最大匹配数=最小点覆盖数(这是Konig定理)
2. 定理2：最大匹配数=最大独立数
3. 定理3：最小路径覆盖数=顶点数-最大匹配数

​​​​​​​
 

思路：枚举男生，used代表这一轮匹配中女生是否访问，nxt【i】代表跟第i位女生匹配的男生，G保存的是两个集合中元素的联系。

#include<bits/stdc++.h>

using namespace std;
const int maxn = 505;
int vis[maxn],nxt[maxn];
vector<int>G[maxn];

bool dfs(int u)
{
    for(int i=0;i<G[u].size();i++)
    {
        int v = G[u][i];
        if(vis[v])continue;
        vis[v] = 1;
        if(nxt[v] == 0 || dfs(nxt[v]))
        {
            nxt[v] = u;
            return true;
        }
    }
    return false ;
}

void match(int n)
{
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))++ans;
    }
    printf("%d\n",ans);
}
int main()
{
    int k,n,m;
    while(~scanf("%d",&k)&&k)
    {
        memset(vis,0,sizeof(vis));
        memset(nxt,0,sizeof(nxt));
        for(int i=0;i<maxn;i++)G[i].clear();
        scanf("%d%d",&n,&m);
        while(k--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
        }
        match(n);
    }
 }