• <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>
            posts - 14,  comments - 11,  trackbacks - 0
                                                                                                            Going Home

            Description

            On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.

            Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point.

            You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.

            Input

            There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.

            Output

            For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.

            Sample Input

            2 2
            .m
            H.
            5 5
            HH..m
            .....
            .....
            .....
            mm..H
            7 8
            ...H....
            ...H....
            ...H....
            mmmHmmmm
            ...H....
            ...H....
            ...H....
            0 0
            

            Sample Output

            2
            10
            28
            KM算法!
            
            其實(shí)這個題求的是最小權(quán)匹配,,但有些題目最小不一定好求,于是我們可以換一種思維,將有所的距離變成負(fù)的,那么我們要求的就是最大權(quán)匹配!(在一位大牛的指點(diǎn)下)
            廢話不多說,看程序:
              1 #include<iostream>
              2 using namespace std;
              3 #define Inf 10000000;
              4 int map[105][105];
              5 int slack[105];
              6 int lx[105],ly[105];
              7 bool x[105],y[105];
              8 int link[105];
              9 int n,m;
             10 char mm[105][105];
             11 bool dfs(int v)
             12 {
             13      x[v]=true;
             14      int t;
             15      for (int i=0;i<m;i++)
             16      {
             17          if (!y[i])
             18          {
             19             t=lx[v]+ly[i]-map[v][i];
             20             if (t==0)
             21             {
             22                y[i]=true;
             23                if (link[i]==-1||dfs(link[i]))
             24                {
             25                   link[i]=v;
             26                   return true;
             27                }
             28             }
             29             else slack[i]=min(slack[i],t);
             30          }
             31      }
             32      return false;
             33 }
             34 void KM()
             35 {
             36      int i,j,k;
             37      memset(link,-1,sizeof(link));
             38      for (i=0;i<=m;i++)
             39      {
             40          lx[i]=-Inf;
             41          ly[i]=0;
             42      }
             43      for (i=0;i<m;i++)
             44      {
             45          while (1)
             46          {
             47                memset(x,0,sizeof(x));
             48                memset(y,0,sizeof(y));
             49                
             50                for (j=0;j<m;j++) slack[j]=Inf;
             51                    
             52                if (dfs(i))break;
             53                
             54                int d=Inf;
             55                for (j=0;j<m;j++)
             56                    if (!y[j])d=min(slack[j],d);
             57                    
             58                for (j=0;j<m;j++)
             59                {
             60                    if (x[j])lx[j]-=d;
             61                    if (y[j])ly[j]+=d;
             62                }
             63                for (j=0;j<m;j++)
             64                    if (!y[j])slack[j]-=d;
             65          }
             66      }
             67 }
             68 int main()
             69 {
             70     int i,j,k,t,l,v;
             71     while (cin>>k>>t)
             72     {
             73           if (k+t==0)break;
             74           for (i=1;i<=k;i++)
             75           for (j=1;j<=t;j++)
             76               scanf(" %c",&mm[i][j]);
             77           memset(map,0,sizeof(map));
             78           n=0,m=0;
             79           for (i=1;i<=k;i++)
             80           for (j=1;j<=t;j++)
             81           {
             82               if (mm[i][j]=='H')
             83               {
             84                  n=0;
             85                  for (l=1;l<=k;l++)
             86                  for (v=1;v<=t;v++)
             87                  {
             88                      if (mm[l][v]=='m')
             89                      {
             90                         map[m][n]=-(abs(i-l)+abs(j-v));
             91                         n++;
             92                      }
             93                  }
             94                  m++;
             95               }
             96           }
             97           KM();
             98           int sum=0;
             99           for (i=0;i<m;i++)
            100               sum+=map[link[i]][i];
            101           cout<<0-sum<<endl;
            102     }
            103 return 0;
            104 }
            105  
            106 
            posted on 2011-04-19 13:54 路修遠(yuǎn) 閱讀(1438) 評論(0)  編輯 收藏 引用 所屬分類: 路修遠(yuǎn)
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            轉(zhuǎn)載,請標(biāo)明出處!謝謝~~

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            文章檔案

            搜索

            •  

            最新評論

            • 1.?re: HDU 2433 最短路
            • @test
              的確這組數(shù)據(jù)應(yīng)該輸出20的
            • --YueYueZha
            • 2.?re: HDU 2433 最短路
            • 這方法應(yīng)該不對。 看下面這組數(shù)據(jù)
              4 4
              1 2
              2 3
              3 4
              2 4

              畫個圖,刪去最后一條邊 2 4 后的結(jié)果應(yīng)該是20,但是此方法的輸出是19
            • --test
            • 3.?re: HDU 2433 最短路
            • ans = ans + sum_u + sum_v - sum[u] - sum[v],
              這個公式不是很理解啊,不知道博主怎么想的啊,謝謝咯
            • --姜
            • 4.?re: HDU 2433 最短路
            • @attacker
              the i-th line is the new SUM after the i-th road is destroyed
            • --路修遠(yuǎn)
            • 5.?re: HDU 2433 最短路
            • 你這樣可以AC????刪除<U,V>不僅改變 u,v最短路啊、、、求解
            • --attacker

            閱讀排行榜

            評論排行榜

            91久久香蕉国产熟女线看| 国内精品久久久久久麻豆| 久久精品日日躁夜夜躁欧美| 久久久久女教师免费一区| 久久国产乱子伦精品免费午夜| 亚洲人AV永久一区二区三区久久| 一本一道久久综合狠狠老 | 香蕉久久夜色精品国产尤物| 亚洲国产成人精品久久久国产成人一区二区三区综 | 亚洲精品美女久久久久99| 国产精品久久免费| 欧美亚洲国产精品久久| 青青草国产成人久久91网| 久久精品视频一| 国产亚洲美女精品久久久| 99精品久久精品一区二区| 99久久婷婷国产综合精品草原 | 亚洲午夜精品久久久久久浪潮| 久久人人爽爽爽人久久久| 无码任你躁久久久久久老妇| 亚洲国产精品一区二区久久| 久久久久亚洲AV成人网人人网站 | 91精品婷婷国产综合久久| 无码人妻久久久一区二区三区 | 91精品免费久久久久久久久| 亚洲欧美成人综合久久久| 久久国产精品免费| 情人伊人久久综合亚洲| 99久久国产热无码精品免费| 久久久国产打桩机| 性高湖久久久久久久久AAAAA| 欧美亚洲国产精品久久蜜芽| 亚洲综合日韩久久成人AV| 久久精品免费全国观看国产| 欧美亚洲国产精品久久久久| 国产精品久久久久a影院| 亚洲精品WWW久久久久久| 97精品伊人久久大香线蕉| 久久久国产视频| 久久亚洲私人国产精品| 精品久久久久久成人AV|