• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            AOJ--The Max Weight--Floyd Folyd算法變形,把求最短路徑的和改為求最大載重量的問題

            The Max Weight
            Time Limit: 1000 ms   Memory Limit: 64 MB
            Total Submission: 36   Accepted: 4
            Description
            There a lot of bridges connect different positions in Venice,but they can't carry too much weigh,so each of them has a limit which can be described as an interger.A man wants to carry some goods from positon 1 to n.Help him find how much can he carry.

            Input
            There are T cases.
            For each case,the number of positions ( 1 < = n < = 100) and number m of bridges are exhibited on the first line.The following m lines contain triples of integers specifying start and end positions of the bridge and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one bridge between each pair of crossings.

            Output
            The output for every scenario begins with a line containing "Case #i:", where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that the man can transport. Terminate the output for the scenario with a blank line.

            Sampel Input
            1
            3 3
            1 2 3
            1 3 4
            2 3 5 

            Sample Output
            Case #1:[EOL]
            4[EOF]

            題意:
            n個點,有些點間有橋,橋上有最大承重量,問你從1到n可以最大攜帶的物品的重量。
            題解: 
             Folyd算法變形,把求最短路徑的和改為求最大載重量的問題,關鍵是dis[i][j]=dis[i][j]>dis[i][k]+dis[k][j]?dis[i][j]>dis[i][k]+dis[k][j]?:dis[i][j];換成dis[i][j]=max(dis[i][j],min(dis[i][k],dis[k][j]));
             1#include<iostream>
             2#include<cmath>
             3#include<string.h>
             4using namespace std;
             5long long dis[105][105];
             6 
             8void Floyd(int n)
             9{
            10     for(int k=1; k<=n; k++)
            11     for(int i=1; i<=n; i++)
            12     for(int j=1; j<=n; j++)
            13     {
            14       if(i!=k&&j!=k&&dis[i][k]&&dis[k][j])
            15         dis[i][j]=max(dis[i][j],min(dis[i][k],dis[k][j]));
            16     }

            17}

            18
            19int main()
            20{
            21    int t,i,j,m,n;
            22    cin>>t;
            23    for(int k=1; k<=t; k++)
            24    {
            25      cin>>n>>m;
            26      memset(dis,0,sizeof (dis));
            27      i=1;
            28      for(int s,e,w; i<=m; i++)
            29      {
            30        cin>>s>>e>>w;
            31        dis[s][e]=dis[e][s]=w;
            32      }

            33      
            34      Floyd(n);
            35      
            36     cout<<"Case #"<<k<<':'<<endl<<dis[1][n]<<endl<<endl;
            37    }

            38    return 0;
            39}

            posted on 2010-05-29 22:03 田兵 閱讀(1453) 評論(0)  編輯 收藏 引用 所屬分類: 圖論題

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            综合久久一区二区三区| 国产精品国色综合久久| 久久av高潮av无码av喷吹| 久久亚洲国产精品123区| 久久久国产99久久国产一| 精品综合久久久久久97超人| 麻豆久久| 99精品久久精品一区二区| 久久这里只精品99re66| 九九精品99久久久香蕉| 久久久噜噜噜久久中文字幕色伊伊| 国产成人无码精品久久久性色 | 久久久久久极精品久久久| 欧美亚洲国产精品久久| 久久久久国产精品| 久久青青草原精品国产| 久久久久亚洲?V成人无码| 国产精品久久久久久久久| 久久婷婷色综合一区二区| 国内精品久久久久久久亚洲| 久久精品国产99久久无毒不卡| 久久国产香蕉视频| 久久91精品综合国产首页| 国产精品久久久久9999| 精品久久久久久无码中文字幕一区 | 91精品国产高清久久久久久io| 婷婷久久五月天| 久久性生大片免费观看性| 99久久精品国产一区二区三区| 久久精品国产亚洲AV香蕉| 亚洲乱码精品久久久久..| 武侠古典久久婷婷狼人伊人| 久久青青草原亚洲av无码| 久久性生大片免费观看性| 亚洲国产天堂久久久久久| 久久久精品久久久久久| 午夜精品久久久内射近拍高清| 亚洲伊人久久综合影院| 狠狠色丁香婷婷久久综合五月| 亚洲伊人久久成综合人影院 | 97久久精品人妻人人搡人人玩|