wordpress 微信导航站,南昌有哪些企业网站,熬夜必备黄,wordpress资源站主题题目链接#xff1a;点击打开链接 题意#xff1a; 给定n*n的棋盘#xff0c; 能够在.上摆 象棋中的车#xff08;X是墙壁#xff09; 使得随意两个车都不能互相攻击到 问#xff1a;最多能摆多少个车。 思路#xff1a; 二分匹配 1、若没有X。那么做法就是 X点集为行点击打开链接 题意 给定n*n的棋盘 能够在.上摆 象棋中的车X是墙壁 使得随意两个车都不能互相攻击到 问最多能摆多少个车。 思路 二分匹配 1、若没有X。那么做法就是 X点集为行Y点集为列对于图上的每一个点所在的行和列(x,y) 建一条边 x-y 2、有了X那么对于每一个点所在的上方能接触到的X必须各不同样。所以给每一个X标号第一个X标记成n1 3、这样X点集就是行(1-n) 和 n1-siz (siz是X的个数) 4、对于每一个点上方能接触到的近期的X作为列右方能接触到的近期的Y作为行建一条边 X-Y 而处理每一个点上方能接触到的近期的X就是一个dp。右方也是相同处理。 然后跑个二分匹配就好。
pre namecode classcpp#pragma comment(linker, /STACK:1024000000,1024000000)
#includebits/stdc.h
template class T
inline bool rd(T ret) {char c; int sgn;if(cgetchar(),cEOF) return 0;while(c!-(c0||c9)) cgetchar();sgn(c-)?-1:1;ret(c-)?0:(c-0);while(cgetchar(),c0c9) retret*10(c-0);ret*sgn;return 1;
}
template class T
inline void pt(T x) {if (x 0) {putchar(-);x -x;}if(x9) pt(x/10);putchar(x%100);
}
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 ihead[x]; ~i; iedge[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, str1);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][n1] 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][i1];}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][j1], s[i-1][j]);
}
int main(){tim 1; memset(T, 0, sizeof T);while(cinn){input();build();coutsolve()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
