手机网站制作建设,东道设计官网,网站开发哪里安全,如何为网站建设内容题目描述
详见 P2825 [HEOI2016/TJOI2016]游戏。
solution
套路题。
一般思路是行列建点跑二分图最大匹配。
此题中的#会分隔行列#xff0c;因此我们把每行的极大联通块设为点#xff0c;列同理建点。
再对于每个*对应的行的极大联通块与列的最大联通块编号连边…题目描述
详见 P2825 [HEOI2016/TJOI2016]游戏。
solution
套路题。
一般思路是行列建点跑二分图最大匹配。
此题中的#会分隔行列因此我们把每行的极大联通块设为点列同理建点。
再对于每个*对应的行的极大联通块与列的最大联通块编号连边跑最大匹配即可。
#includebits/stdc.h
using namespace std;
const int MAXN55;
vectorint e[MAXN*MAXN];
bool vis[MAXN*MAXN];
char st[MAXN];
int flag[MAXN][MAXN];
int color1[MAXN][MAXN],color2[MAXN][MAXN],X[MAXN*MAXN],Y[MAXN*MAXN];
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
bool check(int u)
{for (int i0;ie[u].size();i){int toe[u][i];if (vis[to]) continue;vis[to]1;if (X[to]-1||check(X[to])) { X[to]u,Y[u]to; return 1; }}return 0;
}
int main()
{int nread(),mread(),colornum1,num0;for (int i1;in;i){scanf(%s,st);for (int j0;jm;j){if (st[j]*) flag[i][j1]0;if (st[j]x) flag[i][j1]1;if (st[j]#) flag[i][j1]2;}}for (int i1;in;i){if (num0) colornum,num0;for (int j1;jm;j)if (flag[i][j]2num0) num0,colornum; else if (flag[i][j]2) color1[i][j]0;else num,color1[i][j]colornum;}for (int i1;im;i){if (num0) colornum,num0;for (int j1;jn;j)if (flag[j][i]2num0) num0,colornum;else if (flag[j][i]2) color2[j][i]0;else num,color2[j][i]colornum;}for (int i1;in;i)for (int j1;jm;j)if (flag[i][j]0) e[color1[i][j]].push_back(color2[i][j]);/*for (int i1;in;i){for (int j1;jm;j) coutsetw(3)color1[i][j];coutendl;}coutendl;for (int i1;in;i){for (int j1;jm;j) coutsetw(3)color2[i][j];coutendl;}*/int ans0;for (int i1;icolornum;i) X[i]Y[i]-1;for (int i1;icolornum;i) {memset(vis,0,sizeof vis);anscheck(i);}printf(%d\n,ans);return 0;
}
