POJ 2175 最小费用最大流之消圈 根据已有流量建立残留网络
这道题看似是建图十分简单，实则用裸的最小费用最大流必然会超时，用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;
}
作者：sdj222555
