3673:Black-White Grid

問題文
https://icpcarchive.ecs.baylor.edu/external/36/3673.pdf

n×nの黒と白のグリッドが与えられる。任意の行と行、列と列をスワップすることができる。この操作を繰り返すことで、縦と横の番号が同じようなマスを全て白にできるか判定せよ。

斜めに並べることができるマスは互いに同じ行または同じ列にはない。これを満たすようにマスを選んでいったとき、選ばれたマスの個数がnになるようなマスの選び方があればYESとなる。

そのようなマスの選び方のうち個数が最大のものの個数は、行の番号を左側に、列の番号を右側にして、あるマスが白であればそのマスの行の番号のノードから列の番号のノードに辺を張った二部グラフのマッチングとなる。

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX_V 2001

using namespace std;

int V,match[MAX_V];
vector<int>g[MAX_V];
bool used[MAX_V];

void add_edge(int u,int v){
  g[u].push_back(v);
  g[v].push_back(u);
}

bool dfs(int v){
  used[v]=true;
  for(int i=0;i<g[v].size();i++){
    int u=g[v][i],w=match[u];
    if(w<0 || !used[w] && dfs(w)){
      match[v]=u,match[u]=v;
      return true;
    }
  }
  return false;
}

int bipartite_matching(){
  int res=0;
  fill(match,match+MAX_V,-1);
  for(int v=0;v<V;v++){
    if(match[v]<0){
      fill(used,used+MAX_V,false);
      if(dfs(v))res++;
    }
  }
  return res;
}

int main(void){

  int t;
  cin >> t;
  while(t--){
    for(int i=0;i<MAX_V;i++)g[i].clear();

    int n;
    cin >> n;

    char ch[1001][1001];
    for(int i=0;i<n;i++)cin >> ch[i];

    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        if(ch[i][j]=='W')add_edge(i,j+n);

    V=n*2;
    if(bipartite_matching()!=n)cout << "NO" << endl;
    else cout << "YES" << endl;
  }
  return 0;
}