「网络流24题」航空路线问题-题解

题目传送门: 「Luogu P2770」航空路线问题

题目大意

给出一个城市,$n$个点,$v$条边,每个城市有一个名字
从西向东按序给出名字
求从最西出发到达最东并返回最西(除起点外,每个城市只能访问一次)的路径

题解

将每个城市拆成入点和出点

1. 源点为点1的入点,汇点为点n的出点
2. 对于 除源点汇点 的每个点, 从 入点 向 出点 建一条 容量为1,费用为1 的边(只能经过一次,且对答案贡献为1)
3. 从 点1的入点 向 点1的出点 建一条 容量为2,费用为1 的边(可以经过2次,且对答案贡献为1)
4. 从 点n的入点 向 点n的出点 建一条 容量为2,费用为1 的边(可以经过2次,且对答案贡献为1)
5. 对于边$<u, v>$, 从 u的出点 向 v的入点 建一条 容量为1,费用为0 的边(可经过1次,对答案无贡献)

求 最大费用最大流, 最大流$maxflow\leq 2$

1. 若最大流为$2$, 则会有一条道路, 经过的城市数为最大费用$maxcost-2$(减去重复的源点和汇点的贡献)
   求路径可以
   • 先一次dfs找到从1到n的所有残量为0的路径(满流$\mathtt{e.cap == e.flow}$),正序输出
   • 再一次dfs找到另一条满流路径,并用vis确保没有重复城市,倒序输出(不重复输出n)
2. 若最大流为$1$, 则直接从源点到汇点有一条通路, 输出$2$, 路径为$1->n->1$
3. 若最大流为$0$, 则无解$\texttt{No Solution!}$

代码

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch))  {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}

const int maxn = 210;
const int inf  = 0x3f3f3f3f;
const int ninf = 0xc0c0c0c0;

int n, m, s, t, ansflow;
int vis[maxn], d[maxn], p[maxn], a[maxn];
long long anscost;

struct Edge {
	int from, to, cap, flow, cost;
	Edge(int u, int v, int c, int f, int w): from(u), to(v), cap(c), flow(f), cost(w){}
};
vector<Edge> edges;
vector<int> G[maxn];
void add(int u, int v, int c, int w) {
	edges.push_back(Edge(u, v, c, 0, w));
	edges.push_back(Edge(v, u, 0, 0,-w));
	int mm = edges.size();
	G[u].push_back(mm - 2);
	G[v].push_back(mm - 1);
}

bool BellmanFord(int& flow, long long& cost) {
    memset(d, 0xc0, sizeof(d));
	memset(vis, 0, sizeof(vis));
	d[s] = 0; vis[s] = 1; p[s] = 0; a[s] = inf;
	queue<int> Q;
	Q.push(s);
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		vis[x] = 0;
		for (int i = 0; i < G[x].size(); ++i) {
			Edge& e = edges[G[x][i]];
			if (e.cap > e.flow && d[e.to] < d[x] + e.cost) {
				d[e.to] = d[x] + e.cost;
				p[e.to] = G[x][i];
				a[e.to] = min(a[x], e.cap - e.flow);
				if (!vis[e.to]) {
					Q.push(e.to);
					vis[e.to] = 1;
				}
			}
		}
	}
	if (d[t] == ninf) return false;
	flow += a[t];
	cost += (long long)d[t] * (long long)a[t];
	for (int u = t; u != s; u = edges[p[u]].from) {
		edges[p[u]].flow += a[t];
		edges[p[u] ^ 1].flow -= a[t];
	}
	return true;
}

int MinCostMaxFlow(long long& cost) {
	int flow = 0; cost = 0;
	while (BellmanFord(flow, cost));
	return flow;
}

string name[maxn];
map<string, int> id;

void dfs1(int u) {
    vis[u] = true;
    cout << name[u - n] << endl;
    for (int i = 0; i < G[u].size(); ++i) {
        Edge& e = edges[G[u][i]];
        if (e.to <= n && e.cap == e.flow) {
            dfs1(e.to + n);
            break;
        }
    }
}

void dfs2(int u) {
    for (int i = 0; i < G[u].size(); ++i) {
        Edge& e = edges[G[u][i]];
        if (e.to <= n && e.cap == e.flow && !vis[e.to + n]) {
            dfs2(e.to + n);
        }
    }
    cout << name[u - n] << endl;
}


int main() {
    n = read(); m = read();
    s = 1; t = 2 * n;
    for (int i = 1; i <= n; ++i) {
        cin >> name[i];
        id[name[i]] = i;
    }
    for (int i = 1; i <= m; ++i) {
        string str1, str2;
        cin >> str1;
        cin >> str2;
        int u = id[str1], v = id[str2];
        if (u > v) swap(u, v);
        add(u + n, v, 1, 0);
    }
    for (int i = 2; i < n; ++i) {
        add(i, i + n, 1, 1);
    }
    add(s, s + n, 2, 1); add(n, t, 2, 1);
    int maxflow = MinCostMaxFlow(anscost);
    if (maxflow == 2) {
        printf("%lld\n", anscost - 2);
    } else if (maxflow == 1) {
        printf("2\n");
        cout << name[1] << "\n" << name[n] << "\n" << name[1] << endl;
        return 0;
    } else {
        printf("No Solution!\n");
        return 0;
    }
    memset(vis, 0, sizeof(vis));
    dfs1(1 + n);
    dfs2(1 + n);
    return 0;
}