题解 P4014 【分配问题】
Ireliaღ
2019-04-09 09:44:25
**费用流经典题目，我用的指针版Zkw费用流。**
### 建图
* 设$0$为超级原点，$2 \times n + 1$为超级汇点。第$i$个人的节点为$i$，第$j$件工作的节点为$n + j$
* 从$0$向$\forall i \in [1,n]$连接容量为$1$，费用为$0$的边
* 从$\forall j \in [n + 1, 2 \times n]$向$2 \times n + 1$连接容量为$1$，费用为$0$的边
* 从$\forall i \in [1, n]$向$\forall j \in [n + 1, n \times 2]$连接容量为$1$，费用为$c_{i, j}$的边
然后跑一遍最小费用最大流，跑一遍最大费用最大流，分别输出两次得到的费用即可。打一个板子复制粘贴一遍就行了。代码如下
```cpp
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int n;
struct Edge{
int to, val, cost;
Edge *next, *ops;
Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
};
namespace Zkw1{
Edge *head[MAXN << 1];
bool vis[MAXN << 1];
int dis[MAXN << 1];
int s, t, res ,ans;
void AddEdge(int u, int v, int w, int c) {
head[u] = new Edge(v, w, c, head[u]);
head[v] = new Edge(u, 0, -c, head[v]);
head[u]->ops = head[v]; head[v]->ops = head[u];
}
bool Spfa() {
memset(dis, INF, sizeof(dis));
memset(vis, false, sizeof(vis));
deque<int> q; q.push_back(s); vis[s] = true; dis[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop_front();
vis[u] =false;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (e->val > 0 && dis[u] + e->cost < dis[v]) {
dis[v] = dis[u] + e->cost;
if (!vis[v]) {
vis[v] = true;
if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[t] < INF;
}
int Dfs(int u, int flow) {
vis[u] = true;
if (u == t) {
res += flow;
return flow;
}
int used = 0;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if ((v == t || !vis[v]) && e->val > 0 && dis[v] == dis[u] + e->cost) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
used += mi;
e->val -= mi;
e->ops->val += mi;
ans += e->cost * mi;
}
if (used == flow) break;
}
}
return used;
}
void Work() {
res = ans = 0;
while (Spfa()) {
vis[t] = true;
while (vis[t]) {
memset(vis, false, sizeof(vis));
Dfs(s, INF);
}
}
}
}
namespace Zkw2{
Edge *head[MAXN << 1];
bool vis[MAXN << 1];
int dis[MAXN << 1];
int s, t, res ,ans;
void AddEdge(int u, int v, int w, int c) {
head[u] = new Edge(v, w, c, head[u]);
head[v] = new Edge(u, 0, -c, head[v]);
head[u]->ops = head[v]; head[v]->ops = head[u];
}
bool Spfa() {
//memset(dis, -INF, sizeof(dis));
for (int i = 1; i <= 2 * n + 1; i++) dis[i] = -INF;
memset(vis, false, sizeof(vis));
deque<int> q; q.push_back(s); vis[s] = true; dis[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop_front();
vis[u] =false;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (e->val > 0 && dis[u] + e->cost > dis[v]) {
dis[v] = dis[u] + e->cost;
if (!vis[v]) {
vis[v] = true;
if (!q.empty() && dis[v] > dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[t] > -INF;
}
int Dfs(int u, int flow) {
vis[u] = true;
if (u == t) {
res += flow;
return flow;
}
int used = 0;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if ((v == t || !vis[v]) && e->val > 0 && dis[v] == dis[u] + e->cost) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
used += mi;
e->val -= mi;
e->ops->val += mi;
ans += e->cost * mi;
}
if (used == flow) break;
}
}
return used;
}
void Work() {
res = ans = 0;
while (Spfa()) {
vis[t] = true;
while (vis[t]) {
memset(vis, false, sizeof(vis));
Dfs(s, INF);
}
}
}
}
int main() {
ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
Zkw1 :: s = 0; Zkw1 :: t = n * 2 + 1; Zkw2 :: s = 0; Zkw2 :: t = n * 2 + 1;
for (int i = 1; i <= n; i++) Zkw1 :: AddEdge(0, i, 1, 0), Zkw1 :: AddEdge(i + n, n * 2 + 1, 1, 0), Zkw2 :: AddEdge(0, i, 1, 0), Zkw2 :: AddEdge(i + n, n * 2 + 1, 1, 0);
for (int i = 1; i <= n; i++) {
for (int j =1; j <= n; j++) {
int x;
cin >> x;
Zkw1 :: AddEdge(i, n + j, 1, x);
Zkw2 :: AddEdge(i, n + j, 1, x);
}
}
Zkw1 :: Work(); Zkw2 :: Work();
cout << Zkw1 :: ans << endl << Zkw2 :: ans << endl;
return 0;
}
```