USACO 5.4.2 tour

题目：

http://ace.delos.com/usacoprob2?a=0H14tt2CoyP&S=tour

http://pingce.ayyz.cn:9000/usaco/data/20110129214306/tour.html

Canada Tour

You have won a contest sponsored by an airline. The prize is a ticket to travel around Canada, beginning in the most western point served by this airline, then traveling only from west to east until you reach the most eastern point served, and then coming back only from east to west until you reach the starting city. No city may be visited more than once, except for the starting city, which must be visited exactly twice (at the beginning and the end of the trip). You are not allowed to use any other airline or any other means of transportation.

Given a list of cities served by the airline and a list of direct flights between pairs of cities, find an itinerary which visits as many cities as possible and satisfies the above conditions beginning with the first city and visiting the last city on the list and returning to the first city.

PROGRAM NAME: tour

INPUT FORMAT

Line 1:	The number N of cities served by the airline and the number V of direct flights that will be listed. N will be a positive integer not larger than 100. V is any positive integer.
Lines 2..N+1:	Each line contains a name of a city served by the airline. The names are ordered from west to east in the input file. There are no two cities in the same meridian. The name of each city is a string of, at most, 15 digits and/or characters of the Latin alphabet; there are no spaces in the name of a city.
Lines N+2..N+2+V-1:	Each line contains two names of cities (taken from the supplied list), separated by a single blank space. This pair is connected by a direct, two-way airline flight.

SAMPLE INPUT (file tour.in)

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

OUTPUT FORMAT

Line 1:

The number M of different cities visited in the optimal itinerary. Output 1 if no itinerary is possible.

SAMPLE OUTPUT (file tour.out)

Namely: Vancouver, Edmonton, Montreal, Halifax, Toronto, Winnipeg, Calgary, and Vancouver (but that's not a different city).

题解：

　　好题！！！问题抽象为找两条不相交路径。

　　做法一：DP。类似于传纸条，双进程DP，写起来不是很难。

　　做法二：网络流。将每个点拆点，起点和终点拆点之后内部流量限制为2来保证只找两条路，然后费用流即可。

View Code

  1 /*
  2 ID:zhongh1
  3 PROB:tour
  4 LANG:C++
  5 */
  6 
  7 #include<cstdio>
  8 #include<cstdlib>
  9 #include<cstring>
 10 #include<queue>
 11 #include<string>
 12 #include<iostream>
 13 
 14 using namespace std;
 15 
 16 const int maxn=1009;
 17 const int maxm=100000;
 18 const int INF=123456789;
 19 
 20 int en,m,n,ans,d[maxn],e,s,f[maxn],flow;
 21 
 22 bool use[maxn];
 23 
 24 string name[maxn],name1,name2;
 25 
 26 struct edge
 27 {
 28     int e,f,d;
 29     edge *next,*op;
 30 }*v[maxn],ed[maxm];
 31 
 32 queue<int> que;
 33 
 34 void add_edge(int s,int e,int f,int d)
 35 {
 36     en++;
 37     ed[en].next=v[s];v[s]=ed+en;v[s]->e=e;v[s]->f=f;v[s]->d=d;
 38     en++;
 39     ed[en].next=v[e];v[e]=ed+en;v[e]->e=s;v[e]->f=0;v[e]->d=-d;
 40     v[s]->op=v[e];v[e]->op=v[s];
 41 }
 42 
 43 bool bfs()
 44 {
 45     memset(d,0x3f,sizeof(d));
 46     d[s]=0;
 47     use[s]=true;
 48     que.push(s);
 49     memset(f,-1,sizeof(f));
 50     while (que.size())
 51     {
 52         int now=que.front();
 53         use[now]=false;
 54         que.pop();
 55         for (edge *e=v[now];e;e=e->next)
 56             if (e->f && d[e->e]>d[now]+e->d)
 57             {
 58                 d[e->e]=d[now]+e->d;
 59                 f[e->e]=now;
 60                 if (!use[e->e])
 61                 {
 62                     que.push(e->e);
 63                     use[e->e]=true;
 64                 }
 65             }
 66     }
 67     return f[e]!=-1;
 68 }
 69 
 70 int dfs(int now,int cur_flow)
 71 {
 72     if (now==e) return cur_flow;
 73     int rest=cur_flow;
 74     for (edge *e=v[now];e;e=e->next)
 75         if (e->f && f[e->e]==now)
 76         {
 77             int new_flow=dfs(e->e,min(e->f,rest));
 78             e->f-=new_flow;
 79             e->op->f+=new_flow;
 80             rest-=new_flow;
 81             ans+=new_flow*e->d;
 82         }
 83     return cur_flow-rest;
 84 }
 85 
 86 void dinic()
 87 {
 88     while (bfs())
 89         flow+=dfs(s,INF);
 90 }
 91 
 92 int main()
 93 {
 94     freopen("tour.in","r",stdin);
 95     freopen("tour.out","w",stdout);
 96 
 97     scanf("%d%d",&n,&m);
 98     for (int a=1;a<=n;a++)
 99         cin>>name[a];
100     for (int a=1;a<=m;a++)
101     {
102         cin>>name1>>name2;
103         for (int b=1;b<=n;b++)
104             if (name[b]==name1)
105             {
106                 for (int c=1;c<=n;c++)
107                     if (name[c]==name2)
108                     {
109                         if (b<c) add_edge(b+n,c,1,0);
110                         else add_edge(c+n,b,1,0);
111                         break;
112                     }
113             }
114     }
115     for (int a=2;a<n;a++)
116         add_edge(a,a+n,1,-1);
117     add_edge(1,n+1,2,0);
118     add_edge(n,2*n,2,0);
119     s=1;
120     e=2*n;
121     dinic();
122     if (flow<2) printf("1\n");
123     else printf("%d\n",-ans+2);
124 
125     return 0;
126 }