[HEOI2016/TJOI2016]游戏 解题报告[HEOI2016/TJOI2016]游戏

[HEOI2016/TJOI2016]游戏

看起来就是个二分图匹配啊

最大化匹配是在最大化边数，那么一条边就代表选中一个坐标内的点

但是每一行不一定只会有一个匹配

于是把点拆开，按照'#'划分一下就好了

---

Code:

复制代码#include <cstdio> #include <cstring> #include <cctype> template <class T> void read(T &x) { x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-'0',c=getchar(); } const int N=52; const int M=1010; int Idr[N][N],Idc[N][N],r,c,n,m,yuu[M][M],vis[M],mat[M]; char s[N][N]; bool dfs(int now) { for(int i=1;i<=m;i++) if(!vis[i]&&yuu[now][i]) { vis[i]=1; if(!mat[i]||dfs(mat[i])) return mat[i]=now,true; } return false; } int main() { read(r),read(c); for(int i=1;i<=r;i++) { scanf("%s",s[i]+1); int las=1; for(int j=1;j<=c+1;j++) { if(s[i][j]=='#'||j==c+1) { if(las==j) {las=j+1;continue;} ++n; for(int k=las;k<j;k++) Idr[i][k]=n; las=j+1; } } } for(int j=1;j<=c;j++) { int las=1; for(int i=1;i<=r+1;i++) { if(s[i][j]=='#'||i==r+1) { if(las==i) {las=i+1;continue;} ++m; for(int k=las;k<i;k++) Idc[k][j]=m; las=i+1; } } } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(s[i][j]=='*') yuu[Idr[i][j]][Idc[i][j]]=1; int ans=0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof vis); ans+=dfs(i); } printf("%dn",ans); return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <cstring>
#include <cctype>
template <class T>
void read(T &x)
{
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
const int N=52;
const int M=1010;
int Idr[N][N],Idc[N][N],r,c,n,m,yuu[M][M],vis[M],mat[M];
char s[N][N];
bool dfs(int now)
{
for(int i=1;i<=m;i++)
if(!vis[i]&&yuu[now][i])
{
vis[i]=1;
if(!mat[i]||dfs(mat[i]))
return mat[i]=now,true;
}
return false;
}
int main()
{
read(r),read(c);
for(int i=1;i<=r;i++)
{
scanf("%s",s[i]+1);
int las=1;
for(int j=1;j<=c+1;j++)
{
if(s[i][j]=='#'||j==c+1)
{
if(las==j) {las=j+1;continue;}
++n;
for(int k=las;k<j;k++) Idr[i][k]=n;
las=j+1;
}
}
}
for(int j=1;j<=c;j++)
{
int las=1;
for(int i=1;i<=r+1;i++)
{
if(s[i][j]=='#'||i==r+1)
{
if(las==i) {las=i+1;continue;}
++m;
for(int k=las;k<i;k++) Idc[k][j]=m;
las=i+1;
}
}
}
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
if(s[i][j]=='*')
yuu[Idr[i][j]][Idc[i][j]]=1;
int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof vis);
ans+=dfs(i);
}
printf("%dn",ans);
return 0;
}

---

2019.3.6