Luogu P2770 航空路線問題

題目連結 \(Click\) \(Here\)

本來想調劑心情沒想到寫了那麼久，還被\(dreagonm\)神仙嘲諷不會傳紙條，我真是太弱了\(QAQ\)（原因：最開始寫最大費用最大流一直想消圈，最後發現自己完全是\(zz\)了）

這個題是最大費用最大流，避免正環的關鍵在于隻從西向東連邊。還有要注意題目中并沒有說能任一點開始結束，是以必須是兩條\(1->n\)的路線。

路徑輸出方法真的是學到了，看下面代碼吧。還有注意隻有\(1->n\)一條邊的特判。

#include <bits/stdc++.h>
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 <string, int> mp;

string s1, s2, str[110];

int inn (int x) {return n * 0 + x;}
int out (int x) {return n * 1 + x;}

queue <int> 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!");
}
                

轉載于:https://www.cnblogs.com/maomao9173/p/10511161.html