淘宝客单页网站程序,注册账号,手机app免费下载,洞头区小程序模板源代码题干#xff1a; 粘贴不过来。。。
题目大意#xff1a; 500*500带权格子#xff0c;每行每列要确定一个值#xff0c;使row[i]col[j] val[i][j]#xff0c;要使所有row值和col值的和最小
输出每行的row[i],和每列的col[i]。
解题报告#xff1a; 跑一边KM#…题干 粘贴不过来。。。
题目大意 500*500带权格子每行每列要确定一个值使row[i]col[j] val[i][j]要使所有row值和col值的和最小
输出每行的row[i],和每列的col[i]。
解题报告 跑一边KM自带着就把我们需要的期望值给求出来了。
AC代码
#include iostream
#include cstring
#include cstdiousing namespace std;
const int MAXN 505;
const int INF 0x3f3f3f3f;
int line[MAXN][MAXN];
int ex[MAXN],ey[MAXN];
bool visx[MAXN];
bool visy[MAXN];
int nxt[MAXN];
int slack[MAXN];
int N;
bool dfs(int x) {visx[x] 1;for (int y 1; y N; y) {if (visy[y]) continue; int tmp ex[x] ey[y] - line[x][y];if (tmp 0) {visy[y] 1;if (nxt[y] -1 || dfs( nxt[y] )) {nxt[y] x;return 1;}} else if(slack[y] tmp) slack[y] tmp;}return 0;
}
int KM() {memset(nxt, -1, sizeof nxt);memset(ey, 0, sizeof ey);for (int i 1; i N; i) {ex[i] line[i][1];for (int j 2; j N; j) {ex[i] max(ex[i], line[i][j]);}}for (int i 1; i N; i) {fill(slack, slack N 1, INF);while (1) {memset(visx, 0, sizeof visx);memset(visy, 0, sizeof visy);if (dfs(i)) break;int d INF;for (int j 1; j N; j)if (!visy[j]) d min(d, slack[j]);for (int j 1; j N; j) {if (visx[j]) ex[j] - d;if (visy[j]) ey[j] d;else slack[j] - d;}}}int res 0;for (int i 1; i N; i) res line[ nxt[i] ][i];return res;
}
int main() {while (~scanf(%d,N)) {for (int i 1; i N; i)for (int j 1; j N; j)scanf(%d, line[i][j]);int ans KM();for(int i 1; iN; i) {printf(%d%c,ex[i],i N ? \n : );}for(int i 1; iN; i) {printf(%d%c,ey[i],i N ? \n : );}printf(%d\n,ans);}return 0;
}
