可以看成甲乙两个人同时从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之有路
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei
TASK: tour
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <string>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 105;
const int INF = 0x7FFFFFF;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin("tour.in");
ofstream fout("tour.out");
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
string city[105];
bool adj[MAX][MAX];
int n,v,ans;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline int find(string str)
{
for(int i=1; i<=n; ++i)
if(str==city[i])
return i;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void input()
{
int i;
fin>>n>>v;
for(i=1; i<=n; ++i)
fin>>city[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
string s,t;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=v; ++i)
{
fin>>s>>t;
int v1 = find(s);
int v2 = find(t);
adj[v1][v2]=adj[v2][v1]=true;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int f[MAX][MAX];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void solve()
{
f[1][1]=1;
for(int i=1; i<=n; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j=i+1; j<=n; ++j)
{
f[i][j]=-INF;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
input();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
solve();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
output();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2011-02-14 22:49
小阮 阅读(557)
评论(1) 编辑 收藏 引用 所属分类:
USACO