最大流增广路(KM算法) HDOJ 2255 奔小康赚大钱-白红宇

最大流增广路(KM算法) HDOJ 2255 奔小康赚大钱

阅读量：6361 次

发布时间：2019-06-23

本文共 2221 字，大约阅读时间需要 7 分钟。

1 /* 2     KM：裸题第一道，好像就是hungary的升级版，不好理解，写点注释 3         KM算法用来解决最大权匹配问题： 在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接Xi，Yj有权w(i,j)， 4         求一种匹配使得所有w(i,j)的和最大。也就是最大权匹配一定是完备匹配。如果两边的点数相等则是完美匹配。 5         如果点数不相等，其实可以虚拟一些点，使得点数相等，也成为了完美匹配。最大权匹配还可以用最大流去解决 6 */ 7 #include 
     
       8 #include 
      
        9 #include 
       
        10 using namespace std;11 12 const int MAXN = 3e2 + 10;13 const int INF = 0x3f3f3f3f;14 int x[MAXN], y[MAXN], w[MAXN][MAXN];15 int lx[MAXN], ly[MAXN];16 bool visx[MAXN], visy[MAXN];17 int n, d;18 19 bool DFS(int u)    {        //hungary算法20     visx[u] = true;21     for (int i=1; i<=n; ++i)    {22         if (x[u] + y[i] == w[u][i] && !visy[i])    {23             visy[i] = true;24             if (ly[i] == -1 || DFS (ly[i]))    {25                 ly[i] = u;    return true;26             }27         }28         else if (x[u] + y[i] > w[u][i])    d = min (d, x[u] + y[i] - w[u][i]);        //更新d，贪心思想29     }30 31     return false;32 }33 34 void KM(void)    {35     for (int i=1; i<=n; ++i)    {36         x[i] = 0;37         for (int j=1; j<=n; ++j)    {38             x[i] = max (x[i], w[i][j]);        //初始x标杆为最大值w，y为039         }40     }41 42     memset (y, 0, sizeof (y));43     memset (ly, -1, sizeof (ly));44     for (int i=1; i<=n; ++i)    {45         while (true)    {46             memset (visx, false, sizeof (visx));47             memset (visy, false, sizeof (visy));48             d = INF;49             if (DFS (i))    break;            //找到增广轨，退出50             for (int i=1; i<=n; ++i)    {        //没有找到，对标杆进行调整51                 if (visx[i])    x[i] -= d;52                 if (visy[i])    y[i] += d;53             }54         }55     }56 57     int res = 0;58     for (int i=1; i<=n; ++i)    {59         res += x[i] + y[i];60     }61     printf ("%d\n", res);62 }63 64 int main(void)    {        //HDOJ 2255 奔小康赚大钱65     //freopen ("HDOJ_2255.in", "r", stdin);66 67     while (scanf ("%d", &n) == 1)    {68         for (int i=1; i<=n; ++i)    {69             for (int j=1; j<=n; ++j)    {70                 scanf ("%d", &w[i][j]);71             }72         }73         KM ();74     }75 76     return 0;77 }