[二分匹配]zoj 3646：Matrix Transformer

大致题意：

 

给出一个n*n的矩阵，每个矩阵元素的U或者是D。

例如

DUD
UDD
DDU

每次操作，可以交换任意两行或者两列。求是否能使得其主对角线上的元素全部变成U。

 

大致思路：

    仔细思考就能发现，问题可以转化为，能否找出n个‘U’，使得他们之间两两的行数和列数都不相同。于是就很容易就能构造出二分匹配模型了。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int nMax=1005;
int n,m;
long long num[nMax];
bool map[nMax][nMax];
bool vis[nMax];
int linkk[nMax];
int dfs(int s){
	for(int i=1;i<=m;i++){
			if(!vis[i]&&map[s][i]){
				vis[i]=1;
		        if(linkk[i]==-1||dfs(linkk[i])){
						linkk[i]=s;
			             return 1;
				}
			}
	}
	return 0;
}

char str[nMax][nMax];
int main(){
	int cas,i,j;
	while(cin>>n){
		m=n;
		memset(map,0,sizeof(map));
		for(i=1;i<=n;i++)
		{
		    cin>>str[i]+1;
		    for(j=1;j<=n;j++)
		    {
		        if(str[i][j]=='U')
		        {
		            map[i][j]=1;
		        }
		    }
		}
        int ans=0;
        memset(linkk,-1,sizeof(linkk));
        for(i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))ans++;
        }
        if(ans==n)
        {
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
	}
	return 0;
}