专栏首页数据结构与算法洛谷P2770 航空路线问题(费用流)

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

题意

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

*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ3295: [Cqoi2011]动态逆序对(cdq分治)

    对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删

    attack
  • BZOJ2754: [SCOI2012]喵星球上的点名(AC自动机)

    attack
  • P3368 【模板】树状数组 2 单点查询与区间修改

    题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数数加上x 2.求出某一个数的和 输入输出格式 输入格式: 第一行包含两个整数...

    attack
  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的边...

    落影
  • 图论--网络流--费用流POJ 2195 Going Home

    On a grid map there are n little men and n houses. In each unit time, every litt...

    风骨散人Chiam
  • MCU SPI屏也能跑这么炫酷的特效?来,移植起来秀一秀

    最近智能小车的项目还在加功能调试中,等后续调试完毕后更文。今天咱们就来分享一个在Github上看到的非常有意思的GUI开源项目。

    morixinguan
  • C++初始化

    Qt君
  • 程序员面试金典 - 面试题 10.10. 数字流的秩(map/树状数组)

    假设你正在读取一串整数。每隔一段时间,你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。

    Michael阿明
  • AtCoder Beginner Contest 100 完整解题报告

    https://beta.atcoder.jp/contests/abc100/tasks

    海天一树
  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的...

    落影

扫码关注云+社区

领取腾讯云代金券