本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-07-16 19:57:33

题目说明

给定m条边，问从首都到城市1和城市2在限定时间内最多拆除道路数。如果无解输出-1。

题目解法

这道题可以反过来想，可以先求出至少需要多少条路。这就成了一个最短路问题，最大的麻烦是两条路可能会重合，这里就需要使用枚举每一个点作为中间点mid。首都到城市1总距离就等于(1 -> mid) + (mid -> s1)，到城市二则为(1 -> mid) + (mid -> s2)，然后判断这是不是所有结果中最小的，这样，最难得部分就处理完了。接下来最少道路数使用 dij 或 bfs 求即可。

Dijkstra:

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int dis[100005],dis2[100005],dis3[100005],head[100005],cnt,n,m,s1,t1,s2,t2,inf=0x3f3f3f3f;
bool vis[100005];
struct EDGE
{
    int to,nxt,val;
}edge[100005];
void add_edge(int u,int t,int v=1)
{
    edge[++cnt].to=t;
    edge[cnt].val=v;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
void dij(int start)\/\/可爱的dij
{
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    priority_queue< pair<int,int> > que;
    que.push(make_pair(0,start));\/\/dij永远配小根堆
    dis[start]=0;
    while(!que.empty())
    {
        int u = que.top().second;
        que.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i = head[u];i;i=edge[i].nxt)
        {
            int to = edge[i].to;
            if(dis[to] > dis[u]+edge[i].val)\/\/经典的松弛
            {
                dis[to]=dis[u]+edge[i].val;
                que.push(make_pair(-dis[to],to));\/\/小根堆永远是符号加入
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i <= m;i++)
    {
        int u,t;
        cin>>u>>t;
        add_edge(u,t);
        add_edge(t,u);
    }
    cin>>s1>>t1>>s2>>t2;
    dij(s1);
    for(int i = 1;i <= n;i++)dis2[i]=dis[i];
    dij(s2);
    for(int i = 1;i <= n;i++)dis3[i]=dis[i];
    dij(1);\/\/从起始点到每个点的最少需要道路数
    int ans=inf;
    for(int i = 1;i <= n;i++)
    {
        if(dis[i]+dis2[i] <= t1&&dis[i] + dis3[i] <= t2)\/\/如果满足要求
        {
            ans=min(ans,dis[i]+dis2[i]+dis3[i]);
        }
    }
    if(ans!=inf)
    {
        cout<<m-ans<<endl;\/\/总道路数减去需要道路数就是拆除道路数
        return 0;
    }
    cout << -1<<endl;
    return 0;
}

BFS:

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int dis[100005],dis2[100005],dis3[100005],head[100005],cnt,n,m,s1,t1,s2,t2,inf=0x3f3f3f3f;
bool vis[100005];
struct EDGE
{
    int to,nxt,val;
}edge[100005];
void add_edge(int u,int t,int v=1)
{
    edge[++cnt].to=t;
    edge[cnt].val=v;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
void bfs(int start)\/\/可爱的BFS
{
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    queue<int> que;
    que.push(start);\/\/即使是BFS，我也要用它 
    dis[start]=0;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i = head[u];i;i=edge[i].nxt)
        {
            int to = edge[i].to;
            if(dis[to]>dis[u]+1)
        	{
        		dis[to]=dis[u]+1;
			}
            que.push(to);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i <= m;i++)
    {
        int u,t;
        cin>>u>>t; 
        add_edge(u,t);
        add_edge(t,u);
    }
    cin>>s1>>t1>>s2>>t2;
    \/*千万不要用指针这个sb，它坑死我了*\/
    bfs(s1);
    for(int i = 1;i <= n;i++)dis2[i]=dis[i];
    bfs(s2);
    for(int i = 1;i <= n;i++)dis3[i]=dis[i];
    bfs(1);\/\/从起始点到每个点的最少需要道路数
    int ans=inf;
    for(int i = 1;i <= n;i++)
    {
        if(dis[i]+dis2[i] <= t1&&dis[i] + dis3[i] <= t2)\/\/如果满足要求
        {
            ans=min(ans,dis[i]+dis2[i]+dis3[i]);
        }
    }
    if(ans!=inf)
    {
        cout<<m-ans<<endl;\/\/总道路数减去需要道路数就是拆除道路数
        return 0;
    }
    cout << -1<<endl;
    return 0;
}

到此，本题就做完了！