学步园

HDU_3435

这是一个求最小权完美匹配的题目，我在使用KM算法建立邻接表时，要把边的权值初始化为MAX-w[e]，然后去求最大权的完美匹配，并在计算结果的时候再转化回来即可。

由于是无向图，所以我们需要对每条无向边建立两条有向边。

#include<stdio.h>
#include<string.h>
#define MAXD 1010
#define MAXM 20010
#define MAX 10001
#define INF 1000000000
int first[MAXD], next[MAXM], v[MAXM], w[MAXM], N, M;
int yM[MAXD], wM[MAXD], A[MAXD], B[MAXD], slack, visx[MAXD], visy[MAXD];
int add(int i, int j, int k)
{
int e;
for(e = first[i]; e != -1; e = next[e])
if(v[e] == j)
break;
if(e == -1)
return 1;
if(MAX - k > w[e])
        w[e] = MAX - k;
return 0;
}
void init()
{
int i, j, e, a, b, c;
    scanf("%d%d", &N, &M);
    memset(first, -1, sizeof(first));
    e = 0;
for(i = 0; i < M; i ++)
    {
        scanf("%d%d%d", &a, &b, &c);
        a --;
        b --;
if(add(a, b, c))
        {
            v[e] = b;
            w[e] = MAX - c;
            next[e] = first[a];
            first[a] = e;
            e ++;
        }
if(add(b, a, c))
        {
            v[e] = a;
            w[e] = MAX - c;
            next[e] = first[b];
            first[b] = e;
            e ++;
        }
    }
}
int searchpath(int u)
{
int e, temp;
    visx[u] = 1;
for(e = first[u]; e != -1; e = next[e])
if(!visy[v[e]])
        {
            temp = A[u] + B[v[e]] - w[e];
if(temp == 0)
            {
                visy[v[e]] = 1;
if(yM[v[e]] == -1 || searchpath(yM[v[e]]))
                {
                    yM[v[e]] = u;
                    wM[v[e]] = w[e];
return 1;
                }
            }
else if(temp < slack)
                slack = temp;
        }
return 0;
}
int EK()
{
int i, j, u, e;
for(u = 0; u < N; u ++)
    {
        A[u] = 0;
for(e = first[u]; e != -1; e = next[e])
if(w[e] > A[u])
                A[u] = w[e];
    }
    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;
if(visy[i])
                    B[i] += slack;
            }
        }
return 1;
}
void printresult()
{
int i, res = 0;
for(i = 0; i < N; i ++)
        res += MAX - wM[i];
    printf("%d\n", res);
}
int main()
{
int t, tt;
    scanf("%d", &t);
for(tt = 0; tt < t; tt ++)
    {
        init();
        printf("Case %d: ", tt + 1);
if(EK())
            printresult();
else
            printf("NO\n");
    }
return 0;    
}