题解：P16565 [ICPC 2026 APC] Extra Transition

jch123 · 2026-11-10 17:30:01 · 题解

题意

一个无向图如果满足以下条件则是好的：对于每个 i 存在一条 1\to n 的简单路径，不存在 i,j 满足在两条 1\to n 的简单路径上先后顺序不同。首先判断这个图是否好，然后再判断有几对 (i,j) 满足 i,j 最开始没有边，添加一条边后图依旧是好的，求这样的 i,j 的 \sum w_iw_j。

思路

条件一等价于把 (1,n) 连上后点双连通，条件二等价于是一个串并联图（如果不满足条件二则有一个 (1,u),(u,n),(1,v),(v,n),(u,v) 的结构，严格强于 K_4）。

所以好图等价于以 1,n 为端点的串并联图，可以通过缩二度点和删重边最后剩下 (1,n) 来判断（注意有一度点就不合法了）。

对于第二问，如果是串联，那么可以连，每条边维护一个 sw 即可，合并 (x,u),(u,y) 时令 ans\gets ans+w_xsw_y+w_ysw_x+sw_xsw_y。对于并联，可以更新一次 ans\gets ans+w_x+w_y，由于不能再向外面连接，于是把 sw 置为 0 即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int N=2e5+10;
int w[N],vis[N],ans;
map<int,int> mp[N];
signed main()
{
    // freopen("transfer.in","r",stdin);
    // freopen("transfer.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        int n,m,fg=1;
        cin>>n>>m;
        ans=0;
        for(int i=1;i<=n;i++)
            cin>>w[i],mp[i].clear(),vis[i]=0;
        for(int i=1;i<=m;i++)
        {
            int u,v;
            cin>>u>>v;
            mp[u][v]=mp[v][u]=0;
        }
        queue<int> q;
        for(int i=2;i<n;i++)
            if(mp[i].size()==2) q.push(i);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            if(vis[u]||mp[u].size()!=2) continue;
            vis[u]=1;
            PII p1=*mp[u].begin(),p2=*next(mp[u].begin());
            int x=p1.first,sx=p1.second,y=p2.first,sy=p2.second;
            mp[u].clear(),mp[x].erase(u),mp[y].erase(u);
            ans+=sx*sy+w[x]*sy+w[y]*sx;
            if(mp[x].count(y)) mp[x][y]=mp[y][x]=0;
            else ans+=w[x]*w[y],mp[x][y]=mp[y][x]=sx+sy+w[u];
            if(x!=1&&x!=n&&mp[x].size()==2) q.push(x);
            if(y!=1&&y!=n&&mp[y].size()==2) q.push(y);
        }
        if(mp[1].size()!=1||mp[1].begin()->first!=n) fg=0;
        for(int i=2;i<n;i++)
            if(!vis[i]) fg=0;
        if(!fg) cout<<"bad\n";
        else cout<<ans<<'\n';
    }
    return 0;
}