/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://poj.org/problem?id=2112
Name : 2112 Optimal Milking
Date : Friday, February 10, 2012
Time Stage : 4 hours
Result: 9791440 panyanyany
2112
Accepted 592K 172MS C++
4274B 2012-02-10 15:28:44
Test Data :
2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0
1 1 1
0 1
1 0
2 2 1
0 0 1 3
0 0 2 100
1 2 0 0
3 100 0 0
Review :
犯了一些概念性的错误,太失败了……
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF (0x3f3f3f3f)
#define MAXN (234)
#define DB /##/
int K, C, M, n, low, hig ;
int map[MAXN][MAXN], net[MAXN][MAXN], level[MAXN], q[MAXN] ;
void floyd()
{
int i, j, k ;
for (k = 1 ; k <= n ; ++k)
for (i = 1 ; i <= n ; ++i)
for (j = i+1 ; j <= n ; ++j)
{
map[j][i] = map[i][j] = min(map[i][j], map[i][k]+map[k][j]) ;
}
}
int dinic (const int beg, const int end)
{
int sum, i, u, v, head, tail ;
sum = 0 ;
while (true)
{
head = tail = 0 ;
q[tail++] = beg ;
MEM (level, -1) ;
level[beg] = 0 ;
while (head < tail)
{
u = q[head++] ;
for (i = beg ; i <= end ; ++i)
if (net[u][i] > 0 && level[i] == -1)
{
level[i] = level[u] + 1 ;
if (end == i)
{
head = tail ;
break ;
}
q[tail++] = i ;
}
}
if (-1 == level[end])
break ;
tail = 0 ;
q[tail++] = beg ;
u = beg ;
while (1)
{
if (end == u)
{
int flow = INF, qbreak ;
for (i = 1 ; i < tail ; ++i)
{
u = q[i-1] ;
v = q[i] ;
if (flow >= net[u][v])
{
flow = net[u][v] ;
qbreak = i - 1 ;
}
}
sum += flow ;
for (i = 1 ; i < tail ; ++i)
{
u = q[i-1] ;
v = q[i] ;
net[u][v] -= flow ;
net[v][u] += flow ;
}
u = q[qbreak] ;
tail = qbreak + 1 ;
}
for (i = beg ; i <= end ; ++i)
if (net[u][i] > 0 && level[u]+1 == level[i])
break ;
if (i > end)
{
if (tail-1 == 0)
break ;
level[q[--tail]] = -1 ;
u =q[tail-1] ;
}
else
{
q[tail++] = i ;
u = i ;
}
}
}
return sum ;
}
void makegraph(const int lim)
{
int i, j ;
MEM(net, 0) ;
for (i = 1 ; i <= K ; ++i)
// 错误代码:for (j = 1 ; j <= n ; ++j)
// 错误代码: for (j = i+1 ; j <= n ; ++j)
// 首先,流向必须是单向的,map[u][v] 若有流量,则map[v][u]的流量须为0
// 其次,必须是由挤奶机流向奶牛,或者从奶牛流向挤奶机。
for (j = K+1 ; j <= n ; ++j)
net[i][j] = (map[i][j] <= lim) ;//? INF : 0 ;
// 源点到所有挤奶机的流量为 M
for (i = 1 ; i <= K ; ++i)
net[0][i] = M ;
// 所有奶牛到汇点的流量为 1
for (i = K+1 ; i <= n ; ++i)
net[i][n+1] = 1 ;
}
int main()
{
int i, j ;
int ans, tmpans ;
while (scanf ("%d%d%d", &K, &C, &M) != EOF)
{
MEM (net, 0) ;
MEM (map, 0) ;
n = K+C ;
for (i = 1 ; i <= n ; ++i)
for (j = 1 ; j <= n ; ++j)
{
scanf("%d", &map[i][j]) ;
if (0 == map[i][j])
map[i][j] = INF ;
}
// 求任意两点间最短路,为二分高度做准备
floyd() ;
for (i = 1 ; i <= K ; ++i)
net[0][i] = M ;
for (i = K+1 ; i <= n ; ++i)
net[i][n+1] = 1 ;
ans = INF ; // 保险起见,先初始化一下
int mid ;
// 本来是在 floyd 里面对每条路径进行比较的,然后可以缩小[low,hig]的区间
// 但是这样代码量大了,比较不容易维护,所以在后来查错的时间就挪出来,
// 直接赋值了
low = 0 ;
hig = INF ;
while (low <= hig)
{
mid = (low + hig) / 2 ;
// 每次限定改变了,就要重新制一次图
// 本来是可以在 dinic 里面增加一些代码,在制层次图和增广路的时候对
// 路径检查距离,从而限定它们的距离的。比如:
// if (map[u][i] <= mid && net[u][i] > 0 && level[i] == -1)
// 但是这样一来,相当于给本来完好的代码埋下了未知的地雷。
// 如果哪里漏了对 map[u][i]<=mid 的判断的话,就很难查错了
makegraph(mid) ;
tmpans = dinic (0, n+1) ;
if (tmpans == C)
{
ans = mid ; // 一开始会习惯性地写成 ans = tmpans 。
hig = mid - 1 ;
}
else
low = mid + 1 ;
}
printf ("%d\n", ans) ;
}
return 0 ;
}
分享到:
相关推荐
floyd算法matlab 利用 MATLAB 实现 Floyd 算法,可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵,且能查询任意两点间的最短距离和路由。 Floyd 算法适用于求解网络中的任意两点间的最短路径:...
本系统采用Dev C++开发平台来进行编写和测试,用到了类、数组、函数,指针、文件的读取存储操作以及DFS算法和所有顶点对的最短路径(Floyd算法)、 图的各种遍历算法等 用无向网表示XX大学的校园景点平面图,图中顶点...
北大POJ2240-Arbitrage【Floyd】 解题报告+AC代码
北大POJ2253-Frogger【Floyd】 解题报告+AC代码
【资源说明】 该项目代码主要针对计算机、自动化等相关专业的学生从业者下载使用,项目代码都经过严格调试,确保可以运行!放心下载使用。 也可作为期末课程设计、课程大作业、毕业设计等。具有较高的学习借鉴价值!...
北大POJ1125-Stockbroker Grapevine【Floyd】 解题报告+AC代码
代码直接就能用,比较简单的算法实现
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法.... (4)递推.... (5)构造法.(poj3295) ... (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
SPFA import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class SPFA { static SE[] e = new SE[9999];... static int[] dis = new int[9999];...
网络的最小费用最大流,弧旁的数字是容量(运费)。 一.Ford和Fulkerson迭加算法. 基本思路:把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路...
最大流最小花费算法 运用floyd和ford yunyo
中国数学建模-数学工具-Floyd最短路算法的MATLAB程序 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> Matlab,Mathematica,maple,几何画板,word,sas,spss......
利用误差扩散算法中的Floyd-Steinberg抖动算法来对图像进行二值化处理,从而方便图像调频加网输出Floyd-Steinberg
floyd算法+matlab计算,对数学建模爱好者有很大的好处~~~~
基于MATLAB的Floyd算法,计算网络中任意结点间的最小距离!
floyd算法的C++代码,用的时候只要改几个参数就可以了
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
Floyd算法 详细介绍了Floyd算法的应用