2017乌鲁木齐网络赛 j 题

题目连接 : https://nanti.jisuanke.com/t/A1256

Life is a journey, and the road we travel has twists and turns, which sometimes lead us to unexpected places and unexpected people.

Now our journey of Dalian ends. To be carefully considered are the following questions.

Next month in Xian, an essential lesson which we must be present had been scheduled.

But before the lesson, we need to attend a wedding in Shanghai.

We are not willing to pass through a city twice.

All available expressways between cities are known.

What we require is the shortest path, from Dalian to Xian, passing through Shanghai.

Here we go.

Input Format

There are several test cases.

The first line of input contains an integer

For each test case, the first line contains an integer

Each of the following

The expressway connects two given cities and it is bidirectional.

Output Format

For eact test case, output the shortest path from Dalian to Xian, passing through Shanghai, or output

样例输入

3
2
Dalian Shanghai 3
Shanghai Xian 4
5
Dalian Shanghai 7
Shanghai Nanjing 1
Dalian Nanjing 3
Nanjing Xian 5
Shanghai Xian 8
3
Dalian Nanjing 6
Shanghai Nanjing 7
Nanjing Xian 8

样例输出

7
12
-1


题目大意是 ，给你两个地方中间的距离，让你从求西安到大连的最短路径，要求中途必须经过上海，而且每个点只能走一次。

啦啦啦  ：  刚刚和队友补题补到这里了，算是重现了一遍网络赛吧，刚刚学了网络流没几天这题就被我发现了，之前做过一道从1到N，再从N回到1，每个边只能走一次这个题，
莫名感觉有点像，直接开的网络流，我屁颠屁颠的跑去建图了，最后还是没出来，哎，我还是继续加油刷题吧。。。

题解 : 这道题确实是个网络流的题目，而且是个费用流，首先我们很容易想到，每个点只能走一次，拆点是必须的，拆成两个点，连一条线，流量为1 ，一个只能进，另一个只能出，
然后如何确定这个一定经过上海呢，先从西安跑到上海，在从上海跑到大连，如果真的想了就发现这个不对劲，首先网络流模型，反向边是个精髓，它可以反悔，然后你可能会把之前要走
的边反悔掉，第二次网络流导致从西安到上海走不了了，如果直接两边迪杰斯特拉的话，两个最短路加拆边很明显不一定是最小那样也错了，那么就要想别滴办法了，首先这题的图是无向的
那么我们先建立一个双向边之后，把上海作为起点，大连和西安连在新建里的汇点上，然后图就完事了。

AC代码：

#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
#define INFINITE 1 << 26
#define MAX_NODE 80005
#define MAX_EDGE_NUM 80005
typedef long long ll;
struct Edge{
    int to;
    int vol;
    int cost;
    int next;
};
Edge gEdges[MAX_EDGE_NUM];

int gHead[MAX_NODE];
int gPre[MAX_NODE];
int gPath[MAX_NODE];
int gDist[MAX_NODE];

int gEdgeCount;
void InsertEdge(int u, int v, int vol, int cost){
    gEdges[gEdgeCount].to = v;
    gEdges[gEdgeCount].vol = vol;
    gEdges[gEdgeCount].cost = cost;
    gEdges[gEdgeCount].next = gHead[u];
    gHead[u] = gEdgeCount++;

    gEdges[gEdgeCount].to = u;
    gEdges[gEdgeCount].vol = 0;         //vol为0，表示开始时候，该边的反向不通
    gEdges[gEdgeCount].cost = -cost;    //cost 为正向边的cost相反数，这是为了
    gEdges[gEdgeCount].next = gHead[v];
    gHead[v] = gEdgeCount++;
}

//假设图中不存在负权和环,SPFA算法找到最短路径/从源点s到终点t所经过边的cost之和最小的路径
bool Spfa(int s, int t){
    memset(gPre, -1, sizeof(gPre));
    memset(gDist, 0x7F, sizeof(gDist));
    gDist[s] = 0;
    queue<int> Q;
    Q.push(s);
    while (!Q.empty()){//由于不存在负权和环，因此一定会结束
        int u = Q.front();
        Q.pop();

        for (int e = gHead[u]; e != -1; e = gEdges[e].next){
            int v = gEdges[e].to;
            if (gEdges[e].vol > 0 && gDist[u] + gEdges[e].cost < gDist[v]){
                gDist[v] = gDist[u] + gEdges[e].cost;
                gPre[v] = u; //前一个点
                gPath[v] = e;//该点连接的前一个边
                Q.push(v);
            }
        }
    }

    if (gPre[t] == -1)  //若终点t没有设置pre，说明不存在到达终点t的路径
        return false;
    return true;
}

int MinCostFlow(int s, int t){
    int cost = 0;
    int flow = 0;
    while (Spfa(s, t)){
        int f = INFINITE;
        for (int u = t; u != s; u = gPre[u]){
            if (gEdges[gPath[u]].vol < f)
                f = gEdges[gPath[u]].vol;
        }
        flow += f;
        cost += gDist[t] * f;
        for (int u = t; u != s; u = gPre[u]){
            gEdges[gPath[u]].vol -= f;   //正向边容量减少
            gEdges[gPath[u]^1].vol += f; //反向边容量增加
        }
    }
    if(flow==2) return cost;
    else return -1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        memset(gHead,-1,sizeof(gHead));
        gEdgeCount=0;
        mp.clear();
        mp["Dalian"]=1;
        mp["Shanghai"]=2;
        mp["Xian"]=3;
        int ge=4;
        int n;
        scanf("%d",&n);
        int nn=n*2;
        for(int i=0;i<n;i++){
            string a,b;
            int c;
            cin>>a;
            cin>>b;
            cin>>c;
            if(!mp[a]) mp[a]=ge++;
            if(!mp[b]) mp[b]=ge++;
            if(mp[a]!=2&&mp[b]!=2){
                InsertEdge(mp[a]+nn,mp[b],1,c);
                InsertEdge(mp[b]+nn,mp[a],1,c);
            }
            else if(mp[a]==2){
                InsertEdge(mp[a],mp[b],1,c);
            }
            else{
                InsertEdge(mp[b],mp[a],1,c);
            }
        }
        for(int i=1;i<ge;i++){
            if(i!=2){
                InsertEdge(i,i+nn,1,0);
            }
        }
        int e=4*n;
        InsertEdge(1,e,1,0);
        InsertEdge(3,e,1,0);
        int dd=MinCostFlow(2,e);
        printf("%d
",dd);
    }
    return 0;
}