第二个读入里面 $i,j$ 反过来好了
by henry_qwh @ 2024-02-23 10:51:31
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define MAXN 410
using namespace std;
inline int read(){
int x = 0,f = 1;
char c = getchar();
while (!isdigit(c)){
if (c == '-') f = -1;
c = getchar();
}
while (isdigit(c)){
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
struct node{
int from,to,cost,c;
}edge[MAXN<<4];
int na,nb,p,q,tot = 1;
int s,t,id[MAXN][MAXN];
int dis[MAXN],flow[MAXN],pre[MAXN];
int head[MAXN];
bool vis[MAXN];
inline void addedge(int u,int v,int c,int w){
edge[++tot].c = c;
edge[tot].cost = w;
edge[tot].from = head[u];
edge[tot].to = v;
head[u] = tot;
//------//
edge[++tot].c = 0;
edge[tot].cost = -w;
edge[tot].from = head[v];
edge[tot].to = u;
head[v] = tot;
}
inline bool spfa(){
memset(dis,-0x3f,sizeof(dis));
memset(flow,0,sizeof(flow));
queue<int> q;
q.push(s);
dis[s] = 0;
vis[s] = 1;
flow[s] = INF;
while (!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for (int i=head[x];i;i=edge[i].from){
int v = edge[i].to;
int w = edge[i].c;
if(!w) continue;
if (dis[x]+edge[i].cost>dis[v]){
dis[v] = dis[x]+edge[i].cost;
pre[v] = i;
flow[v] = min(flow[x],w);
if (!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
return flow[t]>0;
}
inline int EK(){
int ans = 0;
while (spfa()){
int w = flow[t];
ans+=w*dis[t];
int x = t;
while (x != s){
edge[pre[x]].c -= w;
edge[pre[x]^1].c += w;
x = edge[pre[x]^1].to;
}
}
return ans;
}
int e[MAXN][MAXN];
signed main(){
na = read(),nb = read(),p = read(),q = read();
int idx = 0;
s = ++idx,t = ++idx;
for (int i=0;i<=p;i++){
for (int j=0;j<=q;j++){
id[i][j] = ++idx;
}
}
for (int i=0;i<=p;i++){
for (int j=0;j<q;j++){
e[i][j] = read();
addedge(id[i][j],id[i][j+1],1,e[i][j]);
addedge(id[i][j],id[i][j+1],INF,0);
}
}
for (int i=0;i<=q;i++){
for (int j=0;j<p;j++){
e[i][j] = read();
addedge(id[j][i],id[j+1][i],1,e[i][j]);
addedge(id[j][i],id[j+1][i],INF,0);
}
}
while (na--){
int w = read(),i = read(),j = read();
addedge(s,id[i][j],w,0);
}
while (nb--){
int w = read(),i = read(),j = read();
addedge(id[i][j],t,w,0);
}
cout<<EK()<<endl;
return 0;
}
```
by henry_qwh @ 2024-02-23 10:54:15
@[rhisea](/user/279771)
by henry_qwh @ 2024-02-23 10:54:29
@[henry_qwh](/user/421657) 谢谢大佬
by rhisea @ 2024-03-02 08:39:39