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

            A Za, A Za, Fighting...

            堅信:勤能補拙

            PKU 2263 Heavy Cargo

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=2263

            思路:
            這題,我自己的想法是更像DP,設源點是source,d[i]表示從source到頂點i的每條路徑中的最小值的最大值,即該題要求的結果
                               d[i] = max (d[i],  min(d[k], adj[k][i])),其中頂點k是從source到頂點i的路徑中頂點i的前趨
            具體編程的話,更像是Dijkstra的方式,只不過這里所有的頂點都必須更新

            另外,這題還用到了字符串哈希,來將每個頂點用一個整數表示

            代碼:
              1 #include<stdio.h>
              2 #include<stdlib.h>
              3 #include<string.h>
              4 #define MAX_N 201
              5 #define MAX_LEN 31
              6 #define INF 0x7FFFFFFF
              7 #define HASH_LEN 19999
              8 #define Min(a, b) ((a)<(b) ? (a) : (b))
              9 #define Max(a, b) ((a)<(b) ? (b) : (a))
             10 int n, r, hash_val;
             11 int from, to, adj[MAX_N][MAX_N];
             12 int d[MAX_N], in[MAX_N];
             13 struct City{
             14     char name[MAX_LEN];
             15     int num;
             16 } cities[MAX_N];
             17 struct Node {
             18     int index;
             19     struct Node *next;
             20 };
             21 struct Node *hash[HASH_LEN] = {NULL};
             22 
             23 int ELFHash(char *str)
             24 {
             25     unsigned long t, hash = 0;
             26     while(*str) {
             27         hash = (hash<<4+ (*str++);
             28         if((t = hash&0xF0000000L))
             29             hash ^= t>>24;
             30         hash &= ~t;
             31     }
             32     return (hash & 0x7FFFFFFF)%HASH_LEN;
             33 }
             34 
             35 void
             36 insert(int index)
             37 {
             38     struct Node *node = (struct Node *)malloc(sizeof(struct Node));
             39     node->index = index;
             40     node->next = hash[hash_val];
             41     hash[hash_val] = node;
             42 }
             43 
             44 int
             45 search(char *str)
             46 {
             47     struct Node *node = hash[hash_val];
             48     while(node != NULL) {
             49         if(strcmp(str, cities[node->index].name) == 0)
             50             return cities[node->index].num;
             51         node = node->next;
             52     }
             53     return -1;
             54 }
             55 
             56 void
             57 init()
             58 {
             59     int i, j, mark, f, t, c;
             60     char str[MAX_LEN];
             61     memset(hash, 0sizeof(hash));
             62     memset(adj, 0sizeof(adj));
             63     for(j=0, mark=1, i=0; i<r; i++) {
             64         scanf("%s", cities[j].name);
             65         hash_val = ELFHash(cities[j].name);
             66         if((f=search(cities[j].name)) == -1) {
             67             insert(j);
             68             cities[j].num = mark++;
             69             f = cities[j].num;
             70             j++;
             71         }
             72         scanf("%s", cities[j].name);
             73         hash_val = ELFHash(cities[j].name);
             74         if((t=search(cities[j].name)) == -1) {
             75             insert(j);
             76             cities[j].num = mark++;
             77             t = cities[j].num;
             78             j++;
             79         }
             80         scanf("%d"&c);
             81         if(adj[f][t] < c)
             82             adj[f][t] = adj[t][f] = c;
             83     }
             84     scanf("%s", str);
             85     hash_val = ELFHash(str);
             86     from = search(str);
             87     scanf("%s", str);
             88     hash_val = ELFHash(str);
             89     to = search(str);
             90 }
             91 
             92 void
             93 solve()
             94 {
             95     int i, j, k, tmp;
             96     memset(in0sizeof(in));
             97     for(i=1; i<=n; i++)
             98         d[i] = 0;
             99     d[from] = INF;
            100     in[from] = 1;
            101     for(i=1; i<=n; i++) {
            102         if(adj[from][i])
            103             d[i] = adj[from][i];
            104     }
            105 
            106     k = n-1;
            107     while(k > 0) {
            108         for(i=1; i<=n; i++) {
            109             if(!in[i] && d[i]!=0) {
            110                 for(j=1; j<=n; j++) {
            111                     if(adj[i][j]) {
            112                         tmp = Min(d[i], adj[i][j]);
            113                         d[j] = Max(d[j], tmp);
            114                     }
            115                 }
            116                 in[i] = 1;
            117                 --k;
            118             }
            119         }
            120     }
            121 }
            122 
            123 int
            124 main(int argc, char **argv)
            125 {
            126     int tests = 0;
            127     while(scanf("%d %d"&n, &r) != EOF) {
            128         if(n==0 && r==0)
            129             break;
            130         init();
            131         solve();
            132         printf("Scenario #%d\n%d tons\n\n"++tests, d[to]);
            133     }
            134 }

            posted on 2010-09-10 18:54 simplyzhao 閱讀(318) 評論(0)  編輯 收藏 引用 所屬分類: F_圖算法

            導航

            <2010年9月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            一本一道久久综合狠狠老| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 午夜精品久久久久久99热| 国产69精品久久久久APP下载| 久久久久久精品成人免费图片| 久久人人爽爽爽人久久久| 久久久久中文字幕| 中文字幕久久亚洲一区| 色偷偷88888欧美精品久久久| 久久久久久久综合日本| 777米奇久久最新地址| 天堂无码久久综合东京热| 伊人色综合久久天天| 久久久黄色大片| 久久99国产精品成人欧美| 色欲久久久天天天综合网| 久久亚洲2019中文字幕| 久久激情五月丁香伊人| 97精品伊人久久大香线蕉app| 国产成人无码精品久久久性色| 国产精品VIDEOSSEX久久发布| 国产aⅴ激情无码久久| 亚洲七七久久精品中文国产| 亚洲国产天堂久久综合网站| 久久精品国产99国产精品亚洲| 久久中文字幕视频、最近更新| 国产成人香蕉久久久久| 久久精品国产亚洲AV无码麻豆| 熟妇人妻久久中文字幕| 少妇久久久久久被弄高潮| 久久e热在这里只有国产中文精品99| 色综合久久久久网| 国产亚洲欧美成人久久片 | 久久艹国产| 国产成人AV综合久久| 国产—久久香蕉国产线看观看| 97精品伊人久久久大香线蕉| 国产ww久久久久久久久久| 国产福利电影一区二区三区久久老子无码午夜伦不 | 午夜精品久久久久久久无码| 久久综合狠狠综合久久激情 |