学步园

HDU_2426

这个题目是一个求最大权完美匹配的题目，我们需要注意两点：一、要处理好负边的情况。二、要注意N和M不一定相等。

对于第一点的处理，我见过的有两种处理方式：①将所有边都初始化成负边，这样当做N-M之间所有的边都是存在的去进行匹配，如果最后发现边权为正的匹配数为N的话就是有解的，否则无解。②将为负值的边视为不存在，并且在KM算法过程中，如果发现当前状态不能再进行增广，则无解。

对于第二点的处理，我见过的有些AC的程序也没有注意到这个问题，如果对这一点不加处理的话，如果出现N>M的数据并且是用第①种方式去处理第一点的话，程序会陷入死循环。

另外，这个题让我不解的是，现在网上可以搜到的KM算法的slack优化有两种形式，一种是数组形式的，一种是单一变量形式的，我并不觉得两个形式有什么本质的不同，同时我觉得数组形式的应该理论上效率还要稍低一些，但是我用单一变量形式写出的程序（采用第②种方式处理第一点，因为采用第①种方式处理会更慢）要跑1200ms左右，而我搜到的用数组形式写的程序（采用第①种方式处理第一点，采用第②种方式处理要相对慢很多）只跑不到400ms，这个很让我不解。

#include<stdio.h>
#include<string.h>
#define MAXD 510
#define INF 1000000000
int N, M, E, G[MAXD][MAXD];
int yM[MAXD], A[MAXD], B[MAXD];
int visx[MAXD], visy[MAXD], slack;
void init()
{
int i, s, r, v;
    memset(G, -1, sizeof(G));
for(i = 0; i < E; i ++)
    {
        scanf("%d%d%d", &s, &r, &v);
if(G[s][r] == -1 || v > G[s][r])
            G[s][r] = v;
    }
}
int searchpath(int u)
{
int v, temp;
    visx[u] = 1;
for(v = 0; v < M; v ++)
if(G[u][v] != -1 && !visy[v])
        {
            temp = A[u] + B[v] - G[u][v];
if(temp == 0)
            {
                visy[v] = 1;
if(yM[v] == -1 || searchpath(yM[v]))
                {
                    yM[v] = u;
return 1;
                }
            }
else if(temp < slack)
                slack = temp;
        }
return 0;
}
int EK()
{
int i, j, u, v;
for(i = 0; i < N; i ++)
    {
        A[i] = -1;
for(j = 0; j < M; j ++)
if(G[i][j] > A[i])
                A[i] = G[i][j];
    }
    memset(B, 0, sizeof(B));
    memset(yM, -1, sizeof(yM));
for(u = 0; u < N; u ++)
    {
for(;;)
        {
            slack = INF;
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
if(searchpath(u))
break;
if(slack == INF)
return 0;
for(i = 0; i < N; i ++)
if(visx[i])
                    A[i] -= slack;
for(i = 0; i < M; i ++)
if(visy[i])
                    B[i] += slack;
        }
    }
return 1;
}
void printresult()
{
int i, res = 0;
for(i = 0; i < M; i ++)
if(yM[i] != -1)
            res += G[yM[i]][i];
    printf("%d\n", res);
}
int main()
{
int t = 0;
while(scanf("%d%d%d", &N, &M, &E) == 3)
    {
        init();
        printf("Case %d: ", ++t);
if(EK())
            printresult();
else
            printf("-1\n");
    }
return 0;    
}