时间复杂度

显然，这个算法的时间复杂度是O(一边的点数*边数)

因为最坏情况就是每一个点都要把所有的边问一遍能不能匹配

显然，常数极小

另外可以留意一下数据范围，因为如果是稠密图（\(n=500 m=2e5\)这种）就可以考虑邻接矩阵存图，方便判重边S

准备

以下是跑Ntr算法要用的一些东西

如果题里没直接给，应该想办法先搞出来

1.左边的点（和右边的点）
2.左边的点指向右边的点的边（反着的边无所喂）
3.vis数组 用于记录每次增广中一个右边的点是否已经被访问（如果已经访问过就没必要再访问了）
4.match数组 用于记录每一个右边点现在匹配的左边点

板子题

luoguP3386

板子

#include<bits/stdc++.h>
using namespace std;

const int N= 505;
const int M= (int)5e4;

int n,m,c;

int g[505][505];

int match[N];
bool vis[N];

int ans;

bool Ntr(int u)
{
    for(int i=1;i<=m;i++)
    {
        if(g[u][i]==1 && !vis[i])
        {
            vis[i]=1;
            if(!match[i] || Ntr(match[i])) 
            {   
                match[i]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m>>c;
    for(int i=1;i<=c;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u][v]=1;
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(Ntr(i)) ans++;
    }
    cout<<ans;
    return 0;
}