CF543B Destroying Roads

@Pelom  November 11, 2019

题意

在这个国家有$n$个城市,城市间由$m$条双向公路连接。城市被编号为$1$到$n$ 。如果城市$a$和$b$被公路连接,那么你可以双向通行。你可以在这个公路网上通过公路从一个城市移动到另一个城市。走过每条公路均耗时$1$小时
你想要破坏最多的公路,但是破坏后必须满足从指定城市$s_1$ 到$t_1$最短不超过$l_1$小时,且从指定城市$s_2$到$t_2$最短不超过$l_2$​ 小时
计算在符合条件的情况下能破坏的最多公路数量。如果无论如何都无法满足条件,输出$−1$

数据范围:$1 \le n \le 3000,n−1 \le m \le min(3000,\frac{n(n−1)}{2})$

题解

对于两条最短路,可能会有一段重叠的部分
那么枚举这段的起点,求总路径最短

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=3000+10;
int n,m,u,v,s1,t1,l1,s2,t2,l2;
int cnt,ans;
int head[N];
int dis[N][N];
bool vis[N];
struct edge{
    int nxt,to;
} e[N*N>>1];
queue<int> Q;
inline void add(int u,int v){
    e[++cnt]=(edge){head[u],v};
    head[u]=cnt;
}
void bfs(int s){
    memset(vis,0,sizeof(vis));
    dis[s][s]=0;
    vis[s]=1;
    Q.push(s);
    for(;!Q.empty();){
        int u=Q.front();
        Q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(vis[v])
                continue;
            if(dis[s][v]>dis[s][u]+1){
                dis[s][v]=dis[s][u]+1;
                Q.push(v);
                vis[v]=1;
            }
        }
    }
}
int main(){
    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    scanf("%d%d%d%d%d%d",&s1,&t1,&l1,&s2,&t2,&l2);
    for(int i=1;i<=n;i++)
        bfs(i);
    if(dis[s1][t1]>l1 || dis[s2][t2]>l2){
        puts("-1");
        return 0;
    }
    ans=dis[s1][t1]+dis[s2][t2];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1 && dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
                ans=min(ans,dis[s1][i]+dis[i][j]+dis[j][t1]+dis[s2][i]+dis[j][t2]);
            if(dis[s1][j]+dis[i][j]+dis[i][t1]<=l1 && dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
                ans=min(ans,dis[s1][j]+dis[i][j]+dis[i][t1]+dis[s2][i]+dis[j][t2]);
        }
    printf("%d",m-ans);
    return 0;
}

添加新评论