Codeforces543 B. Destroying Roads

传送门：>Here<

题意：给出一张无向图（边权为1），并给出两对起点和终点以及距离：s1,t1,l1; s2,t2,l2; 要求删除尽量多的边，使得dis(s1,t1)<=l1, dis(s2,r2)<=l2

解题思路

　　首先我们会发现，由于边权都为1，删去一些边，某两点间的最短路肯定会随着删的边越来越多而越来越长（捷径被删了）

　　因此我们会发现，要让边删的尽量多，最好最后只剩下最短路，其它边都剩下。换句话说，如果两条最短路不相交，那么最后只会剩下孤零零的两条链

　　于是我们会发现，我们可以初步得到一个答案：$M - d(s1,t1) - d(s2,t2)$

　　但这有可能不是最优的答案——两条最短路有可能有重叠。重叠的部分越长，答案就会越大也就是更优。并且很容易证明，重叠肯定只有连续的一段，而不会有间断的两断——因为如果需要有两断的话肯定不如连起来变为一段来的优。所以可以$O(n^2)$枚举重叠部分，验证一下就好了

Code

　　用SPFA预处理出任意两点间的距离，注意数组要开$N*N$

　　教训：当出现莫名其妙的错误的时候，首先检查数组有没有开错——例如，int开成bool，开得太小等等

/*By QiXingzhi*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define  r  read()

#define  Max(a,b)  (((a)>(b)) ? (a) : (b))

#define  Min(a,b)  (((a)<(b)) ? (a) : (b))

using namespace std;

typedef long long ll;

const int MAXN = ;

const int MAXM = ;

const int INF = ;

inline int read(){

    int x = ; int w = ; register int c = getchar();

    while(c ^ '-' && (c < '' || c > '')) c = getchar();

    if(c == '-') w = -, c = getchar();

    while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar(); return x * w;

}

int N,M,x,y,s1,t1,l1,s2,t2,l2,top,sp1;

int first[MAXM*],nxt[MAXM*],to[MAXM*],num_edge;

int d[MAXN][MAXN],inQ[MAXN],pre[MAXN],ans[MAXN],tmp[MAXN];

queue <int> q;

inline void add(int u, int v){

    to[++num_edge] = v;

    nxt[num_edge] = first[u];

    first[u] = num_edge;

}

inline void SPFA(int s, int c){

    for(int i = ; i <= N; ++i) d[i][c] = INF;

    memset(inQ, , sizeof(inQ));

    d[s][c] = ;

    q.push(s);

    int u,v;

    while(!q.empty()){

        u = q.front();q.pop();

        inQ[u] = ;

        for(int i = first[u]; i; i = nxt[i]){

            v = to[i];

            if(d[u][c] +  < d[v][c]){

                d[v][c] = d[u][c] + ;

                if(!inQ[v]){

                    inQ[v] = ;

                    q.push(v);

                }

            }

        }

    }

}

int main(){

//    freopen(".in","r",stdin);

    N=r,M=r;

    for(int i = ; i <= M; ++i){

        x=r,y=r;

        add(x, y), add(y, x);

    }

    s1=r,t1=r,l1=r;

    s2=r,t2=r,l2=r;

    for(int i = ; i <= N; ++i){

        SPFA(i, i);

    }

    if(d[s1][t1] > l1 || d[s2][t2] > l2){ printf("-1"); return ; }

    int Ans = M - d[s1][t1] - d[s2][t2];

    if(Ans < ) Ans = ;

    for(int i = ; i <= N; ++i){

        for(int j = ; j <= N; ++j){

            if(i == j) continue;

            if(d[s1][i] + d[j][t1] + d[i][j] <= l1){

                if(d[s2][i] + d[j][t2] + d[i][j] <= l2){

                    Ans = Max(Ans, M - (d[s1][i]+d[i][j]+d[j][t1]+d[s2][i]+d[j][t2]));

                }

                if(d[s2][j] + d[i][t2] + d[i][j] <= l2){

                    Ans = Max(Ans, M - (d[s1][i]+d[i][j]+d[j][t1]+d[s2][j]+d[i][t2]));

                }

            }

            if(d[s1][j] + d[i][t1] + d[i][j] <= l1){

                if(d[s2][i] + d[j][t2] + d[i][j] <= l2){

                    Ans = Max(Ans, M - (d[s1][j]+d[i][j]+d[i][t1]+d[s2][i]+d[j][t2]));

                }

                if(d[s2][j] + d[i][t2] + d[i][j] <= l2){

                    Ans = Max(Ans, M - (d[s1][j]+d[i][j]+d[i][t1]+d[s2][j]+d[i][t2]));

                }

            }

        }

    }

    printf("%d", Ans);

    return ;

}