題目鏈接：點擊打開鏈接

題意：

給定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;elsemp[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];elses[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];elsel[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... ....X3 .X. XXX XXX3 .X. X.X XXX3 .X. X.X X.X3 .X. X.X .X. 3 XXX XXX XXX 15 XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX*/

轉載于:https://www.cnblogs.com/yxwkf/p/5269605.html

總結

以上是生活随笔為你收集整理的UVALive 6525 Attacking rooks 二分匹配 经典题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。