P7407 题解

· · 题解

有 M 种可用的颜色，所以每次修改颜色时，一定能找到一种未被使用的颜色（剩余 M-1 条边无法取遍 M 种颜色），因此最优策略下，只要一条边经过了修改，那么之后就可以自由地使用这条边。

可以得出如下结论：一条边能被使用，当且仅当它被修改过或者当前节点相邻的其余所有同色边都被修改过。

首先，两次经过同一个节点是没有意义的（保持所有边的修改情况不变，删掉这个环即可）。同时我们发现，如果我修改了一条边同色的所有相邻边，然后沿着这条边走了一步，之后再走到那些被修改的边相邻的节点也是没有意义的（保持修改状态不变，这一步直接走过去即可）。

因此我们认为，修改即将要走过的边的操作是“好的”，因为这样修改之后可以减小后续操作的代价：下一步如果选择修改所有同色的相邻边，可以少修改一条；修改其余所有边的操作是“不好的”，因为这样操作无法减少后续操作的代价。

所以如果一个“不好的”操作的代价大于“好的”操作，就一定会选择好的操作。进而可以得出，一组同色边当中，只有权重大于一半的边可能会触发“不好的”操作——这样的边至多只有一条。

现在给每条边建立一个虚点 V'_i，表示修改了这条边并走过去；每个原来的点 V_i 代表将所有相邻边视为没有修改的情况。

假设存在一条 (u,v,c,w) 的边 i，那么从 V_u,V_v 向 V'_i 连边，权值为 w；从 V_i' 向 V_u,V_v 连边，权值为 0；从 V_u,V_v 向对方连有向边，权值为其余所有相邻同色边的权值之和。

最后一种情况：进行一个好操作之后，进行一个“不好的”操作，因为之前的操作可以少修改一条边。这样从 V'_i 向最大的相邻同色边连向的节点 V 连边，就可以处理这种情况。

最后跑一遍最短路就做完了，总复杂度 O(m\log m)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=300007;
ll n,m,dis[N],vis[N],U[N],V[N],col[N],w[N];
map<ll,ll> mp[N],mx1[N],mx2[N];
vector<pair<ll,ll> > to[N];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<> > pq;
void update(int u,int c,int i){
    if (mx1[u].find(c)==mx1[u].end()){
        mx1[u][c]=i;return;
    }
    if (w[mx1[u][c]]<w[i]){mx2[u][c]=mx1[u][c];mx1[u][c]=i;return;}
    if (mx2[u].find(c)==mx2[u].end()||w[mx2[u][c]]<w[i]) mx2[u][c]=i;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=m;++i){
        cin>>U[i]>>V[i]>>col[i]>>w[i];
        mp[U[i]][col[i]]+=w[i];
        mp[V[i]][col[i]]+=w[i];
        update(U[i],col[i],i);
        update(V[i],col[i],i);
    }
    for (int i=1;i<=m;++i){
        to[U[i]].emplace_back(n+i,w[i]);
        to[V[i]].emplace_back(n+i,w[i]);
        to[n+i].emplace_back(U[i],0);
        to[n+i].emplace_back(V[i],0);
        to[U[i]].emplace_back(V[i],mp[U[i]][col[i]]-w[i]);
        to[V[i]].emplace_back(U[i],mp[V[i]][col[i]]-w[i]);
        int p1=mx1[U[i]][col[i]],p2=mx2[U[i]][col[i]];
        if (i!=p1) to[n+i].emplace_back(U[p1]^V[p1]^U[i],mp[U[i]][col[i]]-w[p1]-w[i]);
        else if (p2) to[n+i].emplace_back(U[p2]^V[p2]^U[i],mp[U[i]][col[i]]-w[p2]-w[i]);
        p1=mx1[V[i]][col[i]],p2=mx2[V[i]][col[i]];
        if (i!=p1) to[n+i].emplace_back(U[p1]^V[p1]^V[i],mp[V[i]][col[i]]-w[p1]-w[i]);
        else if (p2) to[n+i].emplace_back(U[p2]^V[p2]^V[i],mp[V[i]][col[i]]-w[p2]-w[i]);
    }
    memset(dis,0x3f,sizeof(dis));dis[1]=0;
    pq.emplace(0,1);
    while(!pq.empty()){
        int u=pq.top().second;pq.pop();
        if (vis[u]) continue;
        vis[u]=1;
        for (auto p:to[u]) if (dis[p.first]>dis[u]+p.second){
//          assert(p.second>=0);
            pq.emplace(dis[p.first]=dis[u]+p.second,p.first);
        }
    }
    cout<<(dis[n]>1e17?-1:dis[n])<<endl;
    return 0;
}