int que[MAXN * MAXN];
int nt, n, m;
int ans[MAXN][MAXN], g[MAXN][MAXN], sum[MAXN];
void init()
{
e = 0;
memset(head, -1, sizeof(head));
memset(cnt, 0, sizeof(cnt));
memset(pre, -1, sizeof(pre));
}
void add(int u, int v, int w)
{
edge[e].v = v;
edge[e].w = w;
edge[e].next = head[u];
head[u] = e++;
}
int spfa(int src)
{
for(int i = 0; i <= n; i++) d[i] = INF, vis[i] = 0;
vis[src] = 1;
int h = 0, t = 0;
que[t++] = src;
d[src] = 0;
cnt[src]++;
while(h < t)
{
int u = que[h++];
vis[u] = 0;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
int w = edge[i].w;
if(d[u] + w < d[v])
{
d[v] = d[u] + w;
pre[v] = u;
if(!vis[v])
{
vis[v] = 1;
que[t++] = v;
if(++cnt[v] > n) return v;
}
}
}
}
return -1;
}
int main()
{
scanf("%d%d", &nt, &m);
init();
for(int i = 0; i < nt; i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].w);
n = nt + m;
for(int i = 0; i < nt; i++)
for(int j = 0; j < m; j++)
{
g[i][j] = abs(a[i].x - b[j].x) + abs(a[i].y - b[j].y) + 1;
add(i, j + nt, g[i][j]);
}
for(int i = 0; i < nt; i++)
for(int j = 0; j < m; j++)
{
scanf("%d", &ans[i][j]);
if(ans[i][j])
{
add(j + nt, i, -g[i][j]);
sum[j] += ans[i][j];
}
}
for(int i = 0; i < m; i++)
{
if(sum[i] < b[i].w) add(i + nt, nt + m, 0);
if(sum[i] > 0) add(nt + m, i + nt, 0);
}
int u = spfa(nt + m);
if(u == -1) printf("OPTIMAL\n");
else
{
printf("SUBOPTIMAL\n");
memset(vis, 0, sizeof(vis));
int v = u;
while(!vis[v])
{
vis[v] = 1;
v = pre[v];
}
u = v;
do
{
if(pre[v] < nt && v >= nt) ans[pre[v]][v - nt]++;
if(v < nt && pre[v] >= nt) ans[v][pre[v] - nt]--;
v = pre[v];
}while(v != u);
for(int i = 0; i < nt; i++)
for(int j = 0; j < m; j++)
{www.2cto.com
if(j == m - 1) printf("%d\n", ans[i][j]);
else printf("%d ", ans[i][j]);
}
}
return 0;
}
作者：sdj222555