這道題看似是建圖十分簡單，實則用裸的最小費用最大流必然會超時，用zkw費用流也會超時。
所以必須看清題意，題目要求只要比當前方案好就行，沒說要最好。
那麼根據定理，一個費用流是最小費用流的充要條件是這個費用流的殘量網絡沒有負費用圈。對於這個定理，如果不明白可以畫一畫。
那麼對本題來講，只需要消一次圈就可以找到一個比當前方案好的方案，當然前提是網絡中有負圈得情況下。
此時只需沿著負費用圈把各邊流量增加1（這條負費用圈上有逆邊，逆邊流量加1相當於其對應的正邊流量減1），增流之後殘量網絡對應的方案肯定是一個更優方案
那麼怎麼根據已有的流量建立殘留網絡呢。
實際上就是一個逆向思考的過程。
所有的建築物i和避難所j，連接ij，邊權為正的距離。因為i,j之間容量肯定無窮
如果原方案i到j有人，連接ji，邊權為負的距離。如果i到j有流量過去，那麼j到i的容量就大於0，並且花費是負的，因為這是由最小費用最大流的建的邊所決定的。
如果j避難所的人數大於0，連接匯點和j，邊權0.
如果j避難所沒有滿，連接j和匯點，邊權0.
[cpp]
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct P
{
int x, y, w;
}a[MAXN], b[MAXN];
struct EDGE
{
int v, w, next;
}edge[MAXM];
int head[MAXN], e;
int d[MAXN], vis[MAXN], pre[MAXN], cnt[MAXN];
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);
for(int i = 0; i < m; i++) scanf("%d%d%d", &b[i].x, &b[i].y, &b[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++)
{
if(j == m - 1) printf("%d\n", ans[i][j]);
else printf("%d ", ans[i][j]);
}
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct P
{
int x, y, w;
}a[MAXN], b[MAXN];
struct EDGE
{
int v, w, next;
}edge[MAXM];
int head[MAXN], e;
int d[MAXN], vis[MAXN], pre[MAXN], cnt[MAXN];
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);
for(int i = 0; i < m; i++) scanf("%d%d%d", &b[i].x, &b[i].y, &b[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;
}
