• <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>

            pku Telephone Lines 二分+最短路

            題意:
            一個無向帶權圖,要求將第1個節點與第n個節點聯通,求路徑中第p+1長邊。如果p>n,輸出0;如果不可能聯通,輸出-1

            解法:
            我的做法很搓。。二分+dij最短路,鄰接矩陣實現。復雜度高達10^7。。如果哪位神牛有更好的方法,請留言或者E-mail告訴我,謝謝
            具體做法如下:二分第p+1邊長度len,然后將圖的權值重置:如果g[i][j]<=len,則g[i][j]=0,否則g[i][j]=1。然后用dji求最短路。。如果1到n距離小于等于p,則返回true。

            代碼:
             1 # include <cstdio>
             2 # include <vector>
             3 # include <algorithm>
             4 # include <queue>
             5 # include <cstring>
             6 using namespace std;
             7 int n,p,k;
             8 vector<int>len;
             9 int g[1001][1001];
            10 int used[1001];
            11 bool visited[1001];
            12 void dfs(int pos)
            13 {
            14     if(used[pos]) return;
            15     used[pos]=true;
            16     for(int i=1;i<=n;i++)
            17         if(g[pos][i]!=-1)
            18             dfs(i);
            19 }
            20 bool chk(int l)
            21 {
            22     memset(used,-1,sizeof(used));
            23     memset(visited,0,sizeof(visited));
            24     used[1]=0;
            25     while(true)
            26     {
            27         int pos=-1,minnum=0xfffffff;
            28         for(int i=1;i<=n;i++)
            29             if(!visited[i]&&used[i]!=-1&&used[i]<minnum)
            30                 minnum=used[i],pos=i;
            31         if(pos==-1break;
            32         visited[pos]=1;
            33         for(int i=1;i<=n;i++)
            34             if(!visited[i]&&g[pos][i]!=-1&&(used[i]==-1||used[pos]+(g[pos][i]>l)<used[i]))
            35                 used[i]=used[pos]+(g[pos][i]>l);
            36     }
            37     return used[n]<=k;
            38 }
            39 int main() {
            40     scanf("%d%d%d",&n,&p,&k);
            41     memset(g,-1,sizeof(g));
            42     while(p--)
            43     {
            44         int a,b,value;
            45         scanf("%d%d%d",&a,&b,&value);
            46         if(g[a][b]==-1||g[a][b]>value)
            47             g[a][b]=g[b][a]=value;
            48         len.push_back(value);
            49     }
            50     sort(len.begin(),len.end());
            51     memset(used,0,sizeof(used));
            52     dfs(1);
            53     if(!used[n]) printf("-1\n");
            54     else
            55     {
            56         int s=0,e=len.size()-1;
            57         while(s<=e)
            58         {
            59             int mid=(s+e)>>1;
            60             if(chk(len[mid])) e=mid-1;
            61             else s=mid+1;
            62         }
            63         if(e==-1) printf("0\n");
            64         else printf("%d\n",len[e+1]);
            65     }
            66     return 0;
            67 }
            68 



            posted on 2010-11-27 11:40 yzhw 閱讀(148) 評論(0)  編輯 收藏 引用 所屬分類: graph

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久亚洲欧美日本精品| 蜜臀av性久久久久蜜臀aⅴ| 日日狠狠久久偷偷色综合96蜜桃| 午夜精品久久久久久中宇| 久久久久亚洲av综合波多野结衣| 无码AV中文字幕久久专区| 久久精品国产99国产电影网| 亚洲欧美日韩久久精品| 亚洲国产另类久久久精品小说| 国产成人99久久亚洲综合精品| 亚洲人成网亚洲欧洲无码久久| 国产一区二区精品久久岳| 久久精品一本到99热免费| 久久久久久狠狠丁香| 亚洲精品乱码久久久久久久久久久久 | 青青草原综合久久大伊人| 久久婷婷五月综合97色一本一本| 久久这里只精品99re66| 国产成人精品免费久久久久| 久久久久久极精品久久久| 一本一道久久精品综合| 一本色道久久综合亚洲精品| 久久久久九国产精品| 久久免费线看线看| 久久超乳爆乳中文字幕| 久久亚洲AV成人无码软件| 久久97久久97精品免视看秋霞| 亚洲成人精品久久| av午夜福利一片免费看久久| 中文字幕乱码久久午夜| 久久久久久国产a免费观看黄色大片 | 成人亚洲欧美久久久久 | 91精品国产91久久| 国产精品久久网| 国产成人精品久久免费动漫| 99久久国产热无码精品免费| 99精品国产99久久久久久97| 久久久久久综合网天天| 久久婷婷五月综合97色| 欧美精品一区二区精品久久 | 亚洲va久久久久|