【luogu2747】 [USACO5.4]周游加拿大Canada Tour[动态规划]

就记得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 }