POJ-1125 Stockbroker Grapevine---Floyd应用-白红宇

POJ-1125 Stockbroker Grapevine---Floyd应用

阅读量：6679 次

发布时间：2019-06-25

本文共 1686 字，大约阅读时间需要 5 分钟。

题目链接：

题目大意：

股票经纪人要在一群人中散布一个谣言，而谣言只能在亲密的人中传递，题目各处了人与人之间的关系及传递谣言所用的时间，要求程序给出应以那个人为起点，可以在最短的时间内让所有的人都得知这个谣言。要注意从a到b传递的时间不一定等于从b到a的时间，如果没有方案能够让每一个人都知道谣言，则输出"disjoint"。（有关图的连通性，你懂得！但好像不用考虑这种情况一样能AC，只能说测试数据有点小水！）

题目数据的输入第一行为n，代表总人数，当n=0时结束程序，接着n行，第i+1行的第一个是一个整数t，表示第i个人与t个人的关系要好，接着有t对整数，每对的第一个数是j，表示i与j要好，第二个数是从i直接传递谣言到j所用的时间，数据的输出是两个整数，第一个为选点的散布谣言的起点，第二个整数时所有人得知谣言的最短时间

思路：

Floyd直接求出每两点之间的时间，要求找到一个起点，那就遍历一遍起点u，每次取出最大值time = MAX{ Map[u][i] （i属于1-n）}，time就是以u为起点让其他所有人得知谣言的时间，然后求出time的最小值即可

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #include
             
              10 #include
              
               11 #define MEM(a, b) memset(a, b, sizeof(a));12 using namespace std;13 typedef long long ll;14 const int maxn = 200 + 10;15 const int INF = 0x3f3f3f3f;16 int T, n, m, cases, tot;17 int Map[maxn][maxn];18 19 int main()20 {21 while(cin >> n && n)22 {23 for(int i = 1; i <= n; i++)24 for(int j = 1; j <= n; j++)Map[i][j] = INF;25 for(int i = 1; i <= n; i++)//建图26 {27 cin >> m;28 int u = i, v, w;29 while(m--)30 {31 cin >> v >> w;32 Map[u][v] = w;//单向图33 }34 }35 for(int k = 1; k <= n; k++)//Floyd36 {37 for(int i = 1; i <= n; i++)38 {39 for(int j = 1; j <= n; j++)40 {41 Map[i][j] = min(Map[i][j], Map[i][k] + Map[k][j]);42 }43 }44 }45 int ans = INF;//最少的时间46 int ansi;47 for(int i = 1; i <= n; i++)48 {49 int time = 0;50 for(int j = 1; j <= n; j++)51 {52 if(i == j)continue;//如果i=j,应该直接下一个循环，不然最大值就变成Map[i][i]53 time = max(time, Map[i][j]);54 }55 if(ans > time)56 {57 ans = time;58 ansi = i;59 }60 }61 cout<
               
                <<" "<
                
                 <

转载于:https://www.cnblogs.com/fzl194/p/8733370.html

你可能感兴趣的文章