首页 > 代码库 > UESTC 919 SOUND OF DESTINY --二分图最大匹配+匈牙利算法

UESTC 919 SOUND OF DESTINY --二分图最大匹配+匈牙利算法

2024-07-08 06:58:53   229人阅读

二分图最大匹配的匈牙利算法模板题。

由题目易知，需求二分图的最大匹配数，采取匈牙利算法，并采用邻接表来存储边，用邻接矩阵会超时，因为邻接表复杂度O(nm)，而邻接矩阵最坏情况下复杂度可达O(n^3)。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>using namespace std;#define N 1007int vis[N];int match[N];int n,m;vector<int> G[N];int Search_Path(int s){    for(int i=0;i<G[s].size();i++)    {        int v = G[s][i];        if(!vis[v])        {            vis[v] = 1;            if(match[v] == -1 || Search_Path(match[v]))            {                match[v] = s;                return 1;            }        }    }    return 0;}int main(){    int cnt,i,j,k;    int a,b;    scanf("%d%d",&n,&m);    for(i=0;i<=n;i++)        G[i].clear();    scanf("%d",&k);    memset(match,-1,sizeof(match));    for(i=0;i<k;i++)    {        scanf("%d%d",&a,&b);        a--,b--;        G[a].push_back(b);    }    cnt = 0;    for(i=0;i<n;i++)    {        memset(vis,0,sizeof(vis));        if(Search_Path(i))            cnt++;    }    printf("%d\n",cnt);    return 0;}
View Code

 


联系
我们