【【henuacm2016级暑期训练】动态规划专题 E】Destroying Roads

在这里输入题意

【题解】

首先。
这张图是无向无权图。
因此任意两点之间的最短路可以通过N^2的bfs轻易算出来。
即得到d[N+10][N+10]
考虑s[0]->t[0]的最短路以及s[1]->t[1]的最短路
如果d[s0][t0]>l0或d[s1][t1]>l1那么直接输出无解
假设他们俩的最短路之间没有重合的部分。
那么m-d[s0][t0]+d[s1][t1]就是答案。因为剩下两条最短路肯定最好的情况了。
删掉的肯定是最多的。
接下来考虑他们直接有交集的地方。如果有交集。
那么就是这个交集的路径的最短路。加上起点到这个路径的起点以及这个路径的终点到终点。
看看d[s0][i]+d[i][j]+d[j][t0]思路:

如果没有相交的部分。那么就是两个最短路。

如果有相交的部分。

那么就暴力枚举这个相交部分的两端(x,y)

看看是不是总边数更少且满足长度要求即可.

不可能有多个相交的部分的

因为如果是那样。中间不是相交的部分都走最短的就可以了。

那样更优。而那样。又变成一个整体的相交部分了

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 3e3;

int n,m,d[N+10][N+10],s[2],t[2],l[2];

vector<int> g[N+10];

queue<int> dl;

void bfs(int s){

    d[s][s] = 0;

    dl.push(s);

    while (!dl.empty()){

        int x = dl.front();

        dl.pop();

        for (int y:g[x]){

            if (d[s][y]==-1){

                d[s][y] = d[s][x]+1;

                dl.push(y);

            }

        }

    }

}

int main()

{

    #ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> m;

    for (int i = 1;i <= m;i++){

        int x,y;

        cin >> x >> y;

        g[x].push_back(y);

        g[y].push_back(x);

    }

    for (int i = 0;i <= 1;i++){

        cin >> s[i] >> t[i] >> l[i];

    }

    memset(d,255,sizeof d);

    for (int i = 1;i <= n;i++) bfs(i);

    if (d[s[0]][t[0]]>l[0] || d[s[1]][t[1]]>l[1]) return cout<<-1<<endl,0;

    int ans = d[s[0]][t[0]] + d[s[1]][t[1]];

    for (int i = 1;i <= n;i++)

        for (int j = 1;j <= n;j++)

            if (i!=j){

                if (d[s[0]][i]+d[i][j]+d[j][t[0]] <= l[0] && d[s[1]][i]+d[i][j]+d[j][t[1]] <=l[1])

                    ans = min(ans,d[s[0]][i]+d[s[1]][i]+d[i][j]+d[j][t[0]]+d[j][t[1]]);

                if (d[s[0]][i]+d[i][j]+d[j][t[0]] <= l[0]  && d[t[1]][i]+d[i][j]+d[j][s[1]] <=l[1])

                    ans = min(ans,d[s[0]][i]+d[t[1]][i]+d[i][j]+d[j][t[0]]+d[j][s[1]]);

            }

    cout<<m-ans<<endl;

    return 0;

}

巴特西

【【henuacm2016级暑期训练】动态规划专题 E】Destroying Roads

最新文章

热门文章