Our Journey of Dalian Ends 乌鲁木齐网络赛最小费用最大流

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，费用0
在点之间加双向边，容量INF，费用为距离
在原点和Shanghai之间加边，容量2，费用0
在Dalian和Xian向终点加边，容量1，费用0

在这里注意每个点只过一次的条件不包括上海，也就是说上海入点和出点之间的容量要设置为2

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<deque>
#include<iomanip>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<functional>
#include<fstream>
#include<memory>
#include<list>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int MAXN = 100000;
const int MAXM = 3 * 100000 + 99;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int to, next, cap, flow, cost;
}edge[MAXM];
int head[MAXN], tol;
int pre[MAXN], dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init()
{
    //N = n;
    tol = 0;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int cap, int cost)
{
    edge[tol].to = v;
    edge[tol].cap = cap;
    edge[tol].cost = cost;
    edge[tol].flow = 0;
    edge[tol].next = head[u];
    head[u] = tol++;
    edge[tol].to = u;
    edge[tol].cap = 0;
    edge[tol].cost = -cost;
    edge[tol].flow = 0;
    edge[tol].next = head[v];
    head[v] = tol++;
}
bool spfa(int s, int t)
{
    queue<int>q;
    for (int i = 0; i < N; i++)
    {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow &&
                dis[v] > dis[u] + edge[i].cost)
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if (pre[t] == -1)return false;
    else return true;
}
//返回的是最大流，cost存的是最小费用
int minCostMaxflow(int s, int t, LL &cost)
{
    int flow = 0;
    cost = 0;
    while (spfa(s, t))
    {
        int Min = INF;
        for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to])
        {
            if (Min > edge[i].cap - edge[i].flow)
                Min = edge[i].cap - edge[i].flow;
        }
        for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to])
        {
            edge[i].flow += Min;
            edge[i ^ 1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}

int main()
{
    map<string, int> m;
    int T, cnt, dis;
    ios::sync_with_stdio(false);
    cin >> T;
    string f, t;
    while (T--)
    {
        init();
        int k;
        cin >> k;
        m.clear();
        cnt = 0;
        vector<pair<int, int>> v;
        vector<int> d;
        for (int i = 0; i < k; i++)
        {
            cin >> f >> t >> dis;
            if (m.find(f) == m.end())
            {
                m[f] = cnt++;
            }
            if (m.find(t) == m.end())
            {
                m[t] = cnt++;
            }
            v.push_back(make_pair(m[f], m[t]));
            d.push_back(dis);
        }
        if (m.find("Shanghai") == m.end() || m.find("Xian") == m.end() || m.find("Dalian") == m.end())
        {
            cout << -1 << endl;
            continue;
        }
        int p = m["Shanghai"];
        for (int i = 0; i < k; i++)
        {
            int _u = v[i].first, _v = v[i].second, _d = d[i];
            addedge(_u + cnt, _v, INF, _d);
            addedge(_v + cnt, _u, INF, _d);
        }
        for (int i = 0; i < cnt; i++)
        {
            if (i != p)
                addedge(i, i + cnt, 1, 0);
            else
                addedge(i, i + cnt, 2, 0);
        }
        int st = 2 * cnt, ed = 2 * cnt + 1;
        N = 2 * cnt + 2;
        int S = m["Shanghai"], X = m["Xian"], D = m["Dalian"];
        addedge(st, S, 2, 0);
        addedge(D + cnt, ed, 1, 0);
        addedge(X + cnt, ed, 1, 0);
        LL tmp;
        int ans = minCostMaxflow(st, ed, tmp);
        if (ans != 2)
            cout << -1 << endl;
        else
            cout << tmp << endl;
    }
}