• <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ù)應(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
            • --路修遠
            • 5.?re: HDU 2433 最短路
            • 你這樣可以AC????刪除<U,V>不僅改變 u,v最短路啊、、、求解
            • --attacker

            閱讀排行榜

            評論排行榜

            国产精品岛国久久久久| 日本国产精品久久| 国产午夜精品久久久久免费视| 亚洲欧洲日产国码无码久久99| 久久无码人妻一区二区三区| 久久99国产亚洲高清观看首页 | 欧美777精品久久久久网| a级毛片无码兔费真人久久| 久久久www免费人成精品| 97久久久久人妻精品专区| 色婷婷狠狠久久综合五月| 久久精品国产亚洲一区二区| 性高朝久久久久久久久久| 99久久99久久| 久久久久亚洲精品日久生情| 国产精品伦理久久久久久| 少妇人妻综合久久中文字幕| 亚洲嫩草影院久久精品| 成人午夜精品无码区久久| 久久久久97国产精华液好用吗| 新狼窝色AV性久久久久久| 久久久久久久亚洲精品| 国产成人无码精品久久久免费 | 久久国产乱子伦免费精品| 色综合久久久久综合99| 好属妞这里只有精品久久| 久久亚洲精品无码AV红樱桃| 伊人久久大香线蕉成人| 精品久久久久久无码免费| 国产精品久久久久久久| 久久久久久久久无码精品亚洲日韩 | 蜜桃麻豆WWW久久囤产精品| 99久久99久久精品国产片| 精品国产一区二区三区久久久狼| 人人妻久久人人澡人人爽人人精品 | 伊人丁香狠狠色综合久久| 国产精品久久久久9999高清| 国产欧美一区二区久久| 久久99精品国产99久久| 99久久无色码中文字幕| 国产精品久久午夜夜伦鲁鲁|