嘟嘟嘟



虽然我已经会网络流了，但是还是学了一个匈牙利算法。

——就跟我会线段树，但还是学了树状数组一样。



其实匈牙利算法挺暴力的。简单来说就是先贪心匹配，然后如果左部点\(i\)匹配不上了，就尝试更改前面已经匹配好的点，腾出地给他匹配。

因此对于每一个点跑一遍匈牙利算法，如果这个点匹配成功，总匹配数就加1。

感觉没啥好讲的。

关于这道题怎么做，看我这篇博客吧。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define rg register

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 505;

const int maxe = 1e4 + 5;

inline ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

inline void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

int n, k;

struct Edge

{

  int nxt, to;

}e[maxe];

int head[maxn], ecnt = -1;

void addEdge(int x, int y)

{

  e[++ecnt] = (Edge){head[x], y};

  head[x] = ecnt;

}

int fa[maxn], vis[maxn], vcnt = 0;

//fa:下标是右部点,表示右部点i和左部点fa[i]匹配上了

//vis:表示匹配点i的时候这个点是不是i要匹配的

//因此每一次dfs前应该清空,为了降低复杂度,改为累加标记

bool dfs(int now)

{

  for(int i = head[now], v; i != -1; i = e[i].nxt)

    {

      if(vis[v = e[i].to] != vcnt)

	{

	  vis[v] = vcnt;

	  if(!fa[v] || dfs(fa[v])) {fa[v] = now; return 1;}

	}

    }

  return 0;

}

int main()

{

  Mem(head, -1);

  n = read(); k = read();

  for(int i = 1; i <= k; ++i)

    {

      int x = read(), y = read();

      addEdge(x, y);

    }

  int ans = 0;

  for(int i = 1; i <= n; ++i)

    {

      ++vcnt;

      if(dfs(i)) ans++;

    }

  write(ans), enter;

  return 0;

}