题解：P17102 [ICPC 2017 Qingdao R] Our Journey of Xian Ends

· · 题解

题意简述

行程从西安出发，先到上海参加婚礼，再到青岛，最后返回上海浦东。除规定的上海换乘外，每个机场最多到达一次且最多离开一次。求全部航班的最小费用。

解题思路

先把完整行程拆成西安到上海、上海到青岛、青岛到上海三段。航线都是双向的，所以可以反转第二段。三段路便拥有统一的方向：一条从西安前往上海，两条从青岛前往上海。

不使用补偿换乘时，第一次经过上海必须在虹桥到达并从虹桥离开，最后在浦东到达。反转第二段后，三条路径分别为：

使用补偿换乘时，第一次从浦东到达上海，再由虹桥离开；第二次从虹桥到达，再前往浦东。反转第二段后，三条路径分别为：

因此，两种情况的起点多重集合都是「西安、青岛、青岛」。终点多重集合都是「虹桥、虹桥、浦东」。西安对应的流最终到达虹桥或浦东，恰好决定是否使用补偿，不会产生第三种行程。

用最小费用最大流同时选择这 3 条路径。对每个机场拆入点和出点，并从入点向出点连费用为 0 的边。普通机场的容量为 1，防止两条路径重复使用同一机场。青岛是两条路径的共同起点，虹桥可能是两条路径的共同终点，所以它们的容量为 2。

对每条双向航线，分别从一个机场的出点向另一个机场的入点连边。边的费用等于机票价格，容量取 3。再按照起点多重集合，从超级源向西安、青岛连容量为 1,2 的边；按照终点多重集合，从虹桥、浦东向超级汇连容量为 2,1 的边。

任意合法行程反转第二段后，都会在网络中形成 3 单位整数流。机场容量保证三条路径只在青岛和虹桥处按规定重复。反过来，将任意 3 单位整数流分解为三条路径，再恢复第二段方向。它必然落入上述两种上海行程之一。网络费用与机票费用逐边相同，所以最小费用流等于最优答案。若最大流不足 3，则不存在合法行程。

初始残量网络的正向边费用均非负。每次增广后，用势能把残量边重标为非负费用。然后用 Dijkstra 求下一条最短增广路。总流量仅为 3，所以时间复杂度为 O(E\log V)，空间复杂度为 O(V+E)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=40015;
const int M=10005;
const int E=80025;
const int inf=0x3f3f3f3f;
struct Edge
{
    int v,w,c;
}e[E];
int dis[N],h[N],pre[N],cnt,tot,last;
int x[M],y[M],co[M];
vector<int> G[N];
map<string,int> mp;
int get(const string &s)
{
    if(!mp.count(s))mp[s]=tot++;
    return mp[s];
}
void add(int u,int v,int w,int c)
{
    e[cnt]={v,w,c};
    G[u].push_back(cnt++);
    e[cnt]={u,0,-c};
    G[v].push_back(cnt++);
}
bool dijkstra(int s,int t,int n)
{
    fill(dis,dis+n,inf);
    priority_queue<pii,vector<pii>,greater<pii>> q;
    dis[s]=0;
    q.push({0,s});
    while(!q.empty())
    {
        auto [d,u]=q.top();
        q.pop();
        if(d!=dis[u])continue;
        for(auto i:G[u])
        {
            int v=e[i].v,nd=d+e[i].c+h[u]-h[v];
            if(e[i].w&&dis[v]>nd)
            {
                dis[v]=nd;
                pre[v]=i;
                q.push({nd,v});
            }
        }
    }
    if(dis[t]==inf)return 0;
    for(int i=0;i<n;i++)if(dis[i]!=inf)h[i]+=dis[i];
    return 1;
}
pii flow(int s,int t,int n)
{
    fill(h,h+n,0);
    int f=0,ans=0;
    while(f<3&&dijkstra(s,t,n))
    {
        int d=3-f,cost=0,u=t;
        while(u!=s)
        {
            d=min(d,e[pre[u]].w);
            cost+=e[pre[u]].c;
            u=e[pre[u]^1].v;
        }
        u=t;
        while(u!=s)
        {
            e[pre[u]].w-=d;
            e[pre[u]^1].w+=d;
            u=e[pre[u]^1].v;
        }
        f+=d;
        ans+=d*cost;
    }
    return {f,ans};
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=0;i<last;i++)G[i].clear();
        mp.clear();
        tot=0;
        int m;
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            string a,b;
            cin>>a>>b>>co[i];
            x[i]=get(a);
            y[i]=get(b);
        }
        int xa=get("Xian"),qd=get("Qingdao"),hq=get("Hongqiao"),pd=get("Pudong"),s=tot*2,t=s+1;
        last=t+1;
        cnt=0;
        for(int i=1;i<=m;i++)
        {
            add(x[i]+tot,y[i],3,co[i]);
            add(y[i]+tot,x[i],3,co[i]);
        }
        for(int i=0;i<tot;i++)add(i,i+tot,i==qd||i==hq?2:1,0);
        add(s,xa,1,0);
        add(s,qd,2,0);
        add(hq+tot,t,2,0);
        add(pd+tot,t,1,0);
        pii ans=flow(s,t,last);
        cout<<(ans.first==3?ans.second:-1)<<'\n';
    }
    return 0;
}