洛谷 P2747 [USACO5.4]周游加拿大Canada Tour 题解【费用流】

点击量：150

    类似方格取数/吃豆豆一类的费用流。（我考试没想到。。。）

目录

题目描述

你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。除了旅行开始的城市之外，每个城市只能访问一次，因为开始的城市必定要被访问两次（在旅行的开始和结束）。

 

当然不允许使用其他公司的航线或者用其他的交通工具。

 

给出这个航空公司开放的城市的列表，和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线，这条路线必须满足上述条件，也就是从列表中的第一个城市开始旅行，访问到列表中最后一个城市之后再返回第一个城市。

 

输入输出格式

输入格式：

第1行: 航空公司开放的城市数N和将要列出的直达航线的数量V。N是一个不大于100的正整数。V是任意的正整数。

 

第2..N+1行: 每行包括一个航空公司开放的城市名称。城市名称按照自西向东排列。不会出现两个城市在同一条经线上的情况。每个城市的名称都 是一个字符串，最多15字节，由拉丁字母表上的字母组成；城市名称中没有空格。

 

第 N+2..N+2+V-1 行: 每行包括两个城市名称（由上面列表中的城市名称组成），用一个空格分开。这样就表示两个城市之间的直达双程航线。

 

输出格式：

Line 1: 按照最佳路线访问的不同城市的数量 M。如果无法找到路线，输出1。

输入输出样例

输入样例#1：

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

输出样例#1：

7

题解：

    因为不能有一个点被重复地经过，所以我们需要找到一条最大的包含起点和终点的“环”，而tarjan不能在复杂图中处理这种问题，因为整个双联通都会被缩点缩掉，不能直接用图论的方式来思考。

    而我们知道，路线能且仅能走两条且不相交。走两条就可以用流量为2的费用流来解，每跑一次计算n点的费用，最后算出最大费用即可。

    不过要注意一点，为了每个点只被经过一次，它可以被拆成两个点，从后面指向前面的边，流量为1，费用为1。剩下的图上的边流量可以设为∞，费用为0。最后从1号点的开头跑到n号点的开头就可以了。至于这样会少算最后一个点的问题，实际上是多算了第一个点一次。

Code：

#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#include<iostream>
using std::cin;
using std::map;
using std::swap;
using std::deque;
using std::string;
struct edge
{
    int n,v,w;
    int nxt;
    edge(int n,int v,int w,int nxt)
    {
        this->n=n;
        this->v=v;
        this->w=w;
        this->nxt=nxt;
    }
    edge(){nxt=-1;v=0;}
}e[100000];
int head[111],ecnt=-1;
void add(int from,int to,int v,int w)
{
    e[++ecnt]=edge(to,v,w,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,0,-w,head[to]);
    head[to]=ecnt;
}
map<string,int> num;
int n;
int dis[210],pre[210];
bool spfa()
{
    deque<int> q;
    q.push_back(1);
    int used[210];
    used[1]=1;
    memset(dis,-0x3f,sizeof(dis));
    memset(pre,-1,sizeof(pre));
    memset(used,0,sizeof(used));
    dis[1]=0;
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        used[k]=0;
        for(int i=head[k];~i;i=e[i].nxt)
            if(e[i].v&&dis[e[i].n]<dis[k]+e[i].w)
            {
                dis[e[i].n]=dis[k]+e[i].w;
                pre[e[i].n]=i;
                if(!used[e[i].n])
                {
                    used[e[i].n]=1;
                    if(q.empty()||dis[e[i].n]<dis[q.front()])
                        q.push_front(e[i].n);
                    else
                        q.push_back(e[i].n);
                }
            }
    }
    return dis[n]>=-1000000;
}
int main()
{
    memset(head,-1,sizeof(head));
    string s1,s2;
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        cin>>s1;
        num[s1]=i;
        if(i==1)
            add(i,n+i,2,1);//1号点流出流量为2
        else
            add(i,n+i,1,1);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>s1>>s2;
        if(num[s1]>num[s2])//从西到东
            swap(s1,s2);
        add(n+num[s1],num[s2],0x3fffffff,0);
    }
    int ans=0,sum=0;
    while(spfa())//增广
    {
        sum++;
        ans+=dis[n];
        int p=pre[n],minn=0x3fffffff;
        while(~p)
        {
            minn=minn<e[p].v?minn:e[p].v;
            p=pre[e[p^1].n];
        }

        p=pre[n];
        while(~p)
        {
            e[p].v-=minn;
            e[p^1].v+=minn;
            p=pre[e[p^1].n];
        }
    }
    if(sum==2)
        printf("%d\n",ans);
    else
        puts("1");
    return 0;
}