题目大意
给定一个二分图,每个点集各有 n 个节点;再给定两个矩阵 {ai,j}、{bi,j}。求二分图的一个完美匹配,使得
C=b1′+b2′+⋯+bn′a1′+a2′+⋯+an′
最大。
当二分图的点集 X 中的点 i 与点集 Y 中的点 j 匹配时,ai′=ai,j,bi′=bi,j。
1⩽n⩽100
1⩽ai,j,bi,j⩽10,000
题目链接
【SDOI 2017】新生舞会 - LibreOJ 2003
题解
把那个式子写成 C×(b1′+b2′+⋯+bn′)−(a1′+a2′+⋯+an′)=0,二分答案。
具体地说,以 C×bi,j−ai,j 为边 Xi−Yj 的权值求最大匹配,若小于等于 0,则说明更大。
注意是实数二分。据说固定次数比差小于等于 EPS
要好一点(在控制时间上)。
代码
不要自己搞一个 STL 容器元素的指针!
对于 std::vector
,当容量不够用时,会重新开二倍数组,不一定在原来的位置上,之后指向其内部元素的指针就飞了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
| #include <cstdio> #include <climits> #include <cfloat> #include <vector> #include <queue> #include <algorithm> const int MAXN = 105; struct Edge; struct Node { std::vector<Edge> e; Edge *pre; int flow; double dist; bool inq; } N[MAXN << 1]; struct Edge { Node *u, *v; int cap, flow, rev; double cost; Edge() {} Edge(Node *u, Node *v, int cap, double cost, int rev) : u(u), v(v), cap(cap), flow(0), cost(cost), rev(rev) {} }; void addEdge(int u, int v, int cap, int cost) { N[u].e.push_back(Edge(&N[u], &N[v], cap, cost, N[v].e.size())); N[v].e.push_back(Edge(&N[v], &N[u], 0, -cost, N[u].e.size() - 1)); } namespace EdmondsKarp { void solve(int s, int t, int n, int &flow, double &cost) { flow = 0; cost = 0; while (true) { for (int i = 0; i < n; i++) { N[i].dist = DBL_MAX; N[i].flow = 0; N[i].inq = false; N[i].pre = NULL; } std::queue<Node *> q; q.push(&N[s]); N[s].dist = 0; N[s].flow = INT_MAX; while (!q.empty()) { Node *u = q.front(); q.pop(); u->inq = false; for (Edge *e = &u->e.front(); e && e <= &u->e.back(); e++) { if (e->cap > e->flow && e->v->dist > u->dist + e->cost) { e->v->dist = u->dist + e->cost; e->v->flow = std::min(u->flow, e->cap - e->flow); e->v->pre = e; if (!e->v->inq) { e->v->inq = true; q.push(e->v); } } } } if (N[t].dist == DBL_MAX) break; for (Edge *e = N[t].pre; e; e = e->u->pre) { e->flow += N[t].flow; e->v->e[e->rev].flow -= N[t].flow; } flow += N[t].flow; cost += N[t].dist * N[t].flow; } } } int a[MAXN][MAXN], b[MAXN][MAXN], n; void build() { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) addEdge(i, j + n, 1, 0); const int s = 0, t = 2 * n + 1; for (int i = 1; i <= n; i++) addEdge(s, i, 1, 0), addEdge(n + i, t, 1, 0); } bool check(double c) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { double temp = c * b[i][j] - a[i][j]; N[i].e[j - 1].cost = temp; N[j + n].e[N[i].e[j - 1].rev].cost = -temp; } const int s = 0, t = 2 * n + 1; for (int i = s; i < t; i++) for (int j = 0; j < N[i].e.size(); j++) N[i].e[j].flow = 0; int flow; double cost; EdmondsKarp::solve(s, t, t + 1, flow, cost); return cost <= 0; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &b[i][j]); build(); double l = 0, r = 1e4; for (int i = 0; i < 40; i++) { double mid = l + (r - l) / 2; if (check(mid)) l = mid; else r = mid; } printf("%.6lf\n", l); return 0; }
|