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

            閱讀排行榜

            評論排行榜

            久久国产高清一区二区三区| 91精品国产综合久久精品| 精品久久综合1区2区3区激情| 免费国产99久久久香蕉| 久久久无码精品亚洲日韩京东传媒| 久久精品国产福利国产秒| 国产美女亚洲精品久久久综合| 99久久国产亚洲高清观看2024| 久久人人爽人人爽人人片av高请 | 久久99国产综合精品| 久久亚洲精品无码aⅴ大香| 日韩欧美亚洲综合久久影院d3| 久久综合丁香激情久久| 久久精品亚洲AV久久久无码| 亚洲国产精品久久久久婷婷软件| 午夜精品久久久久| 四虎影视久久久免费观看| 久久久久黑人强伦姧人妻| 久久精品国产亚洲av瑜伽| 婷婷久久香蕉五月综合加勒比| 五月丁香综合激情六月久久| 精品无码久久久久久久久久| 九九99精品久久久久久| 亚洲乱码中文字幕久久孕妇黑人| 久久久国产精品| 久久精品国产亚洲Aⅴ香蕉| 久久精品国产亚洲一区二区| 99久久精品午夜一区二区 | 99久久精品免费看国产一区二区三区| 久久久久免费精品国产| av无码久久久久久不卡网站 | 狠狠人妻久久久久久综合蜜桃| 99国产精品久久| 青青青青久久精品国产h| 99久久99久久久精品齐齐| 精品无码久久久久国产| 一本一道久久综合狠狠老| 99久久精品国产一区二区 | 91精品国产高清久久久久久91| 精品久久久久久中文字幕| 久久国产精品久久国产精品|