破坏道路

今天药忘吃喽~ 2022-06-11 04:56 324阅读 0赞

在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家的道路网络可以允许你从任意一个城市到达另外的城市。

现在你要破坏尽可能多的道路，但是要保证从城市s1到t1不超过l1小时，并且从城市s2到t2不超过l2小时。

输出最多可以破坏的道路数目，如果没有解，请输出-1

Input

单组测试数据。   
第一行有两个整数n,m(1 ≤ n ≤ 3000, n-1 ≤ m ≤ min(3000,n\*(n-1)/2) )。   
接下来m行，每行有两个整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)，表示ai和bi之间有一条道路。   
输入保证是一个连通图。   
最后两行每行有三个整数s1, t1, l1和 s2, t2, l2, (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n)。

Output

输出一个整数，表示最多可以破坏的道路数目，如果没有解，输出-1。

Sample Input

5 4
    1 2
    2 3
    3 4
    4 5
    1 3 2
    3 5 2

Sample Output

0

在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家的道路网络可以允许你从任意一个城市到达另外的城市。

现在你要破坏尽可能多的道路，但是要保证从城市s1到t1不超过l1小时，并且从城市s2到t2不超过l2小时。

输出最多可以破坏的道路数目，如果没有解，请输出-1

Input

单组测试数据。   
第一行有两个整数n,m(1 ≤ n ≤ 3000, n-1 ≤ m ≤ min(3000,n\*(n-1)/2) )。   
接下来m行，每行有两个整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)，表示ai和bi之间有一条道路。   
输入保证是一个连通图。   
最后两行每行有三个整数s1, t1, l1和 s2, t2, l2, (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n)。

Output

输出一个整数，表示最多可以破坏的道路数目，如果没有解，输出-1。

Sample Input

5 4
    1 2
    2 3
    3 4
    4 5
    1 3 2
    3 5 2

Sample Output

0

思路：先将两两之间的最短距离都求出来,然后将题目的s1到t1和s2到t2两个的最短距离加起来,注意这个只是两个最短距离的和，但不是最小的，因为还有可能有重复的路径他们都走过，所以还可以减去重复的才是最短的

#include<cstdio>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    const int inf=0x3f3f3f3f;
    vector<int>map1[3001];
    int dis[3001][3001];
    int vis[3001];
    int s1,t1,l1,s2,t2,l2;
    int n,m;
    void spfa(int x)
    {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            dis[x][i]=inf;
        dis[x][x]=0;
        queue<int>Q;
        Q.push(x);
        while(!Q.empty())
        {
            int u=Q.front();
            vis[u]=0;
            Q.pop();
            for(int i=0;i<map1[u].size();i++)
            {
                int v=map1[u][i];
                if(dis[x][v]>dis[x][u]+1)
                {
                    dis[x][v]=dis[x][u]+1;
                    if(vis[v]==0)
                    {
                        vis[v]=1;
                        Q.push(v);
                    }
                }
            }
        }
        return ;
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=1;i<=n;i++)
                map1[i].clear();
            for(int i=0;i<m;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                map1[x].push_back(y);
                map1[y].push_back(x);
            }
            scanf("%d%d%d%d%d%d",&s1,&t1,&l1,&s2,&t2,&l2);
            for(int i=1;i<=n;i++)
            spfa(i);
            if(dis[s1][t1]>l1||dis[s2][t2]>l2)
            {
                printf("-1\n");
                continue;
            }
            int ans=dis[s1][t1]+dis[s2][t2];//这里求的最短路径总和是没有去掉可能重复走过的路的
            for(int i=1;i<=n;i++)//这里就是找去掉重复了的路径的总和，例如:附在代码后面的那个样例,有重复的路径2--->4--->5
            {
                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(dis[s1][i]+dis[i][j]+dis[j][t1]+dis[s2][i]+dis[j][t2],ans);
                    }
                    if(dis[t1][i]+dis[i][j]+dis[j][s1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
                    {
                        ans=min(dis[t1][i]+dis[i][j]+dis[j][s1]+dis[s2][i]+dis[j][t2],ans);
                    }
                }
            }
            printf("%d\n",m-ans);
        }
        return 0;
    }
    /*
    9 9
    1 2
    2 3
    2 4
    4 5
    5 7
    5 6
    3 8
    8 9
    9 6
    1 7 4
    3 6 4
    */

发表评论取消回复

表情：

评论列表（有 0 条评论，324人围观）

还没有评论，来说两句吧...

相关阅读

相关 P2296-寻找道路

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

我会带着你远行/ 2023年06月01日 08:58/ 0 赞/ 110 阅读

相关 arcgis图形部分输出_ArcGIS制图—道路合并、道路冲突解决

![ac143af1396e6b81328989c1fb1a7324.gif][] 本文主要介绍在制图中对道路的处理技术：道路合并、道路冲突解决对于双线道路，在小比例

浅浅的花香味﹌/ 2023年01月01日 13:49/ 0 赞/ 567 阅读

相关单例模式的创建、破坏和防破坏

单例模式的创建、破坏和防破坏前言单例模式单例模式的几种实现方式懒汉式，线程不安全懒汉式，线程安全饿汉

「爱情、让人受尽委屈。」/ 2022年09月09日 11:43/ 0 赞/ 312 阅读

相关 X的追求道路

X的追求道路 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述 X在大家的帮助下终于找到了一个

r囧r小猫/ 2022年08月14日 05:36/ 0 赞/ 279 阅读

相关破坏道路

在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家的道路网络可以允许你从任意

今天药忘吃喽~/ 2022年06月11日 04:56/ 0 赞/ 325 阅读

相关结构化道路与非结构化道路

实际的道路一般可以分为结构化道路和非结构化道路两类：结构化道路一般是指高速公路、城市干道等结构化较好的公路，这类道路具有清晰的道路标志线，道路的背景环境比较单一，道路的

不念不忘少年蓝@/ 2022年06月02日 06:19/ 0 赞/ 385 阅读

相关算法七：道路升级

免费版：[算法七：道路升级][Link 1] 问题描述 Z国有 n 个城市和 m 条双向道路，每条道路连接了两个不同的城市，保证所有城市之间都可以通过这些道路互达。

喜欢ヅ旅行/ 2022年05月24日 06:59/ 0 赞/ 305 阅读

相关 [APIO2013]道路费用

[\[APIO2013\]道路费用 ][APIO2013] 给一些边确定权值，再找MST，还要最大化，很麻烦不妨枚举k中一个子集最终会在MST上，此基础上最大化每个边的权

我不是女神ヾ/ 2022年01月12日 10:47/ 0 赞/ 381 阅读

相关道路和航线

问题 B: 道路和航线时间限制: 1 Sec 内存限制: 128 MB 提交: 56 解决: 20 \[[提交][Link 1]\] \[[状态][L

末蓝、/ 2021年11月29日 13:32/ 0 赞/ 435 阅读

相关单例模式的破坏及任何防止被破坏

常用的单例模式有懒汉式、饿汉式两种情况。实际的应用场景也是很常见，好比如数据库连接池的设计，还有Windows的Task Manager（任务管理器）等。

太过爱你忘了你带给我的痛/ 2021年09月27日 13:58/ 0 赞/ 504 阅读