• <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算法!
            
            其實這個題求的是最小權(quán)匹配,,但有些題目最小不一定好求,于是我們可以換一種思維,將有所的距離變成負的,那么我們要求的就是最大權(quá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 路修遠 閱讀(1438) 評論(0)  編輯 收藏 引用 所屬分類: 路修遠
            <2011年4月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            1234567

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

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            文章檔案

            搜索

            •  

            最新評論

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

              畫個圖,刪去最后一條邊 2 4 后的結(jié)果應該是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
            • --路修遠
            • 5.?re: HDU 2433 最短路
            • 你這樣可以AC????刪除<U,V>不僅改變 u,v最短路啊、、、求解
            • --attacker

            閱讀排行榜

            評論排行榜

            99久久er这里只有精品18| 久久综合综合久久狠狠狠97色88| 97r久久精品国产99国产精| 色综合久久中文字幕综合网| 久久精品毛片免费观看| 日韩十八禁一区二区久久| 国产精品99久久久精品无码| 国产成人久久精品激情| 四虎国产精品免费久久5151| 三级片免费观看久久| 狠狠色丁香久久综合五月| 狠狠综合久久AV一区二区三区| 成人午夜精品久久久久久久小说| 久久人人爽人人爽人人AV东京热 | 久久国产乱子伦免费精品| 一级做a爱片久久毛片| 久久国产高清字幕中文| 伊人精品久久久久7777| 欧美日韩中文字幕久久久不卡| 久久九九久精品国产免费直播| 伊人久久大香线蕉综合热线| 久久亚洲国产成人影院网站 | 偷偷做久久久久网站| 97久久精品无码一区二区天美| 久久久久亚洲?V成人无码| 精品久久久久中文字| 久久久受www免费人成| 久久青青草原国产精品免费| 一本一本久久a久久综合精品蜜桃 一本一道久久综合狠狠老 | 伊人色综合久久天天网| 91精品久久久久久无码| 久久本道伊人久久| 亚洲精品蜜桃久久久久久| 久久久噜噜噜久久熟女AA片| 久久婷婷五月综合97色直播| 欧美日韩精品久久久久| 亚洲午夜精品久久久久久浪潮| 久久婷婷人人澡人人| 久久99精品国产麻豆婷婷| 久久精品夜色噜噜亚洲A∨| 久久久精品久久久久特色影视|