这题想了很久，今天才想明白。。
写下我的心路历程。供大家参考吧，希望能别像我这样这么久才明白。
题意：
n栋大楼，每个大楼里ni个人，m个避难所，每个避难所能容纳mi个人。每个建筑物都有坐标，每个人到达避难所的费用是距离+1。给了你一种安排，问这种安排是不是最优的。
题解：
消圈定理：残留网络里如果存在负费用圈，那么当前流不是最小费用流。因为你绕着这个圈走一遍，费用更小了。
所以题中给的到底是不是最优的，那么我们就在他建的图的残留网络里找有没有负费用圈就好了。
因为大楼i到避难所j的边容量肯定是MX，所以残留网络一定有i到j的边，费用为距离。所以建边 add(i,j+n,p)。
如果大楼i到避难所j有人去避难，那么残路网络里一定有反边。所以建边add(j+n,i,-p)。
如果避难所j有人来避难，那么残留网络里一定有j到汇点的反边。所以建边add(0,j+n,0)。我把汇点设为0了。
如果避难所j来避难的人数少于他所能承受的人数，那残留网络里一定有残留的正边。所以建边add(j+n,0,0)。
至此，建边结束。 你首先要明白这题要是他不给你他的方案，你要怎么建边，然后你才能知道残留网络是什么。
然后根据图用spfa找负圈。有负圈的话从在spfa跳出的那点开始，找一个圈，因为我们假设从v跳出的spfa，但v不一定在这个圈里。所以我们要自己找圈。
找到圈后，开始更改流量，把这个圈里的所有边的流量+1。pre[now] 到 now这个边，如果 pre[now] >n，就说明pre[now]这点是避难所，now是大楼，这条边是反边，所以map里这个值-1，因为这里存的是正边的流量。同理 如果pre[now]<=n，就说明pre[now]这点时大楼，now是避难所，这条是正边，map的值+1。map里面存的都是正边的流量。
结束了。
#include<stdio.h>
#include<string.h>
#define MX 10000000
#define nMax 300
#define eMax 55555
struct Egde{
int u,v,w,next,pre; // u起点 v终点 c容量 f流量 w费用 next下一条边 pre反边
}eg[eMax];
struct building{
int x,y,numb;
}build[nMax];
struct shelter{
int x,y,numb;
}shel[nMax];
int n, m, ans,vs,vt,map[nMax][nMax];
int k, list[nMax];
int que[nMax*nMax], pre[nMax], dis[nMax];
int cnt[nMax];
bool vis[nMax];
void add(int u, int v, int w){//u起点，v终点，c容量，w费用
eg[k].u=u;eg[k].v=v;eg[k].next=list[u];eg[k].w=w;list[u]=k++;
}
int spfa(){
int i, head = 0, tail = 1;
for(i = vs; i <= vt; i ++){//源点到汇点初始化
dis[i] = MX;
vis[i] = false;
cnt[i]=0;
}
dis[vs] = 0;
que[0] = vs;
vis[vs] = true;
cnt[vs]++;
while(tail > head){
int u = que[head ++];
for(i = list[u]; i != -1; i = eg[i].next){
int v = eg[i].v;
if(dis[v] > dis[u] + eg[i].w){
dis[v] = dis[u] + eg[i].w;
pre[v] = u;
if(!vis[v]){
vis[v]=true;
que[tail ++] = v;
if(++cnt[v]>vt){
return v;
}
}
}
}
vis[u] = false;
}
return -1;
}
int abs(int a){
return a>0?a:-a;
}
int distance(int u,int v){
return abs(build[u].x-shel[v].x)+abs(build[u].y-shel[v].y);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
int number[nMax];
memset(list,-1,sizeof(list));
ans = 0;
k=0;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&build[i].x,&build[i].y,&build[i].numb);
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&shel[i].x,&shel[i].y,&shel[i].numb);
}
memset(number,0,sizeof(number));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&map[i][j]);
add(i,j+n,distance(i,j));
number[j]+=map[i][j];
if(map[i][j]){
add(j+n,i,-distance(i,j));
}
}
}
for(int i=1;i<=m;i++){
if(number[i]){
add(0,i+n,0);
if(number[i]<shel[i].numb){
add(i+n,0,0);
}
}
}
vs=0;
vt=n+m;
int u=spfa();
if(u==-1){
printf("OPTIMAL\n");
}
else{
printf("SUBOPTIMAL\n");
memset(vis,0,sizeof(vis));
int v=u,now;
while(vis[pre[v]]==0){
vis[v]=1;
v=pre[v];
}
now=v;
do{
if(pre[now]<=n && now>n){
map[pre[now]][now-n]++;
}
if(pre[now]>n && now<=n){
map[now][pre[now]-n]--;
}
now=pre[now];
}
while(now!=v);
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
printf("%d ",map[i][j]);
}
printf("%d\n",map[i][m]);
}
}
}
return 0;
}
边开小了。。RE。
队列开小了。。TLE好久。。
一开始map中 pre[now]忘记-n了
distance 中 abs直接加在最外边了。。却忘了有可能一正一负。。。