二分图最大匹配——匈牙利算法

二分图最大匹配

• 牛客ZJOI2007

  #include <iostream>
  #include <string.h>
  
  using namespace std;
  
  int mapx[205][205];
  bool v[205];
  int c[205];
  int n;
  
  int dfs(int x)
  {
  	for (int i = 1; i <= n; i++)
  	{
  		if (!v[i] && mapx[x][i])
  		{
  			v[i] = 1;
  			if (!c[i] || dfs(c[i]))
  			{
  				c[i] = x;
  				return 1;
  			}
  		}
  	}
  	return 0;
  }
  int main()
  {
  	int t;
  
  	cin >> t;
  
  	while (t--)
  	{
  		cin >> n;
  
  		memset(c, 0, sizeof (c));
  
  		for (int i = 1; i <= n; i++)
  		{
  			for (int j = 1; j <= n; j++)
  			{
  				cin >> mapx[i][j];
  			}
  		}
  
  		long long k = 0;
  		for (int i = 1; i <= n; i++)
  		{
  			memset(v, 0, sizeof (v));
  			if(dfs(i)) k++;
  		}
  		if (k == n) cout << "Yes" << endl;
  		else cout << "No" << endl;
  	}
  }