P2825 [HEOI2016/TJOI2016] 游戏 与 P10945 Place the Robots
cnblogs 2024-08-29 16:09:00 阅读 89
讲解 P2825 [HEOI2016/TJOI2016] 游戏 与 P10945 Place the Robots。
首先进行图论建模，考虑使用匈牙利算法求二分图最大匹配数。
本文中的机器人同炸弹，主要是题目描述不同，两道题目做法是本质相同的。
思路：
先说一下没有墙怎么办，那么当一个位置放了机器人之后，这个机器人所在的行和列是不能继续放置的。
那么发现行和列几乎是独立的，考虑建二分图，若 \((i,j)\) 能放一个机器人，那么给 \(i \to j\) 建一条边。
那么答案就是这个二分图的最大匹配，这样每个匹配的就代表着一个机器人所放的位置。
现在再考虑有墙的情况，有墙时，机器人所放的激光无法穿透过去，则在墙另外一边依旧可能可以放置机器人。
发现墙就是把行或列分为了几个部分，每个部分互不干扰，则考虑每遇到墙，就新起一行表示当前位置到下一个墙或者这一行的末尾的放块；列同理。
直接跑匈牙利算法即可。
P2825 [HEOI2016/TJOI2016] 游戏 Code：
<code>#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const ll N=2505;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
inline char get(){
char c;
while((c=getchar())!='*'&&c!='x'&&c!='#');
return c;
}
ll n,m,id,ans,s1,s2;
ll a[N],f[N];
ll h[N][N];
char s[N][N];
vector<ll> E[N];
void add(ll u,ll v){
E[u].push_back(v);
}
bool dfs(ll u){
for(auto v:E[u]){
if(f[v]==id)
continue;
f[v]=id;
if(!a[v]||dfs(a[v])){
a[v]=u;
return 1;
}
}
return 0;
}
void Match(){
for(int i=1;i<=s1;i++){
id=i;
if(dfs(i))
ans++;
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=get();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='#')
continue;
if(s[i][j-1]=='#'||j==1)
++s1;
h[i][j]=s1;
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(s[i][j]=='#')
continue;
if(s[i-1][j]=='#'||i==1)
++s2;
if(h[i][j]&&s[i][j]=='*')
add(h[i][j],s2);
}
}
Match();
write(ans);
return 0;
}
P10945 Place the Robots Code：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const ll N=2505;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
inline char get(){
char c;
while((c=getchar())!='*'&&c!='o'&&c!='#');
return c;
}
ll T,n,m,cnt,id,ans,s1,s2;
ll a[N],f[N];
ll h[N][N];
char s[N][N];
vector<ll> E[N];
void add(ll u,ll v){
E[u].push_back(v);
}
bool dfs(ll u){
for(auto v:E[u]){
if(f[v]==id)
continue;
f[v]=id;
if(!a[v]||dfs(a[v])){
a[v]=u;
return 1;
}
}
return 0;
}
void Match(){
memset(f,0,sizeof(f));
memset(a,0,sizeof(a));
for(int i=1;i<=s1;i++){
id=i;
if(dfs(i))
ans++;
}
}
void solve(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=get();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='#')
continue;
if(s[i][j-1]=='#'||j==1)
++s1;
h[i][j]=s1;
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(s[i][j]=='#')
continue;
if(s[i-1][j]=='#'||i==1)
++s2;
if(h[i][j]&&s[i][j]=='o')
add(h[i][j],s2);
}
}
Match();
printf("Case :%lld\n",++cnt);
write(ans);
putchar('\n');
For(i,1,max(s1,s2))
E[i].clear();
s1=s2=ans=0;
}
int main(){
T=read();
while(T--)
solve();
return 0;
}
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。