本来想调剂心情没想到写了那么久，还被\(dreagonm\)神仙嘲讽不会传纸条，我真是太弱了\(QAQ\)（原因：最开始写最大费用最大流一直想消圈，最后发现自己完全是\(zz\)了）

这个题是最大费用最大流，避免正环的关键在于只从西向东连边。还有要注意题目中并没有说能任一点开始结束，所以必须是两条\(1->n\)的路线。

路径输出方法真的是学到了，看下面代码吧。还有注意只有\(1->n\)一条边的特判。

#include 
    
     using namespace std;const int N = 400010;const int M = 4000010;const int INF = 0x3f3f3f3f;int cnt = -1, head[N];struct edge {    int nxt, to, f, w;}e[M];void add_edge (int from, int to, int flw, int val) {    e[++cnt].nxt = head[from];    e[cnt].to = to;    e[cnt].f = flw;    e[cnt].w = val;    head[from] = cnt;}void add_len (int u, int v, int f, int w) {    add_edge (u, v, f, +w);    add_edge (v, u, 0, -w);}int n, m;map 
     
       mp;string s1, s2, str[110];int inn (int x) {return n * 0 + x;}int out (int x) {return n * 1 + x;}queue 
      
        q;int vis[N], dis[N], flow[N]; int pre_edge[N], pre_node[N], max_flow, max_cost;bool spfa (int s, int t) {    memset (vis, 0, sizeof (vis));    memset (dis, -0x3f, sizeof (dis));    memset (flow, 0x3f, sizeof (flow));    dis[s] = 0; vis[s] = true; q.push (s);    while (!q.empty ()) {        int u = q.front (); q.pop ();        for (int i = head[u]; ~i; i = e[i].nxt) {            int v = e[i].to;            if (dis[v] < dis[u] + e[i].w && e[i].f) {                dis[v] = dis[u] + e[i].w;                flow[v] = min (flow[u], e[i].f);                pre_edge[v] = i;                pre_node[v] = u;                if (!vis[v]) {                    vis[v] = true;                    q.push (v);                }            }         }        vis[u] = false;    }    return dis[t] != dis[0];}void dfs1 (int x) {    cout << str[x - n] << endl;//第一遍dfs正序输出    vis[x] = 1;//不让第二次dfs再找到这个点    for (int i = head[x]; ~i; i = e[i].nxt) {        if (e[i].to <= n && !e[i].f) {            dfs1 (e[i].to + n);            break;        }//第一次dfs只找一条路径，找到就break    }}void dfs2 (int x) {    vis[x - n] = 1;    for (int i = head[x]; ~i; i = e[i].nxt) {        if (e[i].to <= n && !e[i].f && !vis[e[i].to + n]) {            dfs2 (e[i].to + n);        }//不走第一次路径走过的点    }    cout << str[x - n] << endl;//第二次dfs倒序输出}//vis[n]在第一次dfs已经设为1，不会输出第二次int main () {    memset (head, -1, sizeof (head));    cin >> n >> m;    int s = n * 2 + 1;    int t = n * 2 + 2;    for (int i = 1; i <= n; ++i) {        cin >> str[i]; mp[str[i]] = i;        add_len (inn (i), out (i), 1, 1);    }    add_len (inn (1), out (1), 1, 0);    add_len (inn (n), out (n), 1, 0);    add_len (s, inn (1), 2, 0);    add_len (out (n), t, 2, 0);    bool have = false;    for (int i = 1; i <= m; ++i) {        cin >> s1 >> s2;        if (mp[s1] > mp[s2]) swap (s1, s2);        have |= (mp[s1] == 1 && mp[s2] == n);        add_len (out (mp[s1]), inn (mp[s2]), 1, 0);    }    max_flow = 0, max_cost = 0;    while (spfa (s, t)) {        max_flow += flow[t];        max_cost += dis[t] * flow[t];        int u = t;        while (u != s) {            e[pre_edge[u] ^ 0].f -= flow[t];            e[pre_edge[u] ^ 1].f += flow[t];            u = pre_node[u];        }    }    if (max_flow == 1 && have) {        cout << max_cost << endl;        cout << str[1] << endl << str[n] << endl << str[1] << endl;    } else if (max_flow == 2){        memset (vis, 0, sizeof (vis));        cout << max_cost << endl;        dfs1 (n + 1); dfs2 (n + 1);    } else puts ("No Solution!");}