网络流24题之十一 航空路线问题

填坑

<

div class=”content pre”>

模型

求最长两条不相交路径，用最大费用最大流解决。

实现

为了限制经过次数,将每个点i拆成xi,yi.

1、从xi向yi连一条容量为1,费用为1的有向边(1<i<N),
2、从x1向y1连一条容量为2,费用为1的有向边,
3、从xN向yN连一条容量为2,费用为1的有向边,
4、如果存在边(i,j)(i<j)从yi向xj连一条容量为1,费用为0的有向边.

求x1到yN的最大费用最大流.若(x1,y1)满流,则有解,答案为最大费用最大流-2;否则,无解.

分析

每条航线都是自西向东，本题可以转化为求航线图中从1到N两条不相交的路径，使得路径长度之和最大。转化为网络流模型，就是找两条最长的增广路。由于每个城市只能访问一次，要把城市拆成两个点，之间连接一条容量为1的边，费用设为1。因为要找两条路径，所以起始点和终点内部的边容量要设为2。那么费用流值-2就是两条路径长度之和，为什么减2，因为有两条容量为2的边多算了1的费用。求最大费用最大流后，如果(<1.a>,<1.b>)不是满流，那么我们找到的路径不够2条（可能是1条，也可能0条），所以无解。

代码：

#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <iostream>
#define M 10000
#define N 150
#define INF 0x33333333
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<int,int> Pair;
map <string,int>ma;
struct node{int from,to,next,flow,cost;}e[M];
int tot=-1,st[M];
int n,m,x,y,z;
int pe[N],pv[N],dis[N],vis[N];
void add(int x,int y,int z,int zz){
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].cost=zz;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z,int zz){add(x,y,z,zz),add(y,x,0,-zz);}
queue<int>que;
bool spfa(int S,int T)
{
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    que.push(S),vis[S]=1,dis[S]=0;
    while(!que.empty())
    {
        int now=que.front();que.pop();vis[now]=0;
        for (int i=st[now];~i;i=e[i].next)
            if (e[i].flow>0 && dis[e[i].to]<dis[now]+e[i].cost)
            {
                dis[e[i].to]=dis[now]+e[i].cost;
                pe[e[i].to]=i,pv[e[i].to]=now;
                if (!vis[e[i].to])
                    vis[e[i].to]=1,que.push(e[i].to);
            }
    }
    return dis[T];
}
int mfmc(int S,int T,int ans_flow)
{
    int COST=0,flow;
    while(ans_flow)
    {
        if (!spfa(S,T)) return -1;
        flow=ans_flow;
        for (int i=T;i!=S;i=pv[i])
            flow=min(flow,e[pe[i]].flow);
        COST+=flow*dis[T];
        ans_flow-=flow;
        for (int i=T;i!=S;i=pv[i])
            e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
    }
    return COST;
}
//为了限制经过次数,将每个点i拆成xi,yi.
//
//从xi向yi连一条容量为1,费用为1的有向边(1<i<N),
//从x1向y1连一条容量为2,费用为1的有向边,
//从xN向yN连一条容量为2,费用为1的有向边,
//如果存在边(i,j)(i<j)从yi向xj连一条容量为1,费用为0的有向边.
//
//求x1到yN的最大费用最大流.若(x1,y1)满流,则有解,答案为最大费用最大流-2;否则,无解.
string res[N];
int v[N];
int main()
{
    int m,from,to,cnt=0;
    scanf("%d%d",&n,&m);
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    string s,s1;
    for (int i=1;i<=n;i++)
        cin>>s,ma[s]=i,res[i]=s;
    for(int i=0;i<m;i++)
    {
        cin>>s>>s1;
        int l=ma[s],l1=ma[s1];
        if (l>l1)
            swap(l,l1);
        if (l==1&&l1==n)
            add_edge(l+n,l1,2,0);
        else
            add_edge(l+n,l1,1,0);
    }
    add_edge(1,1+n,2,1);
    add_edge(n,n+n,2,1);
    for (int i=2;i<n;i++)
        add_edge(i,i+n,1,1);
    int S=1,T=n+n;
    int ans=mfmc(S,T,2);
//    printf("%d %dn",ans.first,ans.second);
    if (ans==-1)
    {
        puts("No Solution!");
        return 0;
    }
    printf("%dn",ans-2);
    cout<<res[1]<<endl;
    for (int i=st[S+n],now,j;~i;i=e[i].next)
        if (!e[i].flow&&!(i&1))
        {
            now=e[i].to;
            while(now)
            {
                cout<<res[now]<<endl;
                v[now]=1;
                for (j=st[now+n],now=0;~j;j=e[j].next)
                    if (!e[j].flow&&!(j&1))
                    {
                        now=e[j].to;break;
                    }
            }
            break;
        }
    for (int i=st[T-n],now,j;~i;i=e[i].next)
        if (!e[i^1].flow&&(i&1)&&!v[e[i].to-n])
        {
            now=e[i].to-n;
            while(now)
            {
                cout<<res[now]<<endl;
                v[now]=1;
                for (j=st[now],now=0;~j;j=e[j].next)
                    if (!e[j^1].flow&&(j&1))
                    {
                        now=e[j].to-n;
                        break;
                     }
            }
            break;
        }
}