可以看成甲乙两个人同时从A点出发，经过不同的路径，到达B点的最长路径和。
设f[i,j]为甲走到第i座城市，乙走到第j座城市，路径的总和。
初始状态：f[1][1]=1；
转移方程：f[j, i ] = f[i,j] = max{f[i,k]+1} j,k间有路，1<=k<j
结果：ans = max{f[i,n]} i,n之有路
/**//*
ID: lorelei
TASK: tour
LANG: C++
*/
#include <fstream>
#include <string>
using namespace std;
const int MAX = 105;
const int INF = 0x7FFFFFF;
ifstream fin("tour.in");
ofstream fout("tour.out");
string city[105];
bool adj[MAX][MAX];
int n,v,ans;
inline int find(string str)
{
for(int i=1; i<=n; ++i)
if(str==city[i])
return i;
}
void input(){
int i;
fin>>n>>v;
for(i=1; i<=n; ++i)
fin>>city[i];
string s,t;
for(i=1; i<=v; ++i){
fin>>s>>t;
int v1 = find(s);
int v2 = find(t);
adj[v1][v2]=adj[v2][v1]=true;
}
}
int f[MAX][MAX];
void solve(){
f[1][1]=1;
for(int i=1; i<=n; ++i)
for(int j=i+1; j<=n; ++j){
f[i][j]=-INF;
for(int k=1; k<j; ++k){
if(adj[k][j] && f[i][k]>0 && f[i][k]>f[i][j])
f[i][j]=f[i][k];
}
f[j][i]= ++f[i][j];
}
}
void output(){
ans=1;
for(int i=1; i<n; ++i)
if(adj[i][n] && f[i][n]>ans)
ans=f[i][n];
fout<<ans<<endl;
}
int main(){
input();
solve();
output();
return 0;
}
posted on 2011-02-14 22:49
小阮 阅读(572)
评论(1) 编辑 收藏 引用 所属分类:
USACO