2017 - 喵呜的旅行
喵呜突然想去拜访许久不见的皮卡丘。电脑前面待久了，出去一趟总想游览一番。于是喵呜骑上他的草泥马自西向东（皮卡丘居住的城市在喵呜的东边）开始他的拜访之旅。
既然想游览当然想经过更多的城市，但是马粮又很贵，所以喵呜决定不经过同一个城市两次（除了喵呜所在城市），并且不走回头路（拜访皮卡丘的路上不往家的方向走，回家的路上不往皮卡丘家的方向走）！
为了简化问题，我们假定喵呜可能经过的城市自西向东排开。喵呜的家在最西边，皮卡丘的家在最东边。将城市自西向东，从1到N编号。
喵呜出发前用他6400+MHz的大脑心算出了结果。你知道喵呜最多能经过多少城市吗？
题目输入
多组测试数据
第1行两个正整数N（2<=N<=100），M（1<=M<=4950）。N表示有N个城市。
接下来M行每行两个正整数x,y（1<=x,y<=N）。表示编号x的城市和编号y的城市有路连通。
题目输出
一个正整数，喵呜能经过城市的最大值。如果找不到可行路径输出1。
输入/输出样例
题目输入
8 9 1 3 1 4 4 5 5 6 6 8 7 8 3 7 3 2 3 4
题目输出
7
提示
喵呜拜访皮卡丘并回到自己家才算可行路径。喵呜所在城市计算一次。
C++解答
#include <stdio.h> #include <string.h> #include <vector> #include <algorithm> using namespace std; vector<int> edge[105]; int dp[105][105]; int main() { int i,j,n,m,x,y,k; while(scanf("%d%d",&n,&m)!=EOF) { for (i=0;i<n;i++) { edge[i].clear(); } for (i=0;i<m;i++) { scanf("%d%d",&x,&y); x--;y--; edge[min(x,y)].push_back(max(x,y)); } memset(dp,-1,sizeof(dp)); dp[0][0]=1; for (i=0;i<n;i++) { for (j=0;j<n;j++) { if (dp[i][j]==-1) continue; if (i<=j) { for (k=0;k<edge[i].size();k++) { int e=edge[i][k]; if (e==j && e!=n-1) continue; dp[e][j]=max(dp[e][j],dp[i][j]+1); } } else { for (k=0;k<edge[j].size();k++) { int e=edge[j][k]; if (e==i && e!=n-1) continue; dp[i][e]=max(dp[i][e],dp[i][j]+1); } } } } if (dp[n-1][n-1]==-1) printf("1\n"); else printf("%d\n",dp[n-1][n-1]-1); } return 0; }
提示
喵呜拜访皮卡丘并回到自己家才算可行路径。喵呜所在城市计算一次。