Destroying Roads CodeForces - 544D [最短路变形]

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

0

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

1

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

-1

题意:n(<=3000)个点,m条边,问最多能删多少条边,使得2个条件满足.如果一开始就不满足,输出-1

思路:边权都等于1,要求最多能删除多少条边,等价于最少用多少条边,最少用多少条边也就是最短距离和.bfs处理出多源最短路,O(n^2)暴力枚举重合的起点和终点.注意一下有4个判断即可. 有点像上面的题

#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define bug1 cout << "bug1" << endl
#define bug2 cout << "bug2" << endl
#define bug3 cout << "bug3" << endl
#define bug4 cout << "bug4" << endl
#pragma comment(linker, "/STACK:102400000,102400000")


using namespace std;
typedef long long ll;

const int MAX_N=3000+3;
vector <int> edge[MAX_N];
int dis[MAX_N][MAX_N],vis[MAX_N],n,m;
void bfs(int st){
    int vis[MAX_N];
    memset(vis,0,sizeof(vis));
    dis[st][st]=0;
    queue <int>q;
    q.push(st);
    while(!q.empty()){
        int v=q.front();q.pop();
        vis[v]=1;
        for(int i=0;i<edge[v].size();++i){
            int u=edge[v][i];
            if(vis[u])  continue;
            dis[st][u]=dis[st][v]+1;
            vis[u]=1;
            q.push(u);
        }
    }
    return ;
}
int main(void){
    cin >>n >> m;
    memset(dis,INF,sizeof(dis));
    for(int i=1;i<=n;i++)   dis[i][i]=0;
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i=1;i<=n;i++)   bfs(i);
    int s1,t1,l1,s2,t2,l2;
    cin >> s1 >> t1 >> l1 >> s2 >> t2 >> l2 ;
//    cout <<dis[s1][t1]<<"~"<<dis[s2][t2]<<endl;
    if(dis[s1][t1]>l1 || dis[s2][t2]>l2){

        cout <<"-1"<<endl;
        return 0;
    }

    int 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] +dis[s2][i]+dis[t2][j] < ans && dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][i]+dis[t2][j]+dis[i][j]<=l2)    ans=dis[s1][i]+dis[i][j]+dis[j][t1] +dis[s2][i]+dis[t2][j];
            if(dis[s1][i]+dis[i][j]+dis[j][t1] +dis[t2][i]+dis[s2][j] < ans && dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][j]+dis[t2][i]+dis[i][j]<=l2)    ans=dis[s1][i]+dis[i][j]+dis[j][t1] +dis[t2][i]+dis[s2][j];
            if(dis[t1][i]+dis[i][j]+dis[j][s1] +dis[t2][i]+dis[s2][j] < ans && dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][j]+dis[t2][i]+dis[i][j]<=l2)    ans=dis[t1][i]+dis[i][j]+dis[j][s1] +dis[t2][i]+dis[s2][j];
            if(dis[t1][i]+dis[i][j]+dis[j][s1] +dis[s2][i]+dis[t2][j] < ans && dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][i]+dis[t2][j]+dis[i][j]<=l2)    ans=dis[t1][i]+dis[i][j]+dis[j][s1] +dis[s2][i]+dis[t2][j];
        }
    }
//    printf("needmin=%d\n",ans);
    cout << m-ans << endl;
    return 0;
}