题解：P5683 [CSP-J2019 江西] 道路拆除

小陈同学cyh · 2024-12-23 19:26:14 · 题解

似乎dis本来就不用上下标吧

题意：

给定一个 n 个点 m 条边的无向图，问最多能删去多少边，能依旧使得 1 到 s1 的距离不大于 t1 并且 1 到 s2 的距离不大于 t2。

如果不能，输出 -1。

样例

思考

最后剩下的边一定构成一棵树，因为所有的环显然都是可以删掉至少一条边的，让我们来思考一下这棵树是什么形状吧。

结果：最后一定是三条链 1 \rightarrow x,x \rightarrow s1,x \rightarrow s2 答案就是 m-dis_{1,x}-dis_{x,s1}-dis_{x,s2} 了。

调整法证明：若存在 y 使得 dis_{1,y}+dis_{y,s1}+dis_{y,s2} 变小就用 y 代替 x 就好了。

注意枚举 x 时要做好初始化，用 bfs 可以轻松做到 O(n+m) 的单源最短路，一共枚举 n 次，且 n,m 同阶，时间复杂度显然是 O(n^2) 的。

核心代码

马蜂奇特

代码将 dis 压成了一维虽然这毫无作用

void addedge()
{
    int x=in(),y=in();
    cnt++;
    edge[cnt].to=y;
    edge[cnt].nextt=head[x];
    head[x]=cnt;
    cnt++;
    edge[cnt].to=x;
    edge[cnt].nextt=head[y];
    head[y]=cnt;
}
void bfs(int pos)
{
    for (int i=1;i<=n;i++) vis[i]=false,f[i]=1e9;
    f[pos]=0;p=1;q[p]=pos;last=1;vis[pos]=true;
    while (p<=last)
    {
        for (int i=head[q[p]];i;i=edge[i].nextt)
        {
            if (!vis[edge[i].to])
            {
                f[edge[i].to]=f[q[p]]+1;
                vis[edge[i].to]=true;
                last++;
                q[last]=edge[i].to;
            }
        }
        p++;
    }
}
signed main()
{
    n=in();m=in();
    for (int i=2;i<=n;i++) f[i]=-1;
    for (int i=1;i<=m;i++) addedge();
    s1=in();t1=in();s2=in();t2=in();
    bfs(1);
    for (int i=1;i<=n;i++) f1[i]=f[i];
    if (f[s1]>t1||f[s2]>t2)
    {
        cout<<-1;
        return 0;
    }
    for (int i=1;i<=n;i++)
    {
        bfs(i);
        if (f1[i]+f[s1]<=t1&&f1[i]+f[s2]<=t2) ans=min(ans,f1[i]+f[s1]+f[s2]);
    }
    cout<<m-ans;
    return 0;
}