题目链接：https://www.luogu.org/problemnew/show/P4012
洛谷 P4012 深海机器人问题
输入输出样例
输入样例#1：
1 1
2 2
1 2
3 4
5 6
7 2
8 10
9 3
2 0 0
2 2 2
输出样例#1：
42
说明
题解：建图方法如下：
对于矩阵中的每个点，向东、向北分别与其相邻点都要连两条边（重边）：
1）容量为1，费用为该边价值的边；
2）容量为INF，费用为0的边（因为多个深海机器人可以在同一时间占据同一位置）。
对于每个起点：从S（源点）到这个点连：容量为该点机器人数，费用为0的边。
对于每个终点：从这个点到T（汇点）连：容量为该点机器人数，费用为0的边。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
const int M = N*+;
const int INF = 0x3f3f3f3f;
struct Edge { int to,next,cap,flow,cost; }edge[M];
int head[N],tol;
int pre[N],dis[N];
bool vis[N];
int V;
void init(int n) {
V = n;
tol = ;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int cap,int cost) {
edge[tol].to = v; edge[tol].cap = cap; edge[tol].cost = cost; edge[tol].flow = ; edge[tol].next = head[u]; head[u] = tol++;
edge[tol].to = u; edge[tol].cap = ; edge[tol].cost = -cost; edge[tol].flow = ; edge[tol].next = head[v]; head[v] = tol++;
}
bool spfa(int s,int t) {
queue<int>q;
for(int i = ;i < V;i++) {
dis[i] = INF;
vis[i] = false;
pre[i] = -;
}
dis[s] = ;
vis[s] = true;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i != -;i = edge[i].next) {
int v = edge[i].to;
if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ) {
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -) return false;
else return true;
}
int minCostMaxflow(int s,int t,int &cost) {
int flow = ;
cost = ;
while(spfa(s,t)) {
int Min = INF;
for(int i = pre[t];i != -;i = pre[edge[i^].to]) {
if(Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
}
for(int i = pre[t];i != -;i = pre[edge[i^].to]) {
edge[i].flow += Min;
edge[i^].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
}
int main() {
int a, b, p, q, k, x, y, i, j, ans = ;
scanf("%d%d", &a, &b);//出发和目的地数目
scanf("%d%d", &p, &q);
init((p+)*(q+)+); int s = (p+)*(q+)+, t = (p+)*(q+)+; for(i = ; i <= p; ++i) {//p+1行,向东移动
for(j = ; j < q; ++j) {
scanf("%d", &x);//边上的标本价值
addedge(i*(q+)+j, i*(q+)+j+, , -x);
addedge(i*(q+)+j, i*(q+)+j+, INF, );
}
}
for(j = ; j <= q; ++j) {//q+1列,向北移动
for(i = ; i < p; ++i) {
scanf("%d", &x);
addedge(i*(q+)+j, i*(q+)+j+q+, , -x);
addedge(i*(q+)+j, i*(q+)+j+q+, INF, );
}
}
for(i = ; i <= a; ++i) {//起点
scanf("%d%d%d", &k, &x, &y);
addedge(s, x*(q+)+y, k, );
}
for(i = ; i <= b; ++i) {//终点
scanf("%d%d%d", &k, &x, &y);
addedge(x*(q+)+y, t, k, );
}
minCostMaxflow(s, t, ans);
printf("%d\n", -ans);
return ;
}