POJ_2175.cpp

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=220;
const int inf=1e9;

int X[MAXN], Y[MAXN], B[MAXN];
int P[MAXN], Q[MAXN], C[MAXN];
int cost[MAXN][MAXN], cap[MAXN][MAXN];
int cnt[MAXN], dis[MAXN], pre[MAXN], que[MAXN];
bool vis[MAXN];
int N, M, S, T, NN;

int main() {
	scanf("%d%d", &N, &M);
	S=0; T=N+M+1; NN=T+1;
	for (int i=1; i<=N; i++) scanf("%d%d%d", X+i, Y+i, B+i);
	for (int i=1; i<=M; i++) scanf("%d%d%d", P+i, Q+i, C+i);
	memset(cost, 0, sizeof(cost));
	for (int i=1; i<=N; i++) cap[S][i]=B[i];
	for (int j=1; j<=M; j++) cap[j+N][T]=C[j];
	for (int i=1; i<=N; i++)
		for (int j=1; j<=M; j++) {
			cap[i][j+N]=inf;
			cost[i][j+N]=abs(X[i]-P[j])+abs(Y[i]-Q[j])+1;
			cost[j+N][i]=-cost[i][j+N];
		}
	for (int i=1; i<=N; i++)
		for (int j=1; j<=M; j++) {
			int e; scanf("%d", &e);
			cap[S][i]-=e; cap[i][S]+=e;
			cap[i][j+N]-=e; cap[j+N][i]+=e;
			cap[j+N][T]-=e; cap[T][j+N]+=e;
		}	
	memset(cnt, 0, sizeof(cnt));
	memset(dis, 0, sizeof(dis));
	memset(vis, 1, sizeof(vis));
	int head=0, tail=0;
	for (int i=0; i<NN; i++) que[tail++]=i;
	int found=-1;
	while (head!=tail && found==-1) {
		int u=que[head]; head++; if (head==MAXN) head=0;
		vis[u]=false;
		for (int v=0; v<NN; v++)
			if (cap[u][v] && dis[v]>dis[u]+cost[u][v]) {
				pre[v]=u; dis[v]=dis[u]+cost[u][v];
				if (!vis[v]) {
					cnt[v]++;
					if (cnt[v]>NN) {
						found=v;
						break;
					}
					vis[v]=true;
					que[tail]=v; tail++; if (tail==MAXN) tail=0;
				}
			}
	}
	if (found==-1) puts("OPTIMAL");
	else {
		puts("SUBOPTIMAL");
		memset(vis, 0, sizeof(vis));
		int u=found;
		do {
			vis[u]=true;
			u=pre[u];
		}while (!vis[u]);
		int v=u;
		do {
			cap[pre[v]][v]-=1;
			cap[v][pre[v]]+=1;
			v=pre[v];
		}while (v!=u);
		for (int i=1; i<=N; i++)
			for (int j=1; j<=M; j++)
				printf("%d%c", inf-cap[i][N+j], (j==M)?'\n':' ');
	}
	return 0;
}