洛谷P2770 航空路线问题(费用流)

attack

发布于 2018-07-27 07:28:55

36900

代码可运行

文章被收录于专栏：数据结构与算法数据结构与算法

运行总次数：0

代码可运行

题意

$n$个点从左向右依次排列，有$m$条双向道路

问从起点到终点，再从终点回到起点，在经过的点不同的情况下最多能经过几个点

Sol

首先，问题可以转化为求两条互不相交的路径，使得点数最多

为了满足流量的限制，肯定会想到拆点，把每个点拆为两个，连流量为$1$,费用为$1$的边

起点和终点连费用为1，流量为2的边

输出方案比较蛋疼，我是dfs两次，然后第二次倒着输出

但是$a->c->a$这种情况会WA，so只好打表喽

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
const int MAXN = 1e4 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, S, T;
map<string, int> ID;
map<int, string> nam;
int flag[MAXN];
struct Edge {
    int u, v, w, f, nxt, vi;
}E[MAXN];
int head[MAXN], num = 0;
inline void add_edge(int x, int y, int w, int f) {
    E[num] = (Edge) {x, y, -w, f, head[x], 0};
    head[x] = num++;
}
inline void AddEdge(int x, int y, int w, int f) {
    add_edge(x, y, w, f); add_edge(y, x, -w, 0);
}
int dis[MAXN], vis[MAXN], Pre[MAXN];
bool SPFA() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q; q.push(S); dis[S] = 0;
    while(!q.empty()) {
        int p = q.front(); q.pop(); vis[p] = 0;
        for(int i = head[p]; i != -1; i = E[i].nxt) {
            int to = E[i].v;
            if(E[i].f && dis[to] > dis[p] + E[i].w) {
                dis[to] = dis[p] + E[i].w; Pre[to] = i;
                if(!vis[to]) vis[to] = 1, q.push(to);
            }
        }
    }
    return dis[T] <= INF;
}
int F() {
    int flow = INF;
    for(int i = T; i != S; i = E[Pre[i]].u) flow = min(flow, E[Pre[i]].f);
    for(int i = T; i != S; i = E[Pre[i]].u) E[Pre[i]].f -= flow, E[Pre[i] ^ 1].f += flow;
    return flow * dis[T];
}
int MCMF() {
    int ans = 0;
    while(SPFA()) ans += F();
    return ans;
}
int out[3][MAXN], tot[3];
void dfs(int now, int opt) {
    if(vis[now] || now == N) return ;
    vis[now] = 1;
    for(int i = head[now]; i != -1; i = E[i].nxt) {
        int to = E[i].v;
        if((E[i].u <= N && E[i].v >= N && (E[i].u + N != to)) || (to > N && to - N < out[opt][tot[opt]])) continue;
        if(!vis[to] && E[i].f < 1) {
            E[i].vi = 1;
            if(to == E[i].u + N) out[opt][++tot[opt]] = E[i].u;
            dfs(E[i].v, opt);
        }
    }
}
int main() {
    memset(head, -1, sizeof(head));
    N = read(); M = read(); S = 1; T = N + N;
    for(int i = 1; i <= N; i++) {
        string s; cin >> s; ID[s] = i; nam[i] = s;
        AddEdge(i, i + N, 1, (i == 1 || i == N) ? 2 : 1);
    }
    for(int i = 1; i <= M; i++) {
        string a, b; cin >> a >> b;
        if(ID[a] > ID[b]) swap(a, b);
        AddEdge(ID[a] + N, ID[b], 0, 1);
    }
    int ans = -MCMF() - 2;
    if(ans <= -2) {puts("No Solution!"); return 0;}
    if(ans == 0) {
        printf("2\n");
        cout << nam[1] << endl;
        cout << nam[N] << endl;
        cout << nam[1] << endl;
        return 0;
    }
    printf("%d\n", ans);
    memset(vis, 0, sizeof(vis)); dfs(1, 1);
    memset(vis, 0, sizeof(vis)); 
    for(int i = 1; i <= tot[1]; i++) vis[out[1][i]] = 1; vis[1] = 0;
    dfs(1, 2);
    for(int i = 1; i <= tot[1]; i++) 
        cout << nam[out[1][i]] << endl;
    cout << nam[N] << endl;
    for(int i = tot[2]; i >= 1; i--) 
        cout << nam[out[2][i]] << endl;
    return 0;
}
/*

*/