51nod

分析

首先做一个转化:最多破坏等于最少不破坏。

还有一个显然的性质是,两条路径只会有一段重叠部分。

因此可以 $\mathcal{O}(n^2)$ 枚举重叠部分,然后判断是否合法并更新答案即可。

这样需要预处理两两之间的最短路,因为边权全部为 $1$,BFS 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=3000+10;

int n,m,s1,t1,l1,s2,t2,l2;

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dis[N][N];
inline void bfs(int s) {
    queue<int> Q; Q.push(s); dis[s][s]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (dis[s][v]==-1) dis[s][v]=dis[s][u]+1,Q.push(v);
        }
    }
}

inline int d(int s,int i,int j,int t) {
    return dis[s][i]+dis[i][j]+dis[j][t];
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    memset(dis,-1,sizeof(dis));
    for (re int i=1;i<=n;++i) bfs(i);
    s1=read(),t1=read(),l1=read();
    s2=read(),t2=read(),l2=read();
    if (dis[s1][t1]>l1||dis[s2][t2]>l2) { puts("-1"); return 0; }
    int ans=dis[s1][t1]+dis[s2][t2];
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j) {
            if (d(s1,i,j,t1)<=l1&&d(s2,i,j,t2)<=l2)
                ans=min(ans,d(s1,i,j,t1)+d(s2,i,j,t2)-dis[i][j]);
            if (d(s1,i,j,t1)<=l1&&d(s2,j,i,t2)<=l2)
                ans=min(ans,d(s1,i,j,t1)+d(s2,j,i,t2)-dis[i][j]);
        }
    printf("%d\n",m-ans);
    return 0;
}
最后修改:2020 年 03 月 14 日 05 : 19 PM