首页 > 编程语言 > 详细

POJ-2195 Going Home---KM算法求最小权值匹配(存负边)

时间:2018-04-15 23:43:02      阅读:77      评论:0      收藏:0      [点我收藏+]

标签:for   二分图   ostream   lse   ons   nod   esp   范围   预处理   

题目链接:

https://vjudge.net/problem/POJ-2195

题目大意:

给定一个N*M的地图,地图上有若干个man和house,且man与house的数量一致。man每移动一格需花费$1(即单位费用=单位距离),一间house只能入住一个man。现在要求所有的man都入住house,求最小费用。

思路:

KM算法传送门: 理解篇    运用篇

每个man和house建立带权二分图,曼哈顿距离就是边的值,这里要求最小费用,也就是二分图最小权值匹配,但是KM算法求的是二分图最大权值匹配,所以此处用边的负数求最优匹配,求出来的答案的负数就是最小权匹配。

注意:题目说house最多100,但是没有说明man的范围,所以man应该最多100*100。

应该用house为二分图的X部,因为算法复杂度和X部点数有关,所以用点数少的house为X部

因为存的是负数,在预处理X部的顶标值初始化应该是-INF,不能是0

剩下的就是模板啦

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 const int maxx = 100 + 5;//house的上限
  7 const int maxy = 10000 + 5;//man的上限
  8 const int INF = 0x3f3f3f3f;
  9 int cntx, cnty;//X部的点的数目,Y部点的数目
 10 bool visx[maxx], visy[maxy];//是否加入增广路
 11 int wx[maxx], wy[maxy];//顶标值
 12 int cx[maxx], cy[maxy];//匹配的点
 13 int minz;//顶标值和边权最小的差值
 14 int Map[maxx][maxy];//保存边
 15 
 16 bool dfs(int u)
 17 {
 18     visx[u] = 1;
 19     for(int v = 1; v <= cnty; v++)
 20     {
 21         if(!visy[v])//还未加入增广路
 22         {
 23             int t = wx[u] + wy[v] - Map[u][v];
 24             //计算边权和顶标之差,为0表示是相等子图
 25             if(t == 0)
 26             {
 27                 visy[v] = 1;
 28                 if(cy[v] == -1 || dfs(cy[v]))//还未匹配或者反向找到增广路
 29                 {
 30                     cy[v] = u;
 31                     cx[u] = v;
 32                     //cout<<u<<"v"<<v<<endl;
 33                     return 1;
 34                 }
 35             }
 36             else if(t > 0)minz = min(minz, t);
 37         }
 38     }
 39     return 0;
 40 }
 41 
 42 int KM()
 43 {
 44     memset(cx, -1, sizeof(cx));
 45     memset(cy, -1, sizeof(cy));
 46     memset(wx, -INF, sizeof(wx));//注意,这里存的是负边,所以初始化必须是负无穷
 47     memset(wy, 0, sizeof(wy));
 48     for(int i = 1; i <= cntx; i++)//预处理出X部的顶标值
 49     {
 50         for(int j = 1; j <= cnty; j++)
 51         {
 52             wx[i] = max(wx[i], Map[i][j]);
 53             //cout<<wx[i]<<endl;
 54         }
 55     }
 56     for(int i = 1; i <= cntx; i++)
 57     {
 58         while(1)
 59         {
 60             minz = INF;
 61             memset(visx, 0, sizeof(visx));
 62             memset(visy, 0, sizeof(visy));
 63             if(dfs(i))break;
 64 
 65             for(int j = 1; j <= cntx; j++)
 66                 if(visx[j])wx[j] -= minz;
 67             for(int j = 1; j <= cnty; j++)
 68                 if(visy[j])wy[j] += minz;
 69         }
 70     }
 71     int ans = 0;
 72     for(int i = 1; i <= cntx; i++)
 73         if(cx[i] != -1)ans += Map[i][cx[i]];
 74     return ans;
 75 }
 76 struct node
 77 {
 78     int x, y;
 79     node(){}
 80     node(int x, int y):x(x), y(y){}
 81 };
 82 node house[maxx], man[maxy];
 83 char M[105][105];
 84 int main()
 85 {
 86     int n, m;
 87     while(cin >> n >> m && (n && m))
 88     {
 89         cntx = cnty = 0;
 90         for(int i = 0; i < n; i++)//读图
 91         {
 92             cin >> M[i];
 93             for(int j = 0; j < m; j++)
 94             {
 95                 if(M[i][j] == H)house[++cntx] = node(i, j);
 96                 else if(M[i][j] == m)man[++cnty] = node(i, j);
 97             }
 98         }
 99 
100         for(int i = 1; i <= cntx; i++)//建图
101         {
102             for(int j = 1; j <= cnty; j++)
103             {
104                 Map[i][j] = -abs(house[i].x - man[j].x) - abs(house[i].y - man[j].y);
105             }
106         }
107         cout<<(-KM())<<endl;
108     }
109     return 0;
110 }

 

POJ-2195 Going Home---KM算法求最小权值匹配(存负边)

标签:for   二分图   ostream   lse   ons   nod   esp   范围   预处理   

原文:https://www.cnblogs.com/fzl194/p/8850226.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号