图论/二分图最优匹配

有一段时间没写KM了，复习一下，别不会写啦。。

二分图最优匹配一般是指的最大权匹配和最小权匹配，两者都可以用KM算法求解。

关于KM算法的资料，可以在百度百科中找到：http://baike.baidu.com/view/739278.htm

这里介绍的是最大权匹配，而最小权匹配和最大权匹配相对，有两种写法：

第一种是在建图的时候将所有边的权值取反，求出最大权匹配后将权值取反。

第二种是在建图的时候将顶标lx[]和ly[]的意义稍微改一下，将lx取成所有相连的边中权值最小的，ly初始化为0不变，然后更新lx[]值时加lack，而ly[]减lack。

这一点和最小费用流-最大费用流有点相似，求最小费用流时用spfa求最短路，而最大费用流可以用先求最小费用流然后取反，也可以直接用spfa求最长路。

hdu3488：最小权匹配

#include <iostream>
#include <cstdio>
#include <cstring>
usingnamespace std;

constint N =210;
constint M =30100;
constint inf =0x1fffffff;

int n, m, tot, lx[N], ly[N], match[N], h[N], v[M], w[M], nxt[M];
bool visx[N], visy[N];
int lack;

void add(int a, int b, int c)
{
    v[tot] = b;
    w[tot] = c;
    nxt[tot] = h[a];
    h[a] = tot++;
}

bool find(int u)
{
int i, t;
    visx[u] =true;
for(i = h[u]; i !=-1; i = nxt[i])
if(!visy[v[i]])
        {
            t = w[i] - lx[u] - ly[v[i]];
if(t ==0)
            {
                visy[v[i]] =true;
if(match[v[i]]==-1|| find(match[v[i]]))
                {
                    match[v[i]] = u;
returntrue;
                }
            }
elseif(t >0)
                lack = min(lack, t);
        }
returnfalse;
}

int main()
{
int t, a, b, c, i, j, ans;
    scanf("%d", &t);
while(t--)
    {
        scanf("%d%d", &n, &m);
        tot =0;
        memset(h, -1, sizeof(h));
for(i =0; i < m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
for(i =1; i <= n; i++)
        {
            lx[i] = inf;
            ly[i] =0;
for(j = h[i]; j !=-1; j = nxt[j])
                lx[i] = min(lx[i], w[j]);
        }
        memset(match, -1, sizeof(match));
for(i =1; i <= n; i++)
        {
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            lack = inf;
while(!find(i))
            {
for(j =1; j <= n; j++)
                {
if(visx[j])  lx[j] += lack;
if(visy[j])  ly[j] -= lack;
                }
                memset(visx, false, sizeof(visx));
                memset(visy, false, sizeof(visy));
            }
        }
        ans =0;
for(i =1; i <= n; i++)  ans = ans + lx[i] + ly[i];
        printf("%d\n", ans);
    }
return0;
}

　　

hdu2255：裸的最大权匹配，刚开始不小心把"visy[i] = true"放错位置了，一直TLE。。。又涨经验啦~

用此题我对比了一下一些常数优化的细节。

750ms的是朴素的未加任何优化的实现。

375ms使用了IO优化和memset

406ms使用了IO优化和手动初始化赋值~看来用memset对付整个数组的初始化效率还是挺高滴~

不过对于那种数组上界N高达10^7，而多组case中很多n都是10^5,10^4的那种题还是手动赋值效果要好一点吧~

贴下375ms的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
usingnamespace std;

constint N =310;
constint inf =0x1fffffff;

int n, lx[N], ly[N], match[N], w[N][N];
bool visx[N], visy[N];
int lack;

int getNum()
{
char c;
int ans =0;
    c = getchar();
while(c<'0'|| c>'9') c = getchar();
while(c>='0'&& c<='9')
    {
        ans = ans*10+c-'0';
        c = getchar();
    }
return  ans;
}

bool find(int u)
{
int i, t;
    visx[u] =true;
for(i =1; i <= n; i++)
if(!visy[i])
        {
            t = lx[u] + ly[i] - w[u][i];
if(t ==0)
            {
                visy[i] =true;
if(match[i]==-1|| find(match[i]))
                {
                    match[i] = u;
returntrue;
                }
            }
elseif(t >0)
                lack = min(lack, t);
        }
returnfalse;
}

int main()
{
int i, j, ans;
while(scanf("%d", &n) != EOF)
    {
for(i =1; i <= n; i++)
        {
            lx[i] = ly[i] =0;
for(j =1; j <= n; j++)
            {
                w[i][j] = getNum();
                lx[i] = max(lx[i], w[i][j]);
            }
        }
        memset(match, -1, sizeof(match));
for(i =1; i <= n; i++)
        {
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            lack = inf;
while(!find(i))
            {
for(j =1; j <= n; j++)
                {
if(visx[j])  lx[j] -= lack;
if(visy[j])  ly[j] += lack;
                }
                memset(visx, false, sizeof(visx));
                memset(visy, false, sizeof(visy));
            }
        }
        ans =0;
for(i =1; i <= n; i++)  ans = ans + lx[i] + ly[i];
        printf("%d\n", ans);
    }
return0;
}