CSU 1531 Jewelry Exhibition二分整合(裸

タイトルリンク:クリックしてリンクを開く
タイトル:
与えられた[0,n]*[0,m]の2次元行列
マトリクス内にk個の緑点がある
以下のk行は緑点座標を与え、(与えられた座標が整数でなく、0<=x<=n、0<=y<=mであることを保証する
質問:
幅1のブラシで、一度に1行を染色したり、1列を染色したりすることができます
ブラシは最低何回使うかを聞く
考え方:
2点マッチングで、すべての点をその点がある四角形の左下隅座標にマッピングします(小数部を捨てます)
そして古典的な行列マッチングで、排兵布陣と同じようにします.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>

template <class T>
inline bool rd(T &ret) {
	char c; int sgn;
	if(c=getchar(),c==EOF) return 0;
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
template <class T>
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if(x>9) pt(x/10);
    putchar(x%10+'0');
}
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int N = 105;
const int inf = 1e8;
int lef[N], pn;//lef[v]  Y   v        , pn x     
bool T[N];     //T[u]   Y  u      X 
vector<int>G[N]; //     G[X ].push_back(Y )    G    

bool match(int x){ // x Y       x       
	for(int i=0; i<G[x].size(); i++)
	{
		int v = G[x][i];
		if(!T[v])
		{
			T[v] = true;
			if(lef[v] == -1 || match( lef[v] ))   //match(lef[v]) :     v X   lef[v]        ，     v        x 
			{
				lef[v] = x;
				return true;
			}
		}
	}
	return false;
}

int solve(){
	int ans = 0;
	memset(lef, -1, sizeof(lef));
	for(int i = 0; i< pn; i++)//X   ，X      1-pn     G[  ].size()
	{
		memset(T, 0, sizeof(T));
		if( match( i ) ) ans++;
	}
	return ans;
}
int n, m, point;

int main(){
	int T; rd(T);
	double x, y;
    while(T-->0){
    	rd(n); rd(m); rd(point);
    	for(int i = 0; i < N; i++)G[i].clear();
    	pn = n;
    	while(point-->0){
    		scanf("%lf %lf", &x, &y);
			int X = x, Y = y;
			G[X].push_back(Y);
    	}
		pt(solve()); puts("");
    }
    return 0;
}