就记得f[1][1]的时候要初始化为1 忘了ans也要设为1 直接弄的0美滋滋
把它看作两个人同时从左边出发 然后dp就好了 可以去了gai一下floyd求最大环,最小环 和这题还是有点区别
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define rg register 5 const int N=100,M=60000; 6 int n,v,ans=1,mp[N+5][N+5],f[N+5][N+5]; 7 template <class t>void rd(t &x) 8 { 9 x=0;int w=0;char ch=0; 10 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 11 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 12 x=w?-x:x; 13 } 14 15 map<string,int>a; 16 17 int main() 18 { 19 //freopen("tour.in","r",stdin); 20 //freopen("tour.out","w",stdout); 21 rd(n),rd(v); 22 memset(f,0,sizeof(f)); 23 f[1][1]=1; 24 for(int i=1;i<=n;++i) {string x;cin>>x;a[x]=i;} 25 for(rg int i=1;i<=v;++i) 26 { 27 string x,y;cin>>x>>y; 28 int u=a[x],v=a[y]; 29 mp[u][v]=mp[v][u]=1; 30 } 31 for(rg int i=1;i<n;++i) 32 for(rg int j=i+1;j<=n;++j) 33 for(rg int k=1;k<j;++k) 34 if(f[i][k]&&mp[k][j]) 35 f[j][i]=f[i][j]=max(f[i][j],f[i][k]+1); 36 for(rg int i=1;i<=n;++i) 37 if(mp[i][n]) ans=max(f[i][n],ans); 38 printf("%d",ans); 39 return 0; 40 }