小可爱zzz绷不住逐步绷一眼秒的题 题解

· · 题解

前言

小可爱zzz一眼秒了，但是我不会做。

做法来源，我的语文成绩不怎么样，所以感觉那篇题解的说明有些难以断句。我在这里再总结一下做法。

做法

由于原图是平面图，很难不想到先建出对偶图。

这里我们从图的每个顶点引出一条射线，将无限面划分成 n 小块，这样保证了对偶图是一棵树。

考虑题目所求，两点间的最大流即为 两点之间两段弧所对应的 两组代表无限面的点的 最短路。

找一些性质。

考虑对偶图上 所有连接无限面和有限面的边中 边权最小的边，记这条边是 e。

这类边一定能找到 唯一 包含它的 边数最小的 一个环（这里指原图上的环），记其为 C。

那么有结论：所有最短路要么与 C 没有交，要么与 C 有交 而且经过 e。

可以感性理解一下。假设 s,t 引出的射线将图分成了上下两部分，而 e 在上部分，如图。

那么若最短路经过 C 且不经过 e，我们把 从 C 连向上半部分无限面的路径 替换成 e 即可。因为 e 是边权最小的连向无限面的边，所以一定不劣。

同时，由于边权非负，那么一个面一定不会被经过两次。这个结论就证完了。

考虑从原图上删除 e，并将 C 上其他边边权加上 e 的权值，形成一张新的图。

这里 在原图上删掉一条边 相当于 合并对偶图一条边连接的两个节点。

这里容易发现：

也就是说原图和新图上任一个点对，其最短路不变。那么我们直接删去这条边即可。这时 C 上的其他边就可能成为新的 e，继续删除最短的 e，直到图变为一棵树。此时点对间路径固定，使用 kruskal 重构树计算答案即可。

贴一下代码（应该可读）：

ai3 ed[400040];
vpi t[400040];
int deg[400040];
bool flg[400040],rm[400040];
pii pt[400040];
int cn[400040];
int n,m,c;

void ade(int u,int v,int w){t[u].eb(v,w),t[v].eb(u,w),pt[w]=mkp(u,v);}

void solve(int _Tid) {
    cin>>n>>m;
    for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,u>v&&(swap(u,v),0),ed[i]={u,v,w};
    // 建对偶图
    sort(ed+1,ed+m+1,[&](const ai3&a,const ai3&b){return a[1]^b[1]?a[1]<b[1]:a[0]>b[0];});
    vpi st;
    for(int i=1;i<=m;i++){
        ++c;
        while(st.size()&&ed[st.back().fi][0]>=ed[i][0])ade(st.back().se,c,st.back().fi),st.pop_back();
        st.eb(i,c);
    }
    ++c,ade(st.back().se,c,st.back().fi);
    for(int i=1;i<=c;i++)deg[i]=t[i].size();
    priority_queue<pii>pq;
    for(int i=1;i<=m;i++)if(ed[i][0]==ed[i][1]-1||ed[i][0]==1&&ed[i][1]==n)pq.emplace(-ed[i][2],i),cn[i]=1,flg[deg[pt[i].fi]==1?pt[i].fi:pt[i].se]=1;else cn[i]=2;
    // 不断删除一侧为无限面的边
    while(pq.size()){
        auto[w,id]=pq.top();
        pq.pop();
        if(!cn[id])continue;
        int u=flg[pt[id].fi]?pt[id].se:pt[id].fi;
        flg[u]=1,w=-w,rm[id]=1;
        for(auto[v,id]:t[u])ed[id][2]+=w,(--cn[id])&&(pq.emplace(-ed[id][2],id),0);
    }
    vector<ai3>vec;
    // 重构树计算答案
    for(int i=1;i<=m;i++)if(!rm[i])vec.pb({ed[i][2],ed[i][0],ed[i][1]});
    sort(all(vec),greater<>());
    DSU d(n+1,-1);
    ll res=0;
    for(auto[w,u,v]:vec)if(d.getfa(u)!=d.getfa(v))res+=(ll)d[d.getfa(u)]*d[d.getfa(v)]%mod*w%mod,d.merge(u,v);
    cout<<res%mod<<'\n';
}