abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S3739 【匹配】

发表于 更新于

Description

给你一个 $n \times n$ 的矩阵 $A$，现在从中选出 $n$ 个数，使得它们中的任意两个不同行、不同列，求在和最大的方案中有哪些点是必选的，你需要求出最大的和以及这些点的坐标。

Solution

带权的二分图匹配为费用流的经典问题。

将矩阵中的数视为费用，规定所有边的流量都为 1，那么点 $(i, j)$ 即可视作一条从点 $i$ 到点 $(j + n)$ 的一条边，然后跑最大费用最大流即可。

对于判定一个点是否是必选的，只需要把这个点所代表的边去掉，然后再跑一边最大费用最大流比较一下就好了。

优化：只有在第一次跑最大费用最大流时满流的边才有可能是必选的，因为这条边至少在一种最优方案中。

Code

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <cstdio>
#define S 0
#define T 165
#define inf 999999999
#define maxN 170
#define maxM 10010
struct edge{ int x, y, c, w, g; } b[maxM << 1];
int Ans = 0, len = 1, n = 0;
int cost[maxN][maxN];
int h[maxN], f[maxN], a[maxN], v[maxN], fr[maxN], jl[maxN], dis[maxN], cur[maxN];
int read ()
{
	int x = 0;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x;
}
int min (int x, int y)
{
	return x < y ? x : y;
}
int max (int x, int y)
{
	return x > y ? x : y;
}
void ins (int x, int y, int c, int w)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].c = c;
	b[len].w = w;
	b[len].g = h[x];
	h[x] = len;
	
	len++;
	b[len].x = y;
	b[len].y = x;
	b[len].c = 0;
	b[len].w = -w;
	b[len].g = h[y];
	h[y] = len;
 }
bool SPFA ()
{
	int tou = 1, wei = 2;
	f[1] = S;
	v[S] = 1;
	const int N = (n << 1);
	for(register int i = S;i <= N; i++)
	{
		a[i] = inf;
		dis[i] = -inf;
	}
	a[T] = dis[T] = -inf;
	dis[S] = 0;
	while(tou != wei)
	{
		int x = f[tou];
		for(register int i = h[x];i;i = b[i].g)
		{
			int y = b[i].y;
			if(b[i].c)
			{
				if(dis[x] + b[i].w > dis[y])
				{
					fr[y] = i;
					dis[y] = dis[x] + b[i].w;
					a[y] = min(a[x], b[i].c);
					if(!v[y])
					{
						v[y] = 1;
						f[wei++] = y;
						if(wei >= maxN)
						{
							wei = 1;
						}
					}
				}
			}
		}
		v[x] = 0;
		tou++;
		if(tou >= maxN)
		{
			tou = 1;
		}
	}
	if(dis[T] != -inf)
	{
		Ans += dis[T] * a[T];
		int num = fr[T];
		while(num)
		{
			b[num].c -= a[T];
			b[num ^ 1].c += a[T];
			num = fr[b[num].x];
		}
		return true;
	}
	return false;
}
int main ()
{
	n = read();
	for(register int i = 1;i <= n; i++)
	{
		ins(S, i, 1, 0);
	}
	for(register int i = 1;i <= n; i++)
	{
		for(register int j = 1;j <= n; j++)
		{
			int x = read();
			ins(i, j + n, 1, x);
			cost[i][j] = x;
		}
	}
	for(register int i = 1;i <= n; i++)
	{
		ins(i + n, T, 1, 0);
	}
	while(SPFA());
	printf("%d\n", Ans);
	int ANS = Ans;
	for(register int i = 2;i <= len; i += 2)
	{
		if(!b[i].c && b[i].x != S && b[i].y != T)
		{
			jl[++jl[0]] = i;
		}
	}
	for(register int now = 1;now <= jl[0]; now++)
	{
		Ans = 0;
		for(register int i = 2;i <= len; i++)
		{
			b[i].c = (b[i].x <= n || b[i].y > n);
		}
		b[jl[now]].c = 0;
		while(SPFA());
		if(Ans != ANS)
		{
			printf("%d %d\n", b[jl[now]].x, b[jl[now]].y - n);
		}
	}
	return 0;
}