这是我写的第一篇题解,希望不是最后一篇.因为我太懒了
题目描述
如题,不搬了
本题解假设读者了解,最大流/spfa费用流
以及二分图的基础知识,最大匹配
本题是二分图的最优匹配模板题,
举一个简单二分图最大匹配的例子,有n个男生m个女生,他们之间有t条男生对女生的暗恋关系,
但男生不能暗恋男生!因为我们会把这种暗恋关系看成一条有向无权边,那样就不是二分图了,同理女生也不能暗恋女生
一个男生可以暗恋多个女生,一个女生也可以被多个男生暗恋.
有暗恋关系一对男女可以凑成一对情侣,该例子中二分图最大匹配就是问最多能凑成多少对情侣呢?
我们把一张图的点分成左右两个集合,所有的边都是左集合连向右集合的有向边,满足这种条件的图称为二分图
我们把左边的集合称为左部点,右边的集合称为右部点,上例子中左部点就是男生,右部点就是女生
左部点连向右部点的边就是男生对女生的暗恋关系
一个点只能用一次,最多选出多少有向边,就是二分图的最大匹配
二分图最大匹配可以用匈牙利算法或者最大流算法求解
由于一个男生可能会暗恋多个女生,那么有可能对不同女生喜欢的程度是不一样的zhanan
我们利用男生对女生的暗恋关系看成一个带权值的有向边,用权值来表示喜欢程度,
权值越高越喜欢这个女生,男生选到最喜欢的女生肯定更开心!
那么二分图的最优匹配就是满足凑最多情侣数量情况下,使得选的暗恋关系的所有边权之和最大/最小!
或者说选出的边权值之和最大,一个点只能用一次
题中$C_i$$_j$表示第i个人做第j项工作所需的费用
把所有的人看做二分图的左部点,把工作看成二分图的右部点
而边呢,就是哪一个人去做哪一份工作,
取S为虚拟源点,T为虚拟汇点
S向所有的人连流量是1费用是0的有向边,
所有的工作向T连流量是1费用是0的有向边
第i个人向第j份工作连一条流量是1费用是$C_i$$_j$的有向边,
同样连一条费用是$-C_i$$_j$流量是0的反向边
其中反向边的作用见上面的最大流/spfa费用流
粗略的说,反向边就是一个男生选了一个妹子发现,无法使得总权值之和最大/最小,
让这个男生去选其他的女生或者单身,因为要求总权值和最大/最小,所以可以走反向边再找增广路
先求最小费用最大流,然后取反费用,求最大费用最大流
我们使用最小费用最大流来求解此问题,而不用KM算法因为我不会
C++代码 36 ms
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 200, M = N * N, inf = 0x3f3f3f3f;
int n, S, T, idx = 2, mincost, maxflow;
int h[N], e[M], ne[M], f[M], cos[M];
int pre[N], flow[N], cost[N], st[N];
int g[N][N];
//其中通过spfa求出cost[T]代表一单位的流量流到终点需要多少费用,flow[T]代表起点到终点最多能流多少流量
bool spfa()
{
queue<int> q;
memset(cost, 63, sizeof cost);
memset(st, 0, sizeof st);
cost[S] = 0;
flow[S] = inf;
q.push(S);
while (q.size())
{
int p = q.front();
q.pop();
st[p] = false;
for (int i = h[p]; i != 0; i = ne[i])
{
int j = e[i];
if (cost[j] > cost[p] + cos[i] && f[i])
{
cost[j] = cost[p] + cos[i];
flow[j] = min(flow[p], f[i]);
pre[j] = i;
if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
return cost[T] != inf;
}
int mincost_maxflow()
{
maxflow = mincost = 0;
while (spfa())
{
//flow[T]代表起点到终点,这一次增广路,最多能流多少流量
maxflow += flow[T];
//其中通过spfa求出cost[T]代表一单位的流量流到终点需要多少费用,一共流了flow[T]单位的流量
//一共花了flow[T] * cost[T]的花费
mincost += flow[T] * cost[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
{
f[pre[i]] -= flow[T];
f[pre[i] ^ 1] += flow[T];
}
}
return mincost;
}
void add(int a, int b, int c, int d)
{
e[idx] = b;
f[idx] = c;
cos[idx] = d;
ne[idx]=h[a];
h[a]=idx++;
e[idx]=a;
f[idx]=0;
cos[idx]=-d;
ne[idx]=h[b];h[b]=idx++;
}
int main(int argc, char)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &g[i][j]);
S=n+n+1,T=S+1;
for (int i = 1; i <= n; i++)
add(S, i, 1, 0), add(i + n, T, 1, 0);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
add(i, j + n, 1, g[i][j]);
printf("%d\n", mincost_maxflow());
idx = 2;
memset(h, 0, sizeof(h));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
add(i, j + n, 1, -g[i][j]);
for (int i = 1; i <= n; i++)
add(S, i, 1, 0), add(i + n, T, 1, 0);
printf("%d", -mincost_maxflow());
return 0;
}
Java 代码 快速读 332 ms 不带快速读是1240 ms
Java 你快点啊,给Java倒一杯卡布奇诺
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
/**
* AC
* 最大匹配最大费用
*
* 有 n 件工作要分配给 n 个人做。
* 第 i 个人做第 j 件工作产生的效益为 cij。
* 试设计一个将 n 件工作分配给 n 个人做的分配方案。
* 对于给定的 n 件工作和 n 个人,计算最优分配方案和最差分配方案。
* 输入格式
* 第 1 行有 1 个正整数 n,表示有 n 件工作要分配给 n 个人做。
* 接下来的 n 行中,每行有 n 个整数 cij,表示第 i 个人做第 j 件工作产生的效益为 cij。
* 输出格式
* 第一行输出最差分配方案下的最小总效益。
* 第二行输出最优分配方案下的最大总效益。
* 数据范围
* 1≤n≤50,
* 0≤cij≤100
* 输入样例:
* 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
* 输出样例:
* 5
* 14
* 二分图
* 费用流,最大费用,最小费用
*
*/
public class Main {
public static void main(String[] args) throws IOException {
n = nextInt();
S = n + n + 1;
T = n + n + 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = nextInt();
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
add(i, j + n, 1, g[i][j]);
}
}
for (int i = 1; i <= n; i++) {
add(S, i, 1, 0);
add(i + n, T, 1, 0);
}
min_cost_flow();
System.out.println(mincost);
idx = 2;
Arrays.fill(h, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
add(i, j + n, 1, -g[i][j]);
}
}
for (int i = 1; i <= n; i++) {
add(S, i, 1, 0);
add(i + n, T, 1, 0);
}
min_cost_flow();
System.out.println(-mincost);
}
static int N = 200, M = N * 200, T, n, inf = 0x3f3f3f3f, idx = 2, S, mincost, maxflow;
static int[] h = new int[N], e = new int[M], ne = new int[M], cos = new int[M], f = new int[M];
static ArrayDeque<Integer> q = new ArrayDeque<>();
static int[] pre = new int[N];
static int[] flow = new int[N], cost = new int[N];
static int[][] g = new int[100][100];
static boolean[] st = new boolean[N];
static void add(int a, int b, int c, int d) {
e[idx] = b;
f[idx] = c;
cos[idx] = d;
ne[idx] = h[a];
h[a] = idx++;
e[idx] = a;
f[idx] = 0;
cos[idx] = -d;
ne[idx] = h[b];
h[b] = idx++;
}
static boolean spfa() {
q.clear();
Arrays.fill(cost, inf);
Arrays.fill(st, false);
cost[S] = 0;
flow[S] = inf;
q.add(S);
while (!q.isEmpty()) {
int p = q.poll();
st[p] = false;
for (int i = h[p]; i != 0; i = ne[i]) {
int j = e[i];
if (cost[j] > cost[p] + cos[i] && f[i] != 0) {
cost[j] = cost[p] + cos[i];
flow[j] = Math.min(f[i], flow[p]);
pre[j] = i;
if (!st[j]) {
st[j] = true;
q.add(j);
}
}
}
}
return cost[T] != inf;
}
private static void min_cost_flow() {
mincost = 0;
maxflow = 0;
while (spfa()) {
for (int i = T; i != S; i = e[pre[i] ^ 1]) {
f[pre[i]] -= flow[T];
f[pre[i] ^ 1] += flow[T];
}
maxflow += flow[T];
mincost += flow[T] * cost[T];
//1单位的流量流到终点需要cost[T]的费用,一共有flow[T]单位
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer stk = new StringTokenizer("");
static int nextInt() throws IOException {
while (!stk.hasMoreTokens())
stk = new StringTokenizer(br.readLine());
return Integer.parseInt(stk.nextToken());
}
}