题目类型 最佳完美匹配, 最小费用最大流
题目意思
给出一个最多 100 * 100 的字符矩阵 其中有若干个m和相同数量的H, 现在要使每个m都与一个不同的H配对,问最少的花费是多少
一次配对的花费是配对的两个字符的哈密顿距离
解题方法
用km算法求最佳完美匹配(即花费最小的完美匹配) 每个m点和所有的H点连一条权值为原花费*(-1)的边 然后求一次权值和最大的完美匹配即可
用最小费用最大流的方法做就是新建一个源点s和一个汇点t, s到所有的m连一条容量为1, 费用为0的边,所有的H到t连一条容量为1费用为0的边, 每个m与H之间连一条容量为1费用为相应花费的边, 然后求一次最小费用最大流即可
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
km算法:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn = 100 + 10; const int INF = 1<<29; char str[maxn][maxn]; vector<int>M, H; int Lx[maxn], Ly[maxn], Left[maxn]; int s[maxn], t[maxn], w[maxn][maxn]; int sum; bool match(int i, int n) { s[i] = true; for( int j=1; j<=n; j++ ) if(Lx[i]+Ly[j] == w[i][j] && !t[j]) { t[j] = true; sum += w[i][j]; if(!Left[j] || match(Left[j], n)) { sum -= w[Left[j]][j]; Left[j] = i; return true; } sum -= w[i][j]; } return false; } void update(int n) { int a = 1<<30; for( int i=1; i<=n; i++ ) if(s[i]) for( int j=1; j<=n; j++ ) if(!t[j]) a = min(a, Lx[i]+Ly[j]-w[i][j]); for( int i=1; i<=n; i++ ) { if(s[i]) Lx[i] -= a; if(t[i]) Ly[i] += a; } } void km(int n) { for( int i=1; i<=n; i++ ) { Left[i] = Lx[i] = Ly[i] = 0; for( int j=1; j<=n; j++ ) { Lx[i] = max(Lx[i], w[i][j]); } } for( int i=1; i<=n; i++ ) { for( ; { for( int j=1; j<=n; j++ ) s[j] = t[j] = 0; if(match(i, n)) break; else update(n); } } } int Abs(int x) { return x < 0 ? -x : x; } int main() { //freopen("in", "r", stdin); int n, m, N; while(scanf("%d%d", &n, &m), n || m) { M.clear(), H.clear(); for( int i=0; i<n; i++ ) { scanf("%s", str[i]); for( int j=0; j<m; j++ ) { if(str[i][j] == 'm') M.push_back(i*m+j); else if(str[i][j] == 'H') H.push_back(i*m+j); } } N = M.size(); for( int i=0; i<N; i++ ) { int xi = M[i]/m, yi = M[i]%m; int ti = i + 1; Lx[ti] = -INF; for( int j=0; j<N; j++ ) { int xj = H[j]/m, yj = H[j]%m; int cost = Abs(xi-xj) + Abs(yi - yj); int tj = j + 1; w[ti][tj] = -cost; Lx[ti] = max(Lx[ti], -cost); } } sum = 0; km(N); printf("%d\n", -sum); } return 0; }
最小费用最大流:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <cmath> using namespace std; const int maxn = 100 + 10; const int INF = 1<<29; struct Edge { int from, to, cap, flow, cost; Edge(int _from, int _to, int _cap, int _flow, int _cost) : from(_from), to(_to), cap(_cap), flow(_flow), cost(_cost) {} Edge() {} }; struct MCMF { int n, m, s, t; vector<Edge>edges; vector<int>G[maxn*maxn]; int inq[maxn*2], d[maxn*2], p[maxn*2], a[maxn*2]; void init(int n) { this->n = n; for( int i=0; i<n; i++ ) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap, int cost) { edges.push_back(Edge(from, to, cap, 0, cost)); edges.push_back(Edge(to, from, 0, 0, -cost)); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BellmanFord(int s, int t, int & flow, int & cost) { for( int i=0; i<n; i++ ) d[i] = INF; memset(inq, 0, sizeof(inq)); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; queue<int>Q; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for( int i=0; i<G[u].size(); i++ ) { Edge & e = edges[G[u][i]]; if(e.cap > e.flow && d[e.to] > d[u] + e.cost) { d[e.to] = d[u] + e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; } } } } if(d[t] == INF) return false; flow += a[t]; cost += d[t] * a[t]; int u = t; while(u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].from; } return true; } int Mincost(int s, int t) { int flow = 0, cost = 0; while(BellmanFord(s, t, flow, cost)); return cost; } }MC; char str[maxn][maxn]; int abs(int x) { return x < 0 ? -x : x; } int main() { freopen("in", "r", stdin); int n, m; while(scanf("%d%d", &n, &m), n || m) { vector<int>M, H; for( int i=0; i<n; i++ ) { scanf("%s", str[i]); for( int j=0; j<m; j++ ) { if(str[i][j] == 'm') M.push_back(i*m+j); else if(str[i][j] == 'H') H.push_back(i*m+j); } } int N = M.size(); MC.init(2*N+2); for( int i=0; i<N; i++ ) { int xi = M[i]/m, yi = M[i]%m; for( int j=0; j<N; j++ ) { int xj = H[j]/m, yj = H[j]%m; int cost = abs(xi-xj) + abs(yi - yj); MC.AddEdge(i+1, N+1+j, 1, cost); } } for( int i=1; i<=N; i++ ) MC.AddEdge(0, i, 1, 0); for( int i=N+1; i<=2*N; i++ ) MC.AddEdge(i, 2*N+1, 1, 0); int ans = MC.Mincost(0, 2*N+1); printf("%d\n", ans); } return 0; }