[XRCOI Round 1] C. 草萤有耀终非火 题解

· · 题解

Subtask 1

枚举哪些灯被点亮，暴力搜索和模拟即可。

Subtask 2

因为这两个点本来就存在燃料，所以直接将这两盏灯点亮即可，输出 2。

注意特判 m=1 的情况，此时 (1,1) 与 (1,m) 是同一个点，所以只点亮一盏即可，输出 1。

Subtask 3

因为没有灯在同一行同一列，所以一定点亮不了其他灯，无解，输出 -1 即可。

同样注意特判 m=1 的情况，此时若存在灯 (1,1) 则输出 1 即可。

Subtask 4

考虑同一列全部都有燃料意味着什么。观察发现，如果一行内有两列的灯同时被点亮，那么这两列在其他行的点亮情况一定相同。

这就启发了我们从行与列的角度去考虑问题，这一点同样可以从前两个部分分中得出，行与列是本题的一个关键点。

于是我们继续观察，可以发现，如果将整行和整列都抽象为图论中的节点，就很容易能够刻画他们之间的关系。则一个格点其实就充当了这个图中的无向边。例如，(a,b),(a,c),(d,b) 全部被点亮，就相当于连了 a\leftrightarrow b,a\leftrightarrow c ,d\leftrightarrow b 的无向边，那么此时 (d,c) 和其他三个点在同一个连通块里，就也会被点亮了。

由此通过中间的满列将旁边两列连接即可求出答案。

Subtask 5

连边之后，我们发现将 (1,1) 与 (1,m) 点亮，就相当于让第 1 行、第 1 列和第 m 列的节点处在一个连通块中。问题就变成加上最少的边，使得这三个点在同一连通块里，即求出他们的最小斯坦纳树。

但这个最小斯坦纳树有点特殊，它的边权是 1，并且只要使 3 个点连通，于是观察树的形态，发现树是一个从中转点向外发散的形态（即中转点到其他三个节点路径只有一个交点）。关于树的形态的证明具体参考：P6192 【模板】最小斯坦纳树。因此有一个暴力做法。

枚举中转点的位置，以该点为起点 BFS 一遍，最后求出该点到那三个点的最短距离之和即可。正确性显然，因为我们最终一定会找到一个点 s，使得 s 到另外三个点的最短路不相交，而对于相交的路径一定比 s 的答案大。

时间复杂度 O(t(n+m)^2)。

Subtask 6

因为是无向图，所以我们反过来考虑也是一样的，以那三个点为起点做 BFS，然后枚举中转点，在中转点处统计三个点到该点的距离之和，取最小值即可。

直接跑最小斯坦纳树也可以，但是没必要。

时间复杂度 O(t(n+m))。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,s,d[5][200005],ans;
vector<int>g[200005];
queue<int>q;
void bfs(int x,int y)
{
    bitset<200005>vis;
    q.push(x);
    vis[x]=1;
    d[y][x]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(auto v:g[u])
        {
            if(vis[v]==0)
            {
                vis[v]=1;
                d[y][v]=d[y][u]+1;
                q.push(v);
            }
        }
    }
}
void solve()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n+m;i++)
    {
        g[i].clear();
        d[1][i]=d[2][i]=d[3][i]=1e8;
    }
    ans=1e8;
    while(s--)
    {
        int u,v;
        cin>>u>>v;
        v+=n;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs(1,1);
    bfs(n+1,2);
    bfs(n+m,3);
    for(int i=1;i<=n+m;i++)ans=min(ans,d[1][i]+d[2][i]+d[3][i]);
    if(ans<1e8)cout<<ans<<'\n';
    else cout<<-1<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}