欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分图最大权值完美匹配 hdu2255

程序员文章站 2022-06-07 14:42:49
...

hdu2255

二分图最大权值完美匹配 hdu2255


#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include <cctype>
#include<functional>
#include<memory.h>
#include<stack>
#include <cassert>
#include<set>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e4+5;
const int mod = 1e9 + 7;
const long long INF = 20050206000;
int n, m, s, t,last=0,cnt=0;
int graph[305][305];
int slack[305],match[305];
bool visp[305], vish[305];
int ex_p[305], ex_h[305];
bool dfs(int u) {
	visp[u] = true;
	for (int i = 1;i <= n;i++) {
		if (vish[i])continue;
		int gap = ex_p[u] + ex_h[i] - graph[u][i];
		
		if (gap == 0) {
			vish[i] = true;
			if (match[i] == -1 || dfs(match[i])) {
				match[i] = u;
				return true;
			}
		}
		else {
			slack[i] = min(slack[i], gap);
		}
		
	}
	return false;
}
int main() {
	while (scanf_s("%d",&n)!=EOF) {
		for (int i = 1;i <= n;i++) {
			for (int j = 1;j <= n;j++) {
				scanf_s("%d", &graph[i][j]);
			}
		}
		for (int i = 1;i <= n;i++) {
			match[i] = -1;
			ex_h[i] = 0;
		}
		for (int i = 1;i <= n;i++) {
			ex_p[i] = graph[i][1];
			for (int j = 1;j <= n;j++) {
				ex_p[i] = max(ex_p[i], graph[i][j]);
			}
		}
		for (int i = 1;i <= n;i++) {
			memset(slack, 0x3f, sizeof slack);
			while (1) {
				for (int i = 1;i <= n;i++) {
					vish[i] = visp[i] = 0;
				}
				if (dfs(i))break;
				int d = 0x3f3f3f3f;
				for (int j = 1;j <= n;j++) {
					if (!vish[j])d = min(d, slack[j]);
				}
				for (int j = 1;j <= n;j++) {
					if (visp[j])ex_p[j] -= d;
					if (vish[j])ex_h[j] += d;
					else {
						slack[j] -= d;
					}
				}
			}
		}
		int res = 0;
		for (int i = 1;i <= n;i++) {
			res += graph[match[i]][i];
		}
		printf("%d\n", res);
	}
}

相关标签: 算法入门