hdu2255 奔小康赚大钱 KM 算法

参见这里
#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n, a[305][305], mat[305], exu[305], exv[305], qiw[305];

const int oo=0x3f3f3f3f;

bool viu[305], viv[305];

bool dfs(int x){

	viu[x] = true;

	for(int i=1; i<=n; i++){

		if(viv[i])	continue;

		int gap=exu[x]+exv[i]-a[x][i];

		if(!gap){

			viv[i] = true;

			if(!mat[i] || dfs(mat[i])){

				mat[i] = x;

				return true;

			}

		}

		else qiw[i] = min(qiw[i], gap);

	}

	return false;

}

int main(){

	while(scanf("%d", &n)!=EOF){

		for(int i=1; i<=n; i++)

			for(int j=1; j<=n; j++)

				scanf("%d", &a[i][j]);

		memset(mat, 0, sizeof(mat));

		memset(exu, 0, sizeof(exu));

		memset(exv, 0, sizeof(exv));

		for(int i=1; i<=n; i++)

			for(int j=1; j<=n; j++)

				exu[i] = max(exu[i], a[i][j]);

		for(int i=1; i<=n; i++){

			memset(qiw, 0x3f, sizeof(qiw));

			while(true){

				memset(viu, 0, sizeof(viu));

				memset(viv, 0, sizeof(viv));

				if(dfs(i))	break;

				int tmp=oo;

				for(int j=1; j<=n; j++)

					if(!viv[j])

						tmp = min(tmp, qiw[j]);

				for(int j=1; j<=n; j++){

					if(viu[j])	exu[j] -= tmp;

					if(viv[j])	exv[j] += tmp;

					else	qiw[j] -= tmp;

				}

			}

		}

		int ans=0;

		for(int i=1; i<=n; i++)

			ans += a[mat[i]][i];

		printf("%d\n", ans);

	}

	return 0;

}
巴特西

hdu2255 奔小康赚大钱 KM 算法

最新文章

热门文章
