传送门 ↬\looparrowright

题目描述

有 nn 件工作要分配给 nn 个人做。第 ii 个人做第 jj 件工作产生的效益为 cijc_{ij}。试设计一个将 nn 件工作分配给 nn 个人做的分配方案，使产生的总效益最大。

输入格式

文件的第 11 行有 11 个正整数 nn，表示有 nn 件工作要分配给 nn 个人做。
接下来的 nn 行中，每行有 nn 个整数 cijc_{ij}，表示第 ii 个人做第 jj 件工作产生的效益为cijc_{ij}。

输出格式

两行分别输出最小总效益和最大总效益。

输入输出样例

输入 #1

5
2 2 2 1 2
2 3 1 2 4
2 0 1 1 1
2 3 4 3 3
3 2 1 2 1

输出 #1

5
14

说明/提示

1⩽n⩽1001 \leqslant n \leqslant 100。
一个人只能修一个工件。

分析

将全体工人看作点集 S1\mathbb{S_1}，将所有工作看作点集 S2\mathbb{S_2}；两个集合内部的点各自没有连边，S1\mathbb{S_1} 中的点向 S2\mathbb{S_2} 连边，边权为效益 cijc_{ij}；构建二分图最大权完备匹配模型。若要获得最小的效益，将边权取相反数，求一次最大权匹配，再将结果取相反数输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P4014
Date: 7/24/2020 
Description: KM Algorithm
*******************************************************************/
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int N=104;
const int inf=0x3f3f3f3f;
int lx[N],ly[N];
int c[N][N];
int match[N];
int pre[N];
bool vis[N];
int slack[N];
int n;
void init();
void bfs();
int KM();
int main()
{
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			scanf("%d",&c[i][j]);
			c[i][j]=-c[i][j];
		}
	}
	init();
	cout<<-KM()<<endl;
	init();
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			c[i][j]=-c[i][j];
		}
	}
	cout<<KM()<<endl;
	return 0;
}
void init()
{
	memset(lx,0,sizeof(lx));
	memset(ly,0,sizeof(ly));
	memset(match,-1,sizeof(match));
}
void bfs(int id)
{
	int px,py=0;
	match[py]=id;
	int d;
	int i;
	int temp=0;
	do
	{
		px=match[py];
		d=inf;
		vis[py]=1;
		for(i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				if(slack[i]>lx[px]+ly[i]-c[px][i])
				{
					slack[i]=lx[px]+ly[i]-c[px][i];
					pre[i]=py;
				}
				if(slack[i]<d)
				{
					d=slack[i];
					temp=i;
				}
			}
		}
		for(i=0;i<=n;i++)
		{
			if(vis[i])
			{
				lx[match[i]]-=d;
				ly[i]+=d;
			}
			else slack[i]-=d;
		}
		py=temp;
	}while (~match[py]);
	while(py)
	{
		match[py]=match[pre[py]];
		py=pre[py];
	}
}
int KM()
{
	int i;
	for(i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		memset(pre,0,sizeof(pre));
		memset(slack,inf,sizeof(slack));
		bfs(i);
	}
	int res=0;
	for(i=1;i<=n;i++) if(~match[i]) res+=c[match[i]][i];
	return res;
}