[洛谷 2770]航空路线问题

题目链接

https://www.luogu.com.cn/problem/P2770

题解

我们的任务是在图上找两条只在起点和终点相交的路径。

将点 \(x\) 拆分成 \(x_1,x_2\)。对于除了起点和终点之外的其他点，连 \(x_1 \to x_2\)，流量为 \(1\)（只允许经过一次），费用为 \(0\) 的边。而对于起点和终点，连 \(x_1 \to x_2\)，流量为 \(2\)（要经过两次），费用为 \(0\) 的边。

对于 \(u \to v\) 这样一条路径，连一条 \(u_2 \to v_1\)，流量为 \(1\)，费用为 \(1\) 的边。

跑最大费用最大流即可。如果最大流等于 \(2\) 则有解。费用即为经过的城市数。

特别地，当最大流等于 \(1\) 时，可能存在一条 \(s \to t \to s\) 的路径，需要特判这种情况。

输出方案的话，直接在残量网络上 DFS 两次寻找路径即可。注意第二次 DFS 的时候需要倒序输出。

#include <cstring>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
map<string,int> m1;
map<int,string> m2;
struct edge
{
 int v,w,c,next;
}e[80005];
struct node
{
 int v,e;
}p[205];
int head[205],dis[205],vis[205];
int n,m,s,t,cnt=1,maxw,minf;
void addedge(int u,int v,int w,int c)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].c=c;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool spfa()
{
 queue<int> q;
 memset(dis,INF,sizeof(dis));
 dis[s]=0,vis[s]=1;
 q.push(s);
 while(!q.empty())
 {
  int u=q.front();
  q.pop();
  vis[u]=0;
  for(int i=head[u];i;i=e[i].next)
   if(e[i].w&&dis[u]-e[i].c<dis[e[i].v])
   {
    dis[e[i].v]=dis[u]-e[i].c;
    p[e[i].v].v=u;
    p[e[i].v].e=i;
    if(!vis[e[i].v])
    {
     vis[e[i].v]=1;
     q.push(e[i].v);
    }
   }
 }
 return dis[t]!=INF;
}
void dfs1(int u)
{
 vis[u]=1;
 cout<<m2[u-n]<<endl;
 for(int i=head[u];i;i=e[i].next)
  if(e[i].v<=n&&!e[i].w)
  {
   dfs1(e[i].v+n);
   break;
  }
}
void dfs2(int u)
{
 for(int i=head[u];i;i=e[i].next)
  if(e[i].v<=n&&!vis[e[i].v+n]&&!e[i].w)
   dfs2(e[i].v+n);
 cout<<m2[u-n]<<endl;
}
int main()
{
 bool flag=false;
 cin>>n>>m;
 s=1,t=2*n;
 for(int i=1;i<=n;i++)
 {
  string str;
  cin>>str;
  m1[str]=i;
  m2[i]=str;
  if(i==1||i==n)
  {
   addedge(i,i+n,2,0);
   addedge(i+n,i,0,0);
  }
  else
  {
   addedge(i,i+n,1,0);
   addedge(i+n,i,0,0);
  }
 }
 for(int i=1;i<=m;i++)
 {
  string s,t;
  cin>>s>>t;
  int u=m1[s],v=m1[t];
  if(u==1&&v==n)flag=true;
  addedge(u+n,v,1,1);
  addedge(v,u+n,0,-1);
 }
 while(spfa())
 {
  int minw=INF;
  for(int i=t;i!=s;i=p[i].v)
   minw=min(minw,e[p[i].e].w);
  for(int i=t;i!=s;i=p[i].v)
  {
   e[p[i].e].w-=minw;
   e[p[i].e^1].w+=minw;
  }
  maxw+=minw;
  minf+=minw*dis[t];
 }
 if(maxw!=2&&!flag)cout<<"No Solution!"<<endl;
 else if(maxw!=2&&flag)
 {
  cout<<2<<endl;
  cout<<m2[1]<<endl<<m2[n]<<endl<<m2[1]<<endl;
 }
 else
 {
  cout<<-minf<<endl;
  dfs1(n+1);
  dfs2(n+1);
 }
 return 0;
}