P2825 [HEOI2016/TJOI2016]游戏 （二分图最大匹配，预处理）

P2825 [HEOI2016/TJOI2016]游戏

分析：

• 和 P1129 [ZJOI2007] 矩阵游戏 这题差不多，也是行和列分别看作二分图的两个集合

  多了一些 预处理

  若行或列被硬石头隔开了，那再分别加行或列即可

• 吐槽一下下：$wsfw$ , $"yr[j]=++toy"$ 我直接复制上一行，把 $j$ 变成 $i$ 了，调错调了 $1$ 小时…

  还对着题解写了另一种预处理的解法（见下文）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
vector <int> g[N];
int vis[N],pre[N];
bool dfs(int u,int tag)
{
if(vis[u]==tag) return false;
vis[u]=tag;
for(auto v : g[u])
{
if(!pre[v] || dfs(pre[v],tag))
{
pre[v]=u; return true;
}
}
return false;
}
int xr[N], yr[N];
char s[N][N];
int b[N];
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) xr[i]=i;
for(int i=1;i<=m;i++) yr[i]=i;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cin>>s[i][j];
}
int tox=n, toy=m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='*')
{
g[xr[i]].push_back(yr[j]);
}
if(s[i][j]=='#')
{
if(s[i][j+1]=='x' || s[i][j+1]=='*') xr[i]=++tox;
if(s[i+1][j]=='x' || s[i+1][j]=='*') yr[j]=++toy;
}
}
}
int ans=0;
for(int i=1;i<=tox;i++)
{
if(dfs(i,i)) ans++;
}
cout<<ans<<endl;
return 0;
}

（没有多大区别，我是合并的写，还省空间了）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
vector <int> g[N];
int vis[N],pre[N];
bool dfs(int u,int tag)
{
if(vis[u]==tag) return false;
vis[u]=tag;
for(auto v : g[u])
{
if(!pre[v] || dfs(pre[v],tag))
{
pre[v]=u; return true;
}
}
return false;
}
int row[N][N], col[N][N];
char s[N][N];
int b[N];
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cin>>s[i][j];
}
int tox=0, toy=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='#') continue;
if(j==1 || s[i][j-1]=='#') tox++;
row[i][j]=tox;
}
}
for(int j=1;j<=m;j++)
{
for(int i=1;i<=n;i++)
{
if(s[i][j]=='#') continue;
if(i==1 || s[i-1][j]=='#') toy++;
col[i][j]=toy;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='*')
{
g[row[i][j]].push_back(col[i][j]);
}
}
}
int ans=0;
for(int i=1;i<=tox;i++)
{
if(dfs(i,i)) ans++;
}
cout<<ans<<endl;
return 0;
}

最后

以上就是清新季节为你收集整理的P2825 [HEOI2016/TJOI2016]游戏 （二分图最大匹配，预处理）的全部内容，希望文章能够帮你解决P2825 [HEOI2016/TJOI2016]游戏 （二分图最大匹配，预处理）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。