UVALive - 3353 Optimal Bus Route Design(二分图绝佳匹配)

题目大意：给出一个n个点的有向带权图，找若干个圈，使得每个节点恰好属于一个圈，要求总长度尽量小

解题思路：首先要在一个圈内，且只能在一个圈内，那么每个点的入度和出度要都为1，所以二分图就有了
接着连边，给出来的边都连了，没给的边就设为INF，最后求最小权和就可以来
如果最小权和大于INF了，就表示无法满足每个点都在一个圈内的要求了
注意：会有重边

#include <cstdio>
#include <cstring>

#define N 110
#define INF 0x3f3f3f3f
#define max(a,b)((a)>(b)?(a):(b))
#define min(a,b)((a)<(b)?(a):(b))
#define abs(a)((a)>0?(a):(-(a)))
#define ll long long

int w[N][N], Lx[N], Ly[N], left[N], slack[N];
bool S[N], T[N];
int n, m;

void init() {
    memset(w, 0x3f, sizeof(w));
    int j, d;
    for (int i = 1; i <= n; i++) {
        while(scanf("%d", &j) && j) {
            scanf("%d", &d);
            w[i][j] = min(w[i][j], d);
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            w[i][j] = -w[i][j];
}

bool match(int i) {
    S[i] = true;
    for (int j = 1; j <= n; j++) {
        if (Lx[i] + Ly[j] == w[i][j] && !T[j]) {
            T[j] = true;
            if (!left[j] || match(left[j])) {
                left[j] = i;
                return true;
            }
        }
        else slack[j] = min(slack[j], Lx[i] + Ly[j] - w[i][j]);
    }
    return false;
}

int KM() {
    for (int i = 1; i <= n; i++) {
        left[i] = Ly[i] = 0;
        Lx[i] = -INF;
        for (int j = 1; j <= n; j++)
            Lx[i] = max(Lx[i], w[i][j]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            slack[j] = INF;
        while (1) {
            for (int j = 1; j <= n; j++) S[j] = T[j] = 0;
            if (match(i)) break;
            int a = INF;
            for (int j = 1; j <= n; j++)
                if (!T[j])
                    a = min(a, slack[j]);
            for (int j = 1; j <= n; j++) {
                if (S[j]) Lx[j] -= a;
                if (T[j]) Ly[j] += a;
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans += Lx[i] + Ly[i];
    return ans;
}

void solve() {
    ll ans = KM();
    if (abs(ans) >= INF)
        printf("N\n");
    else
        printf("%lld\n", abs(ans));
}

int main() {
    while (scanf("%d", &n) != EOF && n) {
        init();
        solve();
    }
    return 0;
}