loj #6122. 「网络流 24 题」航空路线问题

#6122. 「网络流 24 题」航空路线问题

题目描述

给定一张航空图，图中顶点代表城市，边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

1. 从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可途经若干城市）。
2. 除起点城市外，任何城市只能访问一次。

对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。

输入格式

第一行有两个正整数 NNN 和 VVV，NNN 表示城市数，VVV 表示直飞航线数。
接下来的 NNN 行中每一行是一个城市名，可乘飞机访问这些城市。城市名出现的顺序是从西向东。也就是说，设 i,ji,ji,j 是城市表列中城市出现的位置次序，当 i>ji>ji>j 时，表示 城市 iii在城市 jjj 的东边，而且不会有两个城市在同一条经线上。城市名是一个长度不超过 151515 的字符串，串中的字符可以是大小写字母或阿拉伯数字。例如，AGR34\text{AGR34}AGR34 或 BEL4\text{BEL4}BEL4。
再接下来的 VVV 行中，每行有两个城市名，中间用空格隔开，如 city1 city2\text{city1 city2}city1 city2 表示 city1\text{city1}city1 到 city2\text{city2}city2 有一条直通航线，从 city2\text{city2}city2 到 city1\text{city1}city1 也有一条直通航线。

输出格式

输出最佳航空旅行路线。
第一行是旅行路线中所访问的城市总数 MMM。
接下来的 M+1M+1M+1 行是旅行路线的城市名，每行一个。首先是出发城市名，然后按访问顺序列出其它城市名。注意，最后一行（终点城市）的城市名必然是出发城市名。如果有多组最优解，输出任意一组均可；如果问题无解，则输出 No Solution!。

样例

样例输入

8 9

Vancouver

Yellowknife

Edmonton

Calgary

Winnipeg

Toronto

Montreal

Halifax

Vancouver Edmonton

Vancouver Calgary

Calgary Winnipeg

Winnipeg Toronto

Toronto Halifax

Montreal Halifax

Edmonton Montreal

Edmonton Yellowknife

Edmonton Calgary

样例输出

7

Vancouver

Edmonton

Montreal

Halifax

Toronto

Winnipeg

Calgary

Vancouver

数据范围与提示

对于所有数据，N<100N < 100N<100

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<queue>

#define maxn 110

using namespace std;

int dis[maxn],head[maxn],n,m,S,T,num=,ans;

bool v[maxn],vis[maxn];

map<string,int>p;

struct node{int to,pre,v,w;}e[maxn*maxn];

struct Node{int e,v;}pre[maxn*maxn];

string pp[maxn],s1,s2;

void Insert(int from,int to,int v,int w){

    e[++num].to=to;e[num].v=v;e[num].w=w;e[num].pre=head[from];head[from]=num;

    e[++num].to=from;e[num].v=;e[num].w=-w;e[num].pre=head[to];head[to]=num;

}

bool spfa(int x){

    memset(dis,,sizeof(dis));

    memset(vis,,sizeof(vis));

    queue<int>q;

    q.push(x);vis[x]=;

    while(!q.empty()){

        int now=q.front();q.pop();vis[now]=;

        for(int i=head[now];i;i=e[i].pre){

            int to=e[i].to;

            if(e[i].v>&&dis[now]+e[i].w>dis[to]){

                dis[to]=dis[now]+e[i].w;

                pre[to].e=i;pre[to].v=now;

                if(!vis[to]){vis[to]=;q.push(to);}

            }

        }

    }

    return dis[T];

}

int max_flow(int f){

    int res=,d;

    while(f){

        if(!spfa(S))return -;

        d=f;

        for(int i=T;i!=S;i=pre[i].v)d=min(e[pre[i].e].v,d);

        res+=d*dis[T];f-=d;

        for(int i=T;i!=S;i=pre[i].v){

            e[pre[i].e].v-=d;

            e[pre[i].e^].v+=d;

        }

    }

    return res;

}

int main(){

    scanf("%d%d",&n,&m);

    S=,T=n*;

    for(int i=;i<=n;i++){

        cin>>pp[i];

        p[pp[i]]=i;

    }

    for(int i=;i<=m;i++){

        cin>>s1>>s2;

        int a1=p[s1],a2=p[s2];

        if(a1>a2)swap(a1,a2);

        if(a1==&&a2==n)Insert(a1+n,a2,,);

        else Insert(a1+n,a2,,);

    }

    Insert(S,+n,,);

    Insert(n,T,,);

    for(int i=;i<n;i++)Insert(i,i+n,,);

    ans=max_flow();

    if(ans<){

        puts("No Solution!");

        return ;

    }

    printf("%d\n",ans-);

    cout<<pp[]<<endl;

    for(int i=head[S+n];i;i=e[i].pre)

        if(!e[i].v&&!(i&)){

            int to=e[i].to;

            while(to){

                cout<<pp[to]<<endl;

                v[to]=;

                int j;

                for(j=head[to+n],to=;j;j=e[j].pre)

                    if(!e[j].v&&!(j&)){

                        to=e[j].to;break;

                    }

            }

            break;

        }

    for(int i=head[T-n];i;i=e[i].pre)

        if(!e[i^].v&&(i&)&&!v[e[i].to-n]){

            int to=e[i].to-n;

            while(to){

                cout<<pp[to]<<endl;

                v[to]=;

                int j;

                for(j=head[to],to=;j;j=e[j].pre)

                    if(!e[j^].v&&(j&)){

                        to=e[j].to-n;break;

                    }

            }

            break;

        }

}