题解：B3791 [信息与未来 2023] 电路布线

Nangu · 2024-03-31 09:26:11 · 题解

题目传送门

闲话：过了这道题后的好几个月，突然有人来问我这道题的解法，于是就有了这篇题解。

题意

给定一块 n\times m 的方格，其中一些格子必须铺线，一些格子不能铺线，另一些可铺可不铺。要求：

• 电线联通。
• 不形成回路。

题解

这道题大概有以下几种方法：

1. 超纲并且难写的轮廓线DP
2. 正解但是难写的折半搜索
3. 难写的随机乱搞做法

反正都很难写就对了。

我们从起点开始走起。

40分做法：

爆搜即可。枚举每一个方格内放/不放电线，并在最终进行判断是否合法。我们需要实现一个搜索函数和一个判断电线合法的函数:

bool dfs2(int x, int y, int prex, int prey){
    if(vis[x][y]) return 0;//有回路
    --cnt, vis[x][y]=1;
    for(auto [tx, ty]:d){
        tx+=x, ty+=y;
        if(tx==prex && ty==prey || tx<1 || ty<1 || tx>n || ty>m || t[tx][ty]!='+') continue;
        if(!dfs2(tx, ty, x, y)) return 0;
    }
    return 1;
}

void dfs(int x, int y, int tot){
    if(y==m+1) ++x, y=1;
    memset(vis, 0, sizeof vis);
    if(x==n+1){
        cnt=tot;//cnt表示总电线数减去搜索到的电线数；若cnt!=0，则该图不连通
        bool flag=0;
        if(tot>res && dfs2(sx, sy, -1, -1) && !cnt){
            memcpy(ans, t, sizeof t);
            res=tot;
        }
        return;
    }
    if(s[x][y]!='#'){
        t[x][y]='+';
        dfs(x, y+1, tot+1);
        t[x][y]=s[x][y];
    } 
    if(s[x][y]!='+') dfs(x, y+1, tot);
}

100分做法：

观察上述程序，我们发现有很多地方可以剪枝优化：

• 因为题目要求的是最大值，故若当前答案已经不可能成为了最大值，直接返回。
• 若一处有回路，则不管其他地方填不填电线都不影响此处回路。因此，每一次填电线时，我们就进行一次判断判断，若填此电线会造成回路，则直接返回。

改良后的代码：

bool dfs2(int x, int y, int prex, int prey){
    if(vis[x][y]) return 0;
    --cnt, vis[x][y]=1;
    for(auto [tx, ty]:d){
        tx+=x, ty+=y;
        if(tx==prex && ty==prey || tx<1 || ty<1 || tx>n || ty>m || t[tx][ty]!='+') continue;
        if(!dfs2(tx, ty, x, y)) return 0;
    }
    return 1;
}

void dfs(int x, int y, int tot){
    if(y==m+1) ++x, y=1;
    if(0.8*((n-x)*m+m-y+1)+tot<=res) return;//1
    memset(vis, 0, sizeof vis);
    if(x==n+1){
        cnt=tot;
        bool flag=0;
        if(dfs2(sx, sy, -1, -1) && !cnt){
            memcpy(ans, t, sizeof t);
            res=tot;
        }
        return;
    }
    if(s[x][y]!='#'){
        t[x][y]='+';
        if(dfs2(x, y, -1, -1)) //2
            dfs(x, y+1, tot+1);
        t[x][y]=s[x][y];
    } 
    if(s[x][y]!='+') dfs(x, y+1, tot);
}

于是，我们就用简洁好写的剪枝搜索通过了这道题。