匈牙利算法
。
#include#include #include using namespace std;const int MAXN = 503;int n, m;bool to[MAXN][MAXN];int xchoice[MAXN];int ychoice[MAXN];bool vis[MAXN];bool match(int x) { for (int y = 1; y <= m; y ++) { if (to[x][y] == false) continue; if (vis[y]) continue; vis[y] = true; if (ychoice[y] == 0 || match(ychoice[y])) { ychoice[y] = x; return true; } } return false;}int main() { int e; scanf("%d%d%d", &n, &m, &e); for (int i = 0; i < e; i ++) { int x, y; scanf("%d%d", &x, &y); to[x][y] = true; } int ans = 0; for (int i = 1; i <= n; i ++) { fill(vis + 1, vis + 1 + m, false); if (match(i)) { ans ++; } } printf("%d\n", ans); for (int i = 1; i <= m; i ++) xchoice[ychoice[i]] = i; for (int i = 1; i <= n; i ++) printf("%d ", xchoice[i]); printf("\n"); return 0;}
KM算法
据说KM算法只能用在完备匹配，我想应该不是这样的吧。
就是一个很好的例子。
对不起，我想错了QAQ，KM算法确实是只能用在完备匹配。
#include#include #include #include using namespace std;const int MAXN = 403;const double INF = 1e100;const double EPS = 1e-12;template T sqr(const T &x) { return x * x;}template void tension(T &a, const T &b) { if (b < a) a = b;}template void relax(T &a, const T &b) { if (b > a) a = b;}int n, root;double dis(int x1, int y1, int x2, int y2) { return sqrt(sqr(x1 - x2) + sqr(y1 - y2));}double to[MAXN][MAXN * 2];double A[MAXN], B[MAXN * 2];double slack[MAXN * 2];int ychoice[MAXN * 2];bool visx[MAXN], visy[MAXN * 2];bool match(int x) { visx[x] = true; for (int y = 0; y < n << 1; y ++) { if (to[x][y] > - EPS) continue; if (visy[y]) continue; if (abs(to[x][y] - A[x] - B[y]) <= EPS) { visy[y] = true; if (ychoice[y] == -1 || match(ychoice[y])) { ychoice[y] = x; return true; } } else { tension(slack[y], A[x] + B[y] - to[x][y]); } } return false;}int main() {#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin);#endif scanf("%d", &n); static int x[MAXN], y[MAXN]; int cnt = 0; root = 0; for (int i = 0; i < n; i ++) { scanf("%d%d", x + i, y + i); if (y[i] > y[root]) { root = i; cnt = 1; } else if (y[i] == y[root]) { cnt ++; } } if (cnt != 1) { printf("-1\n"); return 0; } for (int i = 0; i < n; i ++) { if (i == root) continue; for (int j = 0; j < n; j ++) { if (! (y[j] > y[i])) continue; to[i][j] = to[i][j + n] = - dis(x[i], y[i], x[j], y[j]); } } fill(A, A + n, - INF); fill(ychoice, ychoice + (n << 1), -1); for (int i = 0; i < n; i ++) for (int j = 0; j < n << 1; j ++) { if (to[i][j] > - EPS) continue; relax(A[i], to[i][j]); } for (int i = 0; i < n; i ++) { if (i == root) continue; while (true) { //cerr << i<< endl; fill(visx, visx + n, false); fill(visy, visy + (n << 1), false); fill(slack, slack + (n << 1), INF); if (match(i)) break; double tmp = INF; for (int y = 0; y < n << 1; y ++) if (! visy[y]) tension(tmp, slack[y]); if (tmp + EPS >= INF) { printf("-1\n"); return 0; } for (int x = 0; x < n; x ++) if (visx[x]) A[x] -= tmp; for (int y = 0; y < n << 1; y ++) if (visy[y]) B[y] += tmp; } } double ans = 0; for (int y = 0; y < n << 1; y ++) if (ychoice[y] != -1) ans += to[ychoice[y]][y]; printf("%.10lf\n", - ans); return 0;}