匈牙利板子+题

板子
计算最大匹配
遍历一个集合
时间复杂度o（nm）

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=100005;
vector<int> v[maxn];
bool vis[maxn];
int mat[maxn];
bool dfs(int x){
   
	for(int i=0;i<v[x].size();i++){
   
		if(!vis[v[x][i]]){
   
			vis[v[x][i]]=1;
			if(!mat[v[x][i]]||dfs(mat[v[x][i]])){
   
				mat[v[x][i]]=x;	
				//printf("%d %d\n",v[x][i],x);
				return true;
			}
		}
	}
	return false;
}
int main(){
   
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
   
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
   
		memset(vis,0,sizeof(vis));
		if(dfs(i))	ans++;
	}
	printf("%d",ans);
	return 0;
} 

题目：小QQ是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个N×N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：

行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）

列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）

游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。

对于某些关卡，小QQ百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小QQ决定写一个程序来判断这些关卡是否有解。

思路：以横行和纵行分别作为二分图的两边，可以发现，不管纵行横行怎么换，图是不变的，只是图上点的位置发生了变化，由此可知，当图的最大匹配为n时，一定可以的到所要结果.

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=100005;
vector<int> v[maxn];
bool vis[maxn];
int mat[maxn];
bool dfs(int x){
   
	for(int i=0;i<v[x].size();i++){
   
		if(!vis[v[x][i]]){
   
			vis[v[x][i]]=1;
			if(!mat[v[x][i]]||dfs(mat[v[x][i]])){
   
				mat[v[x][i]]=x;	
				//printf("%d %d\n",v[x][i],x);
				return true;
			}
		}
	}
	return false;
}
int main(){
   
	int t;
	scanf("%d",&t);
	while(t--){
   
		int n;
		scanf("%d",&n);
		for(int i=0;i<=n;i++)
			v[i].clear();
		memset(mat,0,sizeof(mat));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
   
				int x;
				scanf("%d",&x);
				if(x==1)
				v[i].push_back(j);
			}
		int ans=0;
		for(int i=1;i<=n;i++){
   
			memset(vis,0,sizeof(vis));
			if(dfs(i))	ans++;
		}
		if(ans==n)	printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}