题解 P2770 【航空路线问题】
辰星凌
2019-08-24 20:15:56
# **【题解】【网络流24题】航空路线问题 [P2770] [Loj6122]**
[更好的阅读体验](https://www.cnblogs.com/Xing-Ling/p/11405914.html)
**传送门:[航空路线问题 $[P2770]$](https://www.luogu.org/problem/P2770) [$[Loj6122]$](https://loj.ac/problem/6122)**
## **【题目描述】**
给出一张有向图,每个点(除了起点 $1$)每条边都只能经过一次,求出从 $1$ 到 $n$ 在回到 $1$ 的一条路径,使得经过的点个数最大,并输出路径。
**【数据范围】**
$100\%$ $n \leqslant 100$
-------
## **【分析】**
这是一道网络瘤题目。
那么,如何建模呢?
### **【建模】**
俗话说得好啊:**网络瘤,网络瘤,网络建模最毒瘤。**
稍微一不注意踩到了坑就 $GG$ 。
把题意转换一下,实际上是求从 $1$ 到 $n$ 的两条互不相交的路径。
限制条件是除起点、终点外的每条边、每个点只能经过一次,那么就可以进行**拆点**,把**点可以经过的最大次数**作为**点内部的流量**,**节点数**作为点**内部的费用**,最后用 $MCMF$ 求一个最大流最大花费。
求出的**最大流**就是**所找到的路径数**,如果它小于等于 $1$,就说明找不到这样一条路径。
但有一种特殊情况需要特判:起点、终点只有一条边相连,这时候虽然只能找到一条路径,可 $1$ 能直通 $n$ 并直接回来,是合法的路径。
然后就是 **美** $(sang)$ **妙** $(xin)$ **绝** $(bing)$ **伦** $(kuang)$ 的建图了:
首先把每个点拆为**入点**和**出点**,并连一条**流量**(**可经过次数**)为 $1$,费用(**节点数**)为 $1$ 的边,起点、终点要单独拆,**流量**设为 $2$ 。
而对于输入的边 $(x,y)$,要把 $x$ 的**出点**与 $y$ 的**入点**相连(其实是个很简单的道理,一开始死活想不明白,而大佬们的题解基本都没讲,可能是觉得太简单了吧,我太蒻了。。。)。
### **【求答案】**
答案分三种情况:
$(1).$ 当**最大流**等于 $2$ 时,**最大花费**减 $2$ 即为可经过的最大节点数,减 $2$ 是因为起点、终点都经过了两次。
$(2).$ 当处于上述 $1$ 直通 $n$ 的情况时,答案为 $2$,路径为:起点→终点→起点。
$(3).$ 其他情况均为无解。
另外,情况 $(1)$ 中输出路径时写两个 $dfs$ 遍历**满流边**:
第一次随便跑,记录下跑过的节点编号,要注意的是这时候只能跑出一条路,所以找到路后要立马 $break$。
第二次跳过这些节点找剩下那条路径,由于**最大流**(**所找到的路径数**)最多为 $2$,所以这里是否 $break$ 都无所谓(可能会快一丢丢吧)。
## **【Code】**
```cpp
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<queue>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=40000,inf=2e9;
int x,y,o=1,n,m,h,t,st,ed,flag,cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;string CH,ch[N];map<string,int>ip;
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
while(!Q.empty()){
Re x=Q.front();Q.pop();pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){//最长路
dis[to]=dis[x]+a[i].w,pre[to]=i;
cyf[to]=min(cyf[x],a[i].flow);//最小残余网络
if(!pan[to])pan[to]=1,Q.push(to);
}
}
return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
while(SPFA(st,ed)){
Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
while(x!=st){
Re i=pre[x];
a[i].flow-=cyf[ed];
a[i^1].flow+=cyf[ed];
x=a[i^1].to;
}
}
}
inline void dfs1(Re x){
pan[x]=1;//记录一下第一次选的点,第二次就不选它们了
cout<<ch[x-n]<<endl;//第一次正序输出。记得减n
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)<=n&&!a[i].flow){dfs1(to+n);break;}//出点x>n到入点to<=n,再从to的出点搜下去
}
inline void dfs2(Re x){
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)<=n&&!a[i].flow&&!pan[to+n])dfs2(to+n);//出点x>n到入点to<=n,再从to的出点搜下去
cout<<ch[x-n]<<endl;//第二次倒序输出。记得减n
}
int main(){
cin>>n>>m;st=1,ed=n<<1;
for(Re i=1;i<=n;++i)cin>>ch[i],ip[ch[i]]=i;
for(Re i=2;i<n;++i)add_(i,n+i,1,1);//1~n表示入点,n+1~2n表示出点
add_(1,1+n,2,1),add_(n,n+n,2,1);//起点和中点可以经过两次
while(m--){
cin>>CH;x=ip[CH];
cin>>CH;y=ip[CH];
if(x>y)swap(x,y);
flag|=x==1&&y==n;
add_(x+n,y,1,0);//刚从x的出点出来,接下来连到y的入点
}
EK(st,ed);
if(maxflow==2)printf("%d\n",maxcost-2);//找到了两条路
else if(maxflow==1&&flag){//只有一条从1直通n的边
printf("2\n");
cout<<ch[1]<<endl<<ch[n]<<endl<<ch[1]<<endl;//这里要输出三个
return 0;
}
else return !printf("No Solution!\n");
for(Re i=1;i<=n+2;++i)pan[i+n]=0;
dfs1(1+n),dfs2(1+n);//根据边的残余网络来判断是否选了该边,所以从出点开始搜,这里害我调了一个多小时
}
```