题目描述：

有n个建筑物，m个避难所，告诉你每个建筑物的坐标和拥有的人。告诉你每个避难所的坐标和容量。建筑物i和避难所j的距离为|xi-xj| + |yi-yj| + 1。现在要求把建筑物的人都疏散到避难所。给你一个方案，n行m列，i行j列表示建筑物i有x[i][j]的人去j避难所。

问你这个方案是不是最优的，不是的话，输出一个比给定方案好的方案即可（SPJ）。

解题报告：

         如果直接求最小费用流求出最优值输出，算法正确，但是会TLE，注意到题目不一定要求输出最优，好一点就可以。

         “可行流x为最小费用流的充要条件是残量网络中不存在负费用增广圈”

         按照这个条件，我们建立残量网络即可，由于要判断负圈，所以只要剩余容量大于0，就连接边即可，走几遍都无所谓。

         为了简化，可以不需要原来的源点（因为需要源点满流，所以不会沿着建筑物点走回源点当然建立了也无所谓）。

         省下的就是残量网络建图：

         所有的建筑物i和避难所j，连接ij，边权为正的距离。

         如果原方案i到j有人，连接ji，边权为负的距离。

         如果j避难所的人数大于0，连接汇点和j，边权0.

         如果j避难所没有满，连接j和汇点，边权0.

         这样，在残量网络中，容量大于0的边就都建立出来了。

         从汇点出发，找负圈，如果找到了，按照负圈的边，依次更改方案即可。

         比如负圈中有建筑物到i到避难所j的点，x[i][j]++

         如果有避难所j到建筑物i的点，x[i][j]—

         输出方案即可。

         代码如下：

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<queue>

using namespace std;

struct edge{int to, next, cost;}e[10000000];

int n, m, v[300], cnt;

void insert(int from, int to, int cost)

{

    e[cnt].to = to; e[cnt].cost = cost;

    e[cnt].next = v[from]; v[from] = cnt++;

}

int x[100][3], y[100][3], sum[100], ans[100][100];

int pre[300], vst[300], num[300], dis[300];

//pre记录负环，num入队列的次数,spfa返回最先入队>n的点

int g[100][100];

int spfa(int sta, int n)

{

    queue<int> que; que.push(sta); memset(vst, 0, sizeof(vst));

    memset(num, 0, sizeof(num));

    vst[sta] = 1; num[sta]++;

    for(int i = 0; i < n; i++) dis[i] = 100000000;

    dis[sta] = 0;

    while(!que.empty())

    {

        int id = que.front(); que.pop();

        vst[id] = 0;

        for(int i = v[id]; i != -1; i = e[i].next)

            if (dis[id] + e[i].cost < dis[e[i].to])

            {

                dis[e[i].to] = dis[id] + e[i].cost;

                pre[e[i].to] = id;

                if (!vst[e[i].to])

                {

                    vst[e[i].to] = 1;

                    que.push(e[i].to);

                    if (++num[e[i].to] > n) return e[i].to;

                }

            }

    }

    return -1;

}

int main()

{

    while(scanf("%d%d", &n, &m) != EOF)

    {

        for(int i = 0; i < n; i++)

            scanf("%d%d%d", &x[i][0], &x[i][1], &x[i][2]);

        for(int i = 0; i < m; i++)

            scanf("%d%d%d", &y[i][0], &y[i][1], &y[i][2]);

        memset(v, -1, sizeof(v)); cnt = 0; int s = n + m;

        for(int i = 0; i < n; i++)

            for(int j = 0; j < m; j++)

            {

                g[i][j] = abs(x[i][0] - y[j][0]) + abs(x[i][1] - y[j][1]) + 1;

                insert(i, n + j, g[i][j]);

            }

        memset(sum, 0, sizeof(sum));

        for(int i = 0; i < n; i++)

            for(int j = 0; j < m; j++)

            {

                int tmp; scanf("%d", &tmp); ans[i][j] = tmp;

                if (tmp != 0) insert(j + n, i, -g[i][j]);

                sum[j] += tmp;

            }

        for(int i = 0; i < m; i++)

        {

            if (sum[i] < y[i][2]) insert(i + n, s, 0);

            if (sum[i] > 0) insert(s, i + n, 0);

        }

        int id = spfa(s, s + 1);

        if (id == -1) printf("OPTIMAL\n");

        else

        {

            printf("SUBOPTIMAL\n");

            int sta = id; memset(vst, 0, sizeof(vst));

            while(true)//寻找负环起点

            {

                if (!vst[sta]){vst[sta] = true;sta = pre[sta];}

                else {id = sta; break;}

            }

            do

            {

                int from = pre[sta], to = sta;

                //cout << from << ' ' << to << endl;//负环的每条边

                if (from < n && to >= n && to < s) ans[from][to - n]++;

                if (to < n && from >= n && from < s) ans[to][from - n]--;

                sta = pre[sta];

            }while(sta != id);

            for(int i = 0; i < n; i++)

            {

                printf("%d", ans[i][0]);

                for(int j = 1; j < m; j++) printf(" %d", ans[i][j]);

                printf("\n");

            }

        }

    }

         return 0;

}