欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-09 20:16:40
题意 $n$个点从左向右依次排列,有$m$条双向道路 问从起点到终点,再从终点回到起点,在经过的点不同的情况下最多能经过几个点 Sol 首先,问题可以转化为求两条互不相交的路径,使得点数最多 为了满足流量的限制,肯定会想到拆点,把每个点拆为两个,连流量为$1$,费用为$1$的边 起点和终点连费用为1 ......

题意

$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;
}
/*

*/