有服务器有域名如何做网站,无锡网站建设原则,中航长江建设工程有限公司网站,石家庄网站制作福州题意#xff1a;给定两个关系矩阵#xff0c;分别表示雇主和雇员的相互好感度#xff0c;好感度为1最优#xff0c;N最差。如果一个人与好感度为P的人匹配的话#xff0c;差值为P-1#xff0c;现在要求是的总共的差值最小的匹配方法#xff0c;并且输出所有的匹配方案。…题意给定两个关系矩阵分别表示雇主和雇员的相互好感度好感度为1最优N最差。如果一个人与好感度为P的人匹配的话差值为P-1现在要求是的总共的差值最小的匹配方法并且输出所有的匹配方案。 解法将两两关系矩阵转化为边上的权值然后进行一次最大匹配最后dfs枚举输出结果数据中给的矩阵上下颠倒了。 代码如下 #include cstdlib
#include cstdio
#include cstring
#include algorithm
#include iostream
#include cmath
using namespace std;const int INF 0x3f3f3f3f;int N, sum, cnt;
int mp1[20][20], mp2[20][20];
int w[20][20];
int lx[20], ly[20], sx[20], sy[20];
int match[20], slack[20];void build() {for (int i 1; i N; i) {for (int j 1; j N; j) {w[i][j] -mp1[i][j]-mp2[i][j]; // 转化为最大匹配问题 }}
}bool path(int u) {sx[u] 1;for (int i 1; i N; i) {if (sy[i]) continue;int t lx[u]ly[i]-w[u][i];if (!t) {sy[i] 1;if (!match[i] || path(match[i])) {match[i] u;return true; }} else {slack[i] min(slack[i], t); }}return false;
}void KM() {memset(match, 0, sizeof (match));memset(ly, 0, sizeof (ly));memset(lx, 0x80, sizeof (lx));for (int i 1; i N; i) {for (int j 1; j N; j) {lx[i] max(lx[i], w[i][j]); }}for (int i 1; i N; i) {memset(slack, 0x3f, sizeof (slack));while (1) {memset(sx, 0, sizeof (sx));memset(sy, 0, sizeof (sy));if (path(i)) break;int d INF;for (int j 1; j N; j) {if (!sy[j]) d min(d, slack[j]);}for (int j 1; j N; j) {if (sx[j]) lx[j] - d;if (sy[j]) ly[j] d;else slack[j] - d;}}}
}void dfs(int u, int tot, int deep) {if (tot sum) return;if (deep N) { // 匹配数量达到N printf(Best Pairing %d\n, cnt);for (int i 1; i N; i) {printf(Supervisor %d with Employee %d\n, i, match[i]); }return;}for (int i 1; i N; i) {if (!sy[i]) {sy[i] 1;match[u] i;dfs(u1, totw[u][i], deep1);sy[i] 0;}}
}void output(int ca) {double ret 0;sum cnt 0;for (int i 1; i N; i) {ret w[match[i]][i];sum w[match[i]][i];}ret fabs(-ret / (2*N));printf(Data Set %d, Best average difference: %f\n, ca, ret);memset(sy, 0, sizeof (sy));dfs(1, 0, 0);
}int main() {int T, x, ca 0;scanf(%d, T);while (T--) {scanf(%d, N);for (int i 1; i N; i) {for (int j 0; j N; j) {scanf(%d, x);mp1[x][i] j; // 对第x个候选人的好感度排第j }}for (int i 1; i N; i) {for (int j 0; j N; j) {scanf(%d, x);mp2[i][x] j;}}build();KM();output(ca);if (T) puts();}return 0;
} 转载于:https://www.cnblogs.com/Lyush/archive/2013/04/10/3013366.html
