这道题看似是建图十分简单,实则用裸的最小费用最大流必然会超时,用zkw费用流也会超时。
所以必须看清题意,题目要求只要比当前方案好就行,没说要最好。
那么根据定理,一个费用流是最小费用流的充要条件是这个费用流的残量网络没有负费用圈。对于这个定理,如果不明白可以画一画。
那么对本题来讲,只需要消一次圈就可以找到一个比当前方案好的方案,当然前提是网络中有负圈得情况下。
此时只需沿着负费用圈把各边流量增加1(这条负费用圈上有逆边,逆边流量加1相当于其对应的正边流量减1),增流之后残量网络对应的方案肯定是一个更优方案
那么怎么根据已有的流量建立残留网络呢。
实际上就是一个逆向思考的过程。
所有的建筑物i和避难所j,连接ij,边权为正的距离。因为i,j之间容量肯定无穷
如果原方案i到j有人,连接ji,边权为负的距离。如果i到j有流量过去,那么j到i的容量就大于0,并且花费是负的,因为这是由最小费用最大流的建的边所决定的。
如果j避难所的人数大于0,连接汇点和j,边权0.
如果j避难所没有满,连接j和汇点,边权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++)
{
if(j == m - 1) printf("%d\n", ans[i][j]);
else printf("%d ", ans[i][j]);
}
}
return 0;
}
分享到:
相关推荐
poj2516代码最小费用最大流
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1704752
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
很经典的图论,网络流入门的题目,值得一看啊~~其中有简单的解析
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
NULL 博文链接:https://128kj.iteye.com/blog/1705139
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj openjudge 1111题最大正向匹配 提交ac
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 百练 题目分类 poj 百练 题目分类
北大POJ1159-Palindrome 解题报告+AC代码
POJ1083的代码,POJ1083的代码,POJ1083的代码