题目链接：

option=com_onlinejudge&Itemid=8&page=show_problem&problem=4536">点击打开链接

题意：

给定n*n的棋盘，

能够在'.'上摆 象棋中的车（X是墙壁）

使得随意两个车都不能互相攻击到

问：最多能摆多少个车。

思路：

二分匹配

1、若没有X。那么做法就是 X点集为行，Y点集为列，对于图上的每一个点所在的行和列(x,y) 建一条边 x->y

2、有了X，那么对于每一个点所在的上方能接触到的X必须各不同样。所以给每一个X标号，第一个X标记成n+1

3、这样X点集就是行(1-n) 和 n+1-siz (siz是X的个数)

4、对于每一个点，上方能接触到的近期的X作为列，右方能接触到的近期的Y作为行，建一条边 X->Y

而处理每一个点上方能接触到的近期的X就是一个dp。右方也是相同处理。

然后跑个二分匹配就好。

<pre name="code" class="cpp">#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

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;

const int N = 10105;

struct Edge{

    int to, nex;

}edge[N*2];

int head[N], edgenum;

void init(){memset(head, -1, sizeof head); edgenum = 0;}

void add(int u, int v){

    Edge E = {v, head[u]};

    edge[edgenum] = E;

    head[u] = edgenum++;

}

int lef[N], pn;

int tim, T[N];

bool match(int x){

    for(int i=head[x]; ~i; i=edge[i].nex)

    {

        int v = edge[i].to;

        if(T[v] != tim)

        {

            T[v] = tim;

            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 = 1; i<= pn; i++)//X集匹配。X集点标号从 1-pn 匹配边是G[左点].size()

    {

        tim++;

        if( match( i ) ) ans++;

    }

    return ans;

}

int n, siz, s[105][105], l[105][105], mp[105][105];

char str[105];

void input(){

	siz = n;

	for(int i = 1; i <= n; i++)

	{

		scanf("%s", str+1);

		for(int j = 1; j <= n; j++){

			if(str[j] == 'X')

				mp[i][j] = ++siz;

			else

				mp[i][j] = 0;

		}

	}

}

void build(){

	for(int i = 1; i <= n; i++)

		s[0][i] = i;

	for(int i = 1; i <= n; i++)

		for(int j = 1; j <= n; j++)

			if(mp[i][j])

				s[i][j] = mp[i][j];

			else

				s[i][j] = s[i-1][j];

	for(int i = 1; i <= n; i++)

		l[i][n+1] = i;

	for(int i = n; i; i--)

    {

		for(int j = 1; j <= n; j++)

			if(mp[j][i])

				l[j][i] = mp[j][i];

			else

				l[j][i] = l[j][i+1];

    }

	init();

	pn = siz;

	for(int i = 1; i <= n; i++)

		for(int j = 1; j <= n; j++)

			if(mp[i][j] == 0)

				add(l[i][j+1], s[i-1][j]);

}

int main(){

    tim = 1; memset(T, 0, sizeof T);

	while(cin>>n){

		input();

		build();

		cout<<solve()<<endl;

	}

	return 0;

}

/*

5

X....

X....

..X..

.X...

....X

3

.X.

XXX

XXX

3

.X.

X.X

XXX

3

.X.

X.X

X.X

3

.X.

X.X

.X.

3

XXX

XXX

XXX

15

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

XXXXXXXXXXXXXXX

*/