UVALive 6525 Attacking rooks 二分匹配 經典題
來源：程序員人生 發布時間：2014-11-18 08:47:00 閱讀次數：2936次
題目鏈接：點擊打開鏈接
題意：
給定n*n的棋盤，
可以在'.'上擺 象棋中的車（X是墻壁）
使得任意兩個車都不能相互攻擊到
問：最多能擺多少個車。
思路：
2分匹配
1、若沒有X，那末做法就是 X點集為行，Y點集為列，對圖上的每一個點所在的行和列(x,y) 建1條邊 x->y
2、有了X，那末對每一個點所在的上方能接觸到的X必須各不相同，所以給每一個X標號，第1個X標記成n+1
3、這樣X點集就是行(1-n) 和 n+1-siz (siz是X的個數)
4、對每一個點，上方能接觸到的最近的X作為列，右方能接觸到的最近的Y作為行，建1條邊 X->Y
而處理每一個點上方能接觸到的最近的X就是1個dp，右方也是一樣處理。
然后跑個2分匹配就好。
<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;
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, ⑴, 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] == ⑴ || 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, ⑴, 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⑴][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⑴][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
*/
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
