P4014 分配问题

\(\color{#0066ff}{题目描述}\)

有 \(n\) 件工作要分配给 \(n\) 个人做。第 \(i\) 个人做第 \(j\) 件工作产生的效益为 \(c_{ij}\) 。试设计一个将 \(n\) 件工作分配给 \(n\) 个人做的分配方案，使产生的总效益最大。

\(\color{#0066ff}{输入格式}\)

文件的第 \(1\) 行有 \(1\) 个正整数 \(n\)，表示有 \(n\) 件工作要分配给 \(n\) 个人做。

接下来的 \(n\) 行中，每行有 \(n\) 个整数 \(c_{ij}\) ，表示第 \(i\) 个人做第 \(j\) 件工作产生的效益为 \(c_{ij}\) 。

\(\color{#0066ff}{输出格式}\)

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

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

5

14

\(\color{#0066ff}{数据范围与提示}\)

none

\(\color{#0066ff}{题解}\)

裸的费用流。。。

好像可以二分图最大带权匹配。。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <queue>

#include <algorithm>

#include <cmath>

#define _ 0

#define LL long long

inline LL in() {

	LL x = 0, f = 1; char ch;

	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);

	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();

	return x * f;

}

int n, m, s, t;

const int maxn = 105050;

const int inf = 0x7fffffff;

struct node {

	int to, dis, can;

	node *nxt, *rev;

	node(int to = 0, int dis = 0, int can = 0, node *nxt = NULL):to(to), dis(dis), can(can), nxt(nxt) {}

	void *operator new (size_t) {

		static node *S = NULL, *T = NULL;

		return (S == T)&&(T = (S = new node[1024]) + 1024) , S++;

	}

};

typedef node* nod;

nod head[maxn], road[maxn];

int dis[maxn], change[maxn];

bool vis[maxn];

int c[120][120];

std::queue<int> q;

inline void add(int from, int to, int dis, int can) {

	nod o = new node(to, dis, can, head[from]);

	head[from] = o;

}

inline void link(int from, int to, int dis, int can) {

	add(from, to, dis, can);

	add(to, from, -dis, 0);

	head[from]->rev = head[to];

	head[to]->rev = head[from];

}

inline bool spfa1() {

	for(int i = s; i <= t; i++) dis[i] = inf, change[i] = inf;

	dis[s] = 0;

	q.push(s);

	while(!q.empty()) {

		int tp = q.front(); q.pop();

		vis[tp] = false;

		for(nod i = head[tp]; i; i = i->nxt) {

			if(dis[i->to] > dis[tp] + i->dis && i->can > 0) {

				dis[i->to] = dis[tp] + i->dis;

				road[i->to] = i;

				change[i->to] = std::min(change[tp], i->can);

				if(!vis[i->to]) vis[i->to] = true, q.push(i->to);

			}

		}

	}

	return change[t] != inf;

}

inline bool spfa2() {

	for(int i = s; i <= t; i++) dis[i] = -inf, change[i] = inf;

	dis[s] = 0;

	q.push(s);

	while(!q.empty()) {

		int tp = q.front(); q.pop();

		vis[tp] = false;

		for(nod i = head[tp]; i; i = i->nxt) {

			if(dis[i->to] < dis[tp] + i->dis && i->can > 0) {

				dis[i->to] = dis[tp] + i->dis;

				road[i->to] = i;

				change[i->to] = std::min(change[tp], i->can);

				if(!vis[i->to]) vis[i->to] = true, q.push(i->to);

			}

		}

	}

	return change[t] != inf;

}

inline void mcmf1()

{

	int cost = 0;

	while(spfa1()) {

		cost += change[t] * dis[t];

		for(int i = t; i != s; i = road[i]->rev->to) {

			road[i]->can -= change[t];

			road[i]->rev->can += change[t];

		}

	}

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

}

inline void mcmf2()

{

	int cost = 0;

	while(spfa2()) {

		cost += change[t] * dis[t];

		for(int i = t; i != s; i = road[i]->rev->to) {

			road[i]->can -= change[t];

			road[i]->rev->can += change[t];

		}

	}

	printf("%d", cost);

}

int main() {

	n = in();

	s = 0, t = (n << 1) + 1;

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

		link(s, i, 0 ,1);

		link(i + n, t, 0, 1);

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

			link(i, j + n, c[i][j] = in(), 1);

	}

	mcmf1();

	for(int i = s; i <= t; i++) head[i] = NULL;

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

		link(s, i, 0 ,1);

		link(i + n, t, 0, 1);

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

			link(i, j + n, c[i][j], 1);

	}

	mcmf2();

	return 0;

}

巴特西