题解：P10945 Place the Robots

· · 题解

这是一道 Hootime 看到就秒了的水紫。\ 本题解默认已经熟练掌握了匈牙利算法。\ 若没有，请移步 P3386。\ 话不多说，开始！

  1. 题意：\ 在地图内放机器人，只能在空地上放。\ 除非有墙的阻隔，否则不能再同一行列中放机器人。\ 求最多的机器人数量。
  2. 思路：\ 二分图秒了。\ 用行列作为二分图的子图（应该是叫这个名字吧）。\ 跑一遍匈牙利就行了。

  3. 细节：\ 建边的时候怎么办呢？

    如果没有墙，那么只需将行看作是二分图的一边，列看作另一边，然后可以放置机器人的地方的行向列连边即可。

    本来一行只能放一个机器人，但墙的出现导致一行被隔开，所以在有墙的情况下，可以把一行看成多行。

    还有！多测要清空！

那么，上代码！\ 代码里面有注释。

#include <bits/stdc++.h>
using namespace std;
#define int long long
char ch[1145][1145];
bool vis[1145][1145];
string str;
int g[114514],match[114514],re[114514],n,m,sum,next1[114514],head[114514],cnt;
int tot1,tot2;//左部点数量和右部点数量 
struct ppp{
    int d,x,y;
}a1[114514],a2[114514];
void add(int u,int p){ 
    ++cnt;
    next1[cnt] = head[u],g[cnt] = p,head[u] = cnt;
}
bool dfs(int x){//匈牙利 
    for(register int i = head[x];i;i = next1[i]){//枚举右部点
        if(re[g[i]] == 0){//有边并且没被匹配 
            re[g[i]] = 1;//匹配上 
            if(match[g[i]] == 0){//match[i]存储的是匹配的人 
                match[g[i]] = x;
                return 1;
            }
            else if(dfs(match[g[i]])){
                match[g[i]] = x;
                return 1;
            }
        }
    }
    return 0;
}
void init(){
    for(register int i = 0;i <= 1143;++i) re[i] = 0;//re存储的是有没有被dfs过 
}
void init2(){//初始化(不得不说是真的恶心) 
    memset(vis,0,sizeof(vis));
    memset(g,0,sizeof(g));
    memset(match,0,sizeof(match));
    memset(re,0,sizeof(re));
    memset(next1,0,sizeof(next1));
    memset(head,0,sizeof(head));
    cnt = 0,tot1 = 0,tot2 = 0,sum = 0,n = 0,m = 0;
    for(register int i = 0;i <= 1513;++i){
        a1[i] = ppp{0,0,0};
        a2[i] = ppp{0,0,0};
    }
    for(register int i = 0;i <= 164;++i){
        for(register int j = 0;j <= 164;++j){
            ch[i][j] = ' ';
        }
    }
}
signed main(){
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    for(int ___ = 1;___ <= t;___++){
        init2();
        cin >> n >> m;
        for(register int i = 1;i <= n;i++){
            cin >> str;
            for(register int j = 1;j <= m;j++){
                 ch[i][j] = str[j-1];
            }
        }
        for(register int i = 1;i <= n;i++){
            for(register int j = 1;j <= m;j++){
                if(vis[i][j]) continue;
                if(ch[i][j] != 'o') continue;
                int xx11 = i,xx22 = i,yy11 = j,yy22 = j;
                while(xx11 > 1 && ch[xx11-1][j] != '#'){
                    xx11--;//区间左端点 
                }
                while(xx22 < n && ch[xx22+1][j] != '#'){
                    xx22++;//区间右端点 
                }
                for(register int k = xx11;k <= xx22;k++){
                    vis[k][j] = 1;
                }
                a1[++tot1] = ppp{j,xx11,xx22};
            }
        }
        memset(vis,0,sizeof(vis));
        for(register int i = 1;i <= n;i++){
            for(register int j = 1;j <= m;j++){
                if(vis[i][j]) continue;
                if(ch[i][j] != 'o') continue;
                int xx11 = i,xx22 = i,yy11 = j,yy22 = j;
                while(yy11 > 1 && ch[i][yy11-1] != '#'){
                    yy11--;//区间上端点 
                }
                while(yy22 < m && ch[i][yy22+1] != '#'){
                    yy22++;//区间下端点 
                }
                for(register int k = yy11;k <= yy22;k++){
                    vis[i][k] = 1;
                }
                a2[++tot2] = ppp{i,yy11,yy22};
            }
        }
        for(register int i = 1;i <= tot1;i++){
            for(register int j = 1;j <= tot2;j++){
                if(a1[i].x <= a2[j].d && a1[i].y >= a2[j].d){
                    if(a2[j].x <= a1[i].d && a2[j].y >= a1[i].d){
                        if(ch[a2[j].d][a1[i].d] == '*') continue;//交点是草不能建边 
                        add(i,j);
                    }
                }
            }
        }

        for(register int i = 1;i <= tot1;i++){
            init();
            if(dfs(i)) sum++;
        }
        cout << "Case :" << ___ << endl;
        cout << sum << endl;
    }
    return 0;
}