UVa 二分图匹配 Examples

这些都是刘汝佳的算法训练指南上的例题，基本包括了常见的几种二分图匹配的算法。

二分图是这样一个图，顶点分成两个不相交的集合X , Y中，其中同一个集合中没有边，所有的边关联在两个集合中。

给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

最大匹配：包含边数最多的匹配。

最小点覆盖 = 最大匹配数        Matrix67大神的证明写的非常好 http://www.matrix67.com/blog/archives/116

最大独立集 = N - 最大匹配数 (与最小点覆盖互补)

最小路径覆盖 = N - 最大匹配数

UVa 1411 - Ants

问题可以转化成求最小权完美匹配，权值为黑点到白点的欧几里得距离。KM算法

/* **********************************************
Author      : JayYe
Created Time: 2013-8-17 18:06:01
File Name   : zzz.cpp*********************************************** */#include 
#include 
#include 
#include 
using namespace std;const double eps = 1e-6;const int maxn = 100;struct Point{int x, y;
}a[maxn+10];bool S[maxn+10], T[maxn+10]; // S表示在左边集合，T表示在右边集合
double lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10]; // 利用slack来松弛，时间复杂度降到O(n^3)
int match[maxn+10], n;bool dfs(int u) {S[u] = 1;for(int i = 1;i <= n; i++) if(!T[i])if(slack[i] - (w[u][i] - lx[u] - ly[i]) > eps)slack[i] = w[u][i] - lx[u] - ly[i];for(int i = 1;i <= n; i++) if(fabs(w[u][i] - lx[u] - ly[i]) < eps && !T[i]) {T[i] = 1;if(!match[i] || dfs(match[i])) {match[i] = u;return true;}}return false;
}void update() {double delta = 1<<30;for(int i = 1;i <= n; i++) if(!T[i] && delta - slack[i] > eps)delta = slack[i];for(int i = 1;i <= n; i++) {if(S[i])    lx[i] += delta;if(T[i])    ly[i] -= delta;}
}void KM() {int i, j;for(i = 1;i <= n; i++) {lx[i] = 1<<30;ly[i] = match[i] = 0;// 与最大权完美匹配不同，最小权初始lx应该设为最小，每次update有最小增for(j = 1;j <= n; j++) if(lx[i] - w[i][j] > eps)lx[i] = w[i][j];}for(i = 1;i <= n; i++) {while(true) {for(j = 1;j <= n; j++)  S[j] = T[j] = 0 , slack[j] = 1<<30;if(dfs(i))  break;else    update();}}
}void solve() {int i, j, x, y;for(i = 1;i <= n; i++)   scanf("%d%d", &a[i].x, &a[i].y);for(i = 1;i <= n ;i++) {scanf("%d%d", &x, &y);for(j = 1;j <= n; j++)w[i][j] = sqrt((a[j].x - x)*(a[j].x - x) + (a[j].y - y)*(a[j].y - y));}KM();for(i = 1;i <= n; i++) printf("%d\n", match[i]);
}int main() {while(scanf("%d", &n) != -1) {solve();}return 0;
}

UVa  11383 - Golden Tiger Claw
有n*n的格子，每个格子有w(i, j)，现在给每行确定一个整数row(i) ，每列确定一个整数col(i)，使得所有w(i, j) <= row(i) + col(j)。

其实这样就相当于利用KM算法求最大权完美匹配。KM算法实际上最后求出的所有的lx, ly的和是最小的且都满足lx(i) + ly(j) >= w(i, j)，所以直接用KM算法来求解，这个应用还是挺灵活的。

/* **********************************************
Author      : JayYe
Created Time: 2013-8-17 19:43:54
File Name   : zzz.cpp
*********************************************** */#include 
#include int max(int a, int b) { return  a>b?a:b; }
int min(int a, int b) { return  a>b?b:a; }const int maxn = 500;int n, match[maxn+10], lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10];
bool S[maxn+10], T[maxn+10];bool dfs(int i) {S[i] = 1;for(int j = 1;j <= n; j++) if(!T[j])slack[j] = min(slack[j], lx[i] + ly[j] - w[i][j]);for(int j = 1;j <= n; j++) if(w[i][j] == lx[i] + ly[j] && !T[j]) {T[j] = 1;if(!match[j] || dfs(match[j])) {match[j] = i;return true;}}return false;
}void update() {int delta = 1<<30;for(int i = 1;i <= n ;i++) if(!T[i])delta = min(delta, slack[i]);for(int i = 1;i <= n; i++) {if(S[i])    lx[i] -= delta;if(T[i])    ly[i] += delta;}
}void KM() {int i, j;for(i = 1;i <= n; i++) {lx[i] = ly[i] = match[i] = 0;for(j = 1;j <= n; j++)lx[i] = max(lx[i], w[i][j]);}for(i = 1;i <= n; i++) {while(true) {for(j = 1;j <= n; j++)  S[j] = T[j] = 0, slack[j] = 1<<30;if(dfs(i))  break;else    update();}}
}void solve() {int i, j;for(i = 1;i <= n; i++)for(j = 1;j <= n; j++)  scanf("%d", &w[i][j]);KM();int ans = 0;for(i = 1;i <= n; i++)  printf("%d%c", lx[i], i < n ? ' ' : '\n'), ans += lx[i];for(i = 1;i <= n; i++)  printf("%d%c", ly[i], i < n ? ' ' : '\n'), ans += ly[i];printf("%d\n", ans);
}int main() {while(scanf("%d", &n) != -1) {solve();}return 0;
}

UVa 1006 - Fixed Partition Memory Management

大概题意是有n个程序要让他们在m个内存区域里运行，一个内存区域不能同时进行两个程序，但是可以先运行完一个程序再运行下一个。转换成求最小权匹配，最后输出有点麻烦。

/* **********************************************
Author      : JayYe
Created Time: 2013-8-18 8:52:59
File Name   : zzz.cpp*********************************************** */#include 
#include 
#include 
using namespace std;int max(int a, int b) { return a>b?a:b; }
int min(int a, int b) { return a>b?b:a; }int n, m, slack[555], lx[55], ly[555], match[555], w[55][555], mem[22], a[22], t[22];
bool S[55], T[555];bool dfs(int i) {S[i] = 1;for(int j = 1;j <= n*m; j++) if(!T[j])slack[j] = min(slack[j], w[i][j] - lx[i] - ly[j]);for(int j = 1;j <= n*m; j++) if(w[i][j] == lx[i] + ly[j] && !T[j]) {T[j] = 1;if(!match[j] || dfs(match[j])) {match[j] = i;return true;}}return false;
}void update() {int delta = 1<<30;for(int i = 1;i <= n*m; i++) if(!T[i])delta = min(delta, slack[i]);for(int i = 1;i <= n; i++) if(S[i])    lx[i] += delta;for(int i = 1;i <= n*m; i++) if(T[i])ly[i] -= delta;
}void KM() {int i, j;for(i = 1;i <= n; i++) {lx[i] = 1<<30;for(j = 1;j <= n*m; j++) {lx[i] = min(lx[i], w[i][j]);ly[j] = match[j] = 0;}}for(i = 1;i <= n; i++) {while(true) {for(j = 1;j <= n*m; j++)    S[j] = T[j] = 0, slack[j] = 1<<30;if(dfs(i))  break;else    update();}}
}void solve() {for(int i = 1;i <= m; i++)  scanf("%d", &mem[i]);for(int i = 1;i <= n; i++)for(int j = 1;j <= n*m; j++)w[i][j] = 1<<30;for(int i = 1;i <= n; i++) {int k;scanf("%d", &k);for(int j = 1;j <= k; j++)  scanf("%d%d", &a[j], &t[j]);a[k+1] = 1<<30;for(int j = 1;j <= m; j++) {for(int l = 1;l <= k; l++) if(mem[j] >= a[l] && mem[j] < a[l+1]) {for(int ii = 1;ii <= n; ii++) {w[i][(j-1)*n + ii] = ii*t[l];}}}}   KM();
}int main() {int cas = 1;while(scanf("%d%d", &m, &n) != -1) {solve();printf("Case %d\n", cas++);int ans = 0;for(int i = 1;i <= n; i++)  ans += lx[i];for(int i = 1;i <= n*m; i++)    ans += ly[i];printf("Average turnaround time = %.2lf\n", (double)ans/n);int from[55], to[55], in[55], sum; // from表示程序从什么时间开始，to表示结束时间，in表示在哪个内存区域里运行for(int i = n*m;i >= 1; i--) {if(i%n == 0)    sum = 0;if(match[i]) {int tmp = w[match[i]][i];from[match[i]] = sum;int num = i%n;if(i%n == 0)    num = n;to[match[i]] = sum = tmp/num + sum;in[match[i]] = i/n + 1;if(i%n == 0)    in[match[i]]--;}}for(int i = 1;i <= n; i++)printf("Program %d runs in region %d from %d to %d\n", i, in[i], from[i], to[i]);}return 0;
}

UVa 11419 - SAM I AM

最小点覆盖， 求出最大匹配后，最后要找到最小的点覆盖集。最小的点覆盖集的寻找过程，先从右边的非匹配点出发找交错路，并把路径上的点都标记下，最后的点覆盖集就是左边的标记了的顶点加上右边未标记的匹配点。

/* **********************************************
Author      : JayYe
Created Time: 2013-8-18 11:10:00
File Name   : zzz.cpp*********************************************** */#include 
#include 
#include 
using namespace std;const int maxn = 1000+10;bool mp[maxn][maxn], vis[maxn];
int match[maxn], markl[maxn], markr[maxn], right[maxn], n, m;// 求最大匹配数
bool dfs(int i) {for(int j = 1;j <= m; j++) if(mp[i][j] && !vis[j]) {vis[j] = 1;if(!match[j] || dfs(match[j])) {match[j] = i;return true;}}return false;
}
// 交错路寻找点覆盖集
void findmin(int i) {markr[i] = 1;for(int j = 1;j <= n; j++) if(mp[j][i] && !markl[j]) {markl[j] = 1;if(right[j]) {findmin(right[j]);}}
}int main() {int k, i, j, x, y;while(scanf("%d%d%d", &n, &m, &k) != -1 && n) {for(i = 1;i <= n; i++)for(j = 1;j <= m; j++)mp[i][j] = 0;while(k--) {scanf("%d%d", &x, &y);mp[x][y] = 1;}int ans = 0;for(i = 1;i <= m; i++)  match[i] = 0;for(i = 1;i <= n; i++) {for(j = 1;j <= m; j++)  vis[j] = 0;if(dfs(i))  ans++;}printf("%d", ans);for(i = 1;i <= n; i++)  markl[i] = markr[i] = right[i] = 0;for(i = 1;i <= m; i++) if(match[i])right[match[i]] = i;for(i = 1;i <= m; i++) if(!match[i]){findmin(i);}//左边标记过的匹配点for(i = 1;i <= n; i++) if(markl[i]) printf(" r%d", i);//右边未标记的匹配点for(i = 1;i <= m; i++) if(match[i] && !markr[i])　 printf(" c%d", i); puts(""); } return 0;
}

UVa 12083 - Guardian of Decency


最大独立集，根据男女划分为二分图，求最大匹配数，结果就是总数减去最大匹配数。
wrong answer注意有一个地方，身高的条件不是至少相差40厘米，而是身高相差大于40厘米。

/* **********************************************
Author      : JayYe
Created Time: 2013-8-18 13:26:39
File Name   : zzz.cpp
*********************************************** */#include 
#include 
#include 
using namespace std;const int maxn = 500+5;struct PP {int h;char music[111],sport[111];
}boy[maxn], girl[maxn], tmp;int n, m, match[maxn];
bool vis[maxn], mp[maxn][maxn];bool dfs(int i) {for(int j = 1;j <= m; j++) if(mp[i][j] && !vis[j]) {vis[j] = 1;if(!match[j] || dfs(match[j])) {match[j] = i;return true;}}return false;
}char sex[2], music[111], sport[111];
int main() {int t, i, j;scanf("%d", &t);while(t--) {scanf("%d", &n);int n1 = 0, n2 = 0, h;for(i = 1;i <= n; i++) {scanf("%d%s%s%s", &tmp.h, sex, tmp.music, tmp.sport);if(sex[0] == 'M')   boy[++n1] = tmp;else    girl[++n2] = tmp;}n = n1, m = n2;for(i = 1;i <= n; i++) {for(j = 1;j <= m; j++) {if(abs(boy[i].h - girl[j].h) <= 40 && strcmp(boy[i].music, girl[j].music) == 0 && strcmp(boy[i].sport, girl[j].sport) != 0) {mp[i][j] = 1;}elsemp[i][j] = 0;}}for(i = 1;i <= m; i++)  match[i] = 0;int ans = 0;for(i = 1;i <= n; i++) {for(j = 1;j <= m; j++) vis[j] = 0;if(dfs(i))  ans++;}printf("%d\n", n+m-ans);}return 0;
}

UVa 1201 - Taxi Cab Scheme


最小路径覆盖，在图上找尽量少的路径使得每个结点恰好在一条路径上(换句话说， 不同的路径不能有公共点)。单独的结点也看做一条路径。

/* **********************************************
Author      : JayYe
Created Time: 2013-8-18 14:08:39
File Name   : zzz.cpp
*********************************************** */#include 
#include 
#include 
using namespace std;const int maxn = 500+10;struct TAXI {int time, x1, y1, x2, y2;
}a[maxn];int n, match[maxn];
bool vis[maxn], mp[maxn][maxn];bool dfs(int i) {for(int j = 1;j <= n; j++) if(mp[i][j] && !vis[j]) {vis[j] = 1;if(!match[j] || dfs(match[j])) {match[j] = i;return true;}}return false;
}int main() {int i, j, t;scanf("%d", &t);while(t--) {scanf("%d", &n);for(i = 1;i <= n; i++) {int hour, minute;scanf("%d:%d%d%d%d%d", &hour, &minute, &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);a[i].time = hour*60 + minute;// 直接把时间全部转换成分钟，这样更好判断了。}for(i = 1;i <= n; i++) {mp[i][i] = 0;int time = a[i].time;for(j = 1;j <= n; j++) if(j != i) {int ti = time + abs(a[i].x1 - a[i].x2) + abs(a[i].y1 - a[i].y2);ti += abs(a[i].x2 - a[j].x1) + abs(a[i].y2 - a[j].y1);if(ti < a[j].time)mp[i][j] = 1;elsemp[i][j] = 0;}}for(i = 1;i <= n; i++)  match[i] = 0;int ans = 0;for(i = 1;i <= n; i++) {for(j = 1;j <= n; j++)  vis[j] = 0;if(dfs(i))  ans++;}printf("%d\n", n - ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！