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

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久久久久青草大香综合精品| 久久精品成人免费看| 91精品国产高清久久久久久io| 久久婷婷五月综合97色直播| 伊人久久大香线焦综合四虎| 99久久精品国产一区二区蜜芽| 久久精品国产亚洲AV不卡| 亚洲精品乱码久久久久久蜜桃 | 欧美va久久久噜噜噜久久| 日韩人妻无码一区二区三区久久| 人妻精品久久无码专区精东影业| 久久久老熟女一区二区三区| 色综合色天天久久婷婷基地| 久久精品无码一区二区三区免费| 久久人妻无码中文字幕| 99久久国产综合精品网成人影院| 国产成人精品综合久久久久| 青青草国产成人久久91网| 久久久亚洲裙底偷窥综合| 久久99精品国产麻豆蜜芽| 亚洲级αV无码毛片久久精品| 欧美日韩中文字幕久久久不卡| 亚洲AV日韩AV天堂久久| 久久天天躁狠狠躁夜夜av浪潮| 999久久久免费精品国产| 精品久久久久久无码人妻热| 国产亚洲欧美成人久久片| 欧美大香线蕉线伊人久久| 亚洲精品WWW久久久久久| 狠狠人妻久久久久久综合蜜桃 | 日本国产精品久久| 国内精品伊人久久久久av一坑| 久久久久se色偷偷亚洲精品av| 久久精品国产72国产精福利| 一本大道加勒比久久综合| 久久精品夜夜夜夜夜久久| 狠狠色婷婷久久一区二区| 久久精品国产亚洲av麻豆图片 | 97久久精品人妻人人搡人人玩| 亚洲精品蜜桃久久久久久| 国产精品99久久久精品无码|