[CF 543B] Destroying Roads

作法：

破壞掉最多的路，也就是要留下最少的路。如果兩條最短路沒有相交，那麼顯然把其他邊都砍掉是最好的。而如果有相交的話，讓兩條最短路相交成 $H$ 字型會是最好的，因為如果兩條路徑重合的部份分成了很多段，那麼中間就會出現類似一個圈的東西（大概會長的像├O┤），那麼把中間那個圈改成只取比較短的那條就好了。因此只要枚舉兩個點當 $H$ 的中繼點，計算 $H$ 的總長就可以了。但這題有一些陷阱，首先是如果兩條路徑一模一樣的話不能去枚舉 $H$ 的兩個中繼點，否則長度會算到太長。還有必須把 $s2$ 和 $t2$ 交換再算一次，因為有可能當中繼點是 $i , j$ 時， $i$ 連到 $s1$ 和 $t2$ 是比較好的選擇。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=3000+10 ;
 
vector<int> v[maxn] ;
bool vis[maxn] ;
void BFS(int st,int *d)
{
    queue<int> q ;
    memset(vis,0,sizeof(vis)) ;
    q.push(st) ; vis[st]=1 ;
    d[st]=0 ;
    while(!q.empty())
    {
        int u=q.front() ; q.pop() ;
        for(auto i : v[u]) if(!vis[i])
            d[i]=d[u]+1 , vis[i]=1 , q.push(i) ;
    }
}
 
int n,d[maxn][maxn],t1,t2 ;
int solve(int s1,int e1,int s2,int e2)
{
    if(s1==s2 && e1==e2) return d[s1][e1] ;
    int ans=d[s1][e1]+d[s2][e2] ;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        if(d[s1][i]+d[i][j]+d[j][e1]<=t1 &&
           d[s2][i]+d[i][j]+d[j][e2]<=t2)
           ans=min(ans,d[s1][i]+d[i][j]+d[j][e1]+d[s2][i]+d[j][e2]) ;
    return ans ;
}
 
main()
{
    int m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=m;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
 
    for(int i=1;i<=n;i++) BFS(i,d[i]) ;
    int s1,e1 , s2,e2 ;
    scanf("%d%d%d%d%d%d",&s1,&e1,&t1,&s2,&e2,&t2) ;
    if(d[s1][e1]>t1 || d[s2][e2]>t2) {printf("-1\n") ; return 0;}
    printf("%d\n",m-min(solve(s1,e1,s2,e2),solve(s1,e1,e2,s2))) ;
}