hdu 4460 第37届ACM/ICPC杭州赛区H题 STL+bfs

时间：2022-09-27 12:16:55

题意：一些小伙伴之间有朋友关系，比如a和b是朋友，b和c是朋友，a和c不是朋友，则a和c之间存在朋友链，且大小为2，给出一些关系，求出这些关系中最大的链是多少？

求最短路的最大距离

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt,dis[MAXN][MAXN];

 map<string,int> mp;

 vector<int> vc[MAXN];

 void bfs(int u)

 {

     queue<int> q;

     bool vis[MAXN];

     dis[u][u]=;

     cl(vis);

     int now,next;

     q.push(u);

     vis[u]=;

     while(!q.empty())

     {

         now=q.front();

         q.pop();

         int num=vc[now].size();

         for(int j=;j<num;j++)

         {

             next=vc[now][j];

             if(vis[next])  continue;

             dis[u][next]=dis[u][now]+;

             q.push(next);

             vis[next]=;

         }

     }

 }

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     while(scanf("%d",&n)!=EOF)

     {

         string s1,s2;

         cl(dis);

         if(n==)    break;

         for(i=;i<n;i++)

         {

             cin>>s1;

             mp[s1]=i;

         }

         for(int i=;i<n;i++)

         {

             dis[i][i]=;

             for(int j=i+;j<n;j++)

                 dis[i][j]=dis[j][i]=INF;

         }

         scanf("%d",&m);

         for(i=;i<n;i++)    vc[i].clear();

         while(m--)

         {

             cin>>s1>>s2;

             int t1=mp[s1];

             int t2=mp[s2];

             vc[t1].push_back(t2);

             vc[t2].push_back(t1);

         }

         for(i=;i<n;i++)    bfs(i);

         int ans=;

         for(i=;i<n;i++)

              for(j=i+;j<n;j++)

              {

                  ans=max(ans,dis[i][j]);

              }

         if(ans==INF)ans=-;

         printf("%d\n",ans);

     }

 }

相关文章