题意:一个城市有n座行政楼和m座避难所，现发生核战，要求将避难所中的人员全部安置到避难所中，每个人转移的费用为两座楼之间的曼哈顿距离+1,题目给了一种方案，问是否为最优方案,即是否全部的人员转移费用之和最小?若不是，输出SUBOPTIMAL,之后输出转移矩阵Ei,j.即第i座行政楼中Ei,j个人转移到第j座避难所;输出的不必是最优转移方案，只要比题解的sum小即可；
思路:直接建一个残量网络，即按照开始建的原图跑完最小费用流之后剩下的网络，行政楼和避难所之间的原图连边正向容量为inf,反向为0。之后反向从汇点t跑最短路，看是否存在一个负圈，若存在负圈则说明题目解的并不是最优解，这时找到圈中一点，把圈中权值为正(正向边)的流量-1,为负的流量加1即可；
负圈:圈中所有边的流量为正(跑spfa时可行)，并且总的权值之和为负(不断地更新dist，直到有一点的序号超过总点数)；
注:从spfa中跳出的点并不是就是圈中的点，可能开始时就弄进去负边权，导致之后出圈了序号才大于点数；
ps: sb地竟然是一直MLE...，但是返回WA，图中的边数为n*n(没算源汇连边)..
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
#include<stack>
#include<set>
#include<map>
#include<queue>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
typedef long long ll;
#define A first
#define B second
#define MK make_pair
typedef __int64 ll;
template<typename T>
void read1(T &m)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>9) out(a/10);
putchar(a%10+'0');
}
int T,kase = 1,i,j,k,n,m,s,t;
const int M = 25007;
const int N = 207;
int head[M],tot;
struct Edge{
int from,to,cap,Next,w;
Edge(){}
Edge(int f,int to,int cap,int w,int Next):from(f),to(to),cap(cap),Next(Next),w(w){}
}e[M<<1];
inline void ins(int u,int v,int cap,int w)
{
e[++tot] = Edge{u,v,cap,w,head[u]};
head[u] = tot;
}
int dist[N][N];
struct data{int x,y,c;}X[N],Y[N];
void calc()
{
rep1(i,1,n)
rep1(j,1,m) //这和之后的建图并不一样;
dist[i][j] = abs(X[i].x - Y[j].x) + abs(X[i].y - Y[j].y) + 1;
}
int sum[N],ans[N][N];
int inq[N],d[N],num[N],p[N];
queue<int> Q;
int spfa()
{
while(!Q.empty()) Q.pop();
MSi(d);MS0(inq);MS0(num);
Q.push(t);
inq[t] = 1;d[t] = 0;num[t] = 1;
while(!Q.empty()){
int u = Q.front();Q.pop();
inq[u] = 0;
for(int id = head[u];id;id = e[id].Next){
int v = e[id].to;
if(d[v] > d[u] + e[id].w && e[id].cap){ //负圈的判定,所有圈中的边费用均为正，费用之和为负;
d[v] = d[u] + e[id].w;
p[v] = u;
if(!inq[v]){
num[v] = num[u] + 1;
if(num[v] > n+m+2) return v;
Q.push(v);inq[v] = 1;
}
}
}
}
return -1;
}
int solve()
{
int st = spfa(),u,v;
if(st == -1){return puts("OPTIMAL"),0;}
puts("SUBOPTIMAL");
MS0(inq);
while(1){
if(!inq[st]) inq[st] = 1,st = p[st];
else{ v = st;break;}
}
do{
u = p[v];
if(u > n) ans[v][u-n]--;//正向边的费用为正，所以--将费用减少;
else ans[u][v-n]++;
v = u;
}while(v != st);
rep1(i,1,n){
printf("%d",ans[i][1]);
rep1(j,2,m) printf(" %d",ans[i][j]);
puts("");
}
}
int main()
{
while(scanf("%d%d",&n,&m) == 2){
MS0(head);tot = 1;
rep1(i,1,n) read3(X[i].x,X[i].y,X[i].c);
rep1(i,1,m) read3(Y[i].x,Y[i].y,Y[i].c);
calc();
s = 0, t = n + m + 1;
int w;
rep1(i,1,n)
rep1(j,1,m){
read1(w);
ans[i][j] = w;
ins(i,n+j,inf - w,dist[i][j]);//残余网络，但是边的权值没变
ins(n+j,i,w,-dist[i][j]);//原图中房子之间容量为inf和0；
sum[j] += w;
}
rep1(i,1,n) ins(s,i,0,0), ins(i,s,X[i].c,0);
rep1(j,1,m) ins(j+n,t,Y[j].c-sum[j],0), ins(t,j+n,sum[j],0);
solve();
}
return 0;
}