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

## 题意

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

## Sol

```#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
const int MAXN = 1e4 + 10, INF = 1e9 + 10;
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];
inline void add_edge(int x, int y, int w, int f) {
E[num] = (Edge) {x, y, -w, f, head[x], 0};
}
inline void AddEdge(int x, int y, int w, int f) {
}
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() {
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的一个排列，按照某种顺序依次删

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

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

• ### 程序员进阶之算法练习（三十五）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...

• ### MCU SPI屏也能跑这么炫酷的特效？来，移植起来秀一秀

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

• ### 程序员面试金典 - 面试题 10.10. 数字流的秩（map/树状数组）

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

• ### 程序员进阶之算法练习（三十五）LeetCode专场

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