杂题随笔 2024.10.25 两道图论

最近在写abc375这场，最后的F和G是两道很典的图论题。

https://atcoder.jp/contests/abc375/tasks/abc375_f
题意：大致就是说给你一张图，有两种操作：第一种操作是把第i条边删掉，第二种操作是询问u,v两点的最短路。
解法：这种题目印象里好像是考过几次了，把在线询问的顺序转变，倒着做，把减边变成加边操作然后再一步步用Floyd维护最短路即可。这道题的点的数量只有300.具体处理的细节就是先把操作给离线下来，那些没有涉及到操作的边就直接在预处理的时候就更新距离，涉及到操作的边再一步步用Floyd维护。
代码

const ll INF = 1e18;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<int> a(m),b(m),c(m);
    for(int i=0;i<m;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        a[i]--;
        b[i]--;
    }
    vector<int> o(q),x(q),y(q);
    vector<bool> bl(m);
    for(int i=0;i<q;i++)
    {
        cin>>o[i];
        if(o[i]==1)
        {
            cin>>x[i];
            x[i]--;
            bl[x[i]]=1;
        }
        else 
        {
            cin>>x[i]>>y[i];
            x[i]--;
            y[i]--;
        }
    }
    // cerr<<1<<'\n';
    vector dis(n,vector(n,INF));
    for(int i=0;i<n;i++)
    {
        dis[i][i]=0;
    }
    for(int i=0;i<m;i++)
    {
        if(!bl[i])
        {
            dis[a[i]][b[i]]=dis[b[i]][a[i]]=c[i];
        }
    }
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    // cerr<<1<<'\n';
    vector<ll> ans(q);
    for(int i=q-1;i>=0;i--)
    {
        if(o[i]==1)
        {
            int j=x[i];
            for(int x=0;x<n;x++)
            {
                for(int y=0;y<n;y++)
                {
                    dis[x][y]=min({dis[x][y],dis[x][a[j]]+c[j]+dis[b[j]][y],dis[x][b[j]]+c[j]+dis[a[j]][y]});
                }
            }
        }
        else 
        {
            ans[i]=dis[x[i]][y[i]];
        }
    }
    // cerr<<1<<'\n';
    for(int i=0;i<q;i++)
    {
        if(o[i]==2)
        {
            ll x=ans[i];
            if(x==INF)
            {
                cout<<-1<<'\n';
            }
            else 
            {
                cout<<ans[i]<<'\n';
            }
        }
    }
}

https://atcoder.jp/contests/abc375/tasks/abc375_g
题意：给出一张图，问拆掉第i条边会不会改变1到n的最短路。
解法：这种题好像也是常出的题。我们先分别以1和n为起点各自跑一遍Dij，然后去一步步筛选。如果一条边，他到1的最短路+他到n的最短路+他自己的权值=1到n的最短路，那么这条边就先被保存下来，其他不满足这个条件的边就没必要讨论了，全部都是No，因为肯定不会是在1到n的最短路上的。然后我们再考虑这些边，假如说当前遍历到的这条边是桥，那么肯定是Yes，否则是No。
代码：

#define maxn 200010
int n,m;
int a[maxn],b[maxn],c[maxn];
int d1[maxn],d2[maxn];
vector<PII> vec[maxn];
array<int,4> e[maxn];
vector<int> G[maxn];
int vis[maxn];
ll dis[maxn];
priority_queue<PII,vector<PII>,greater<PII> >que;
void dij(int st,int dis[])
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=1e18;
    }
    dis[st]=0;
    que.push({dis[st],st});
    while(!que.empty())
    {
        auto x=que.top().second;
        que.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(auto [to,val]:vec[x])
        {
            if(dis[to]>dis[x]+val)
            {
                dis[to]=dis[x]+val;
                que.push({dis[to],to});
            }
        }
    }
}
int dfn[maxn],low[maxn],idx;
map<PII,bool> mm;
void dfs(int now,int fa)
{
    dfn[now]=low[now]=++idx;
    for(auto to:G[now])
    {
        if(!dfn[to])
        {
            dfs(to,now);
            low[now]=min(low[now],low[to]);
            if(low[to]>dfn[now])
            {
                mm[{now,to}]=1;
                mm[{to,now}]=1;
            }
        }
        else if(to!=fa)
        {
            low[now]=min(low[now],dfn[to]);
        }
    }
}

vector<array<int,4> > ve;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        e[i]={a[i],b[i],c[i],i};
        vec[a[i]].push_back({b[i],c[i]});
        vec[b[i]].push_back({a[i],c[i]});
    }
    dij(1,d1);
    int dis=d1[n];
    for(int i=1;i<=n;i++)
    {
        vis[i]=0;
    }
    dij(n,d2);
    vector<int> ans(m+1,0);
    for(int i=1;i<=m;i++)
    {
        auto [u,v,w,id]=e[i];
        if(d1[u]+d2[v]+w==dis||d1[v]+d2[u]+w==dis)
        {
            G[u].push_back(v);
            G[v].push_back(u);
            ve.push_back(e[i]);
            // cerr<<1<<'\n';
        }
        else 
        {
            ans[i]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            dfs(i,0);
        }
    }
    for(auto [u,v,w,id]:ve)
    {
        // cerr<<mm[{u,v}]<<" ";
        if(mm[{u,v}])
        {
            ans[id]=1;
        }
        else 
        {
            ans[id]=0;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(ans[i])
        {
            cout<<"Yes"<<'\n';
        }
        else 
        {
            cout<<"No"<<'\n';
        }
    }


}