/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://poj.org/problem?id=2455
Name : 2455 Secret Milking Machine
Date : Sunday, February 12, 2012
Time Stage : 4 hours
Result:
9799773 panyanyany
2455
Accepted 1900K 282MS C++
3943B 2012-02-12 21:46:03
Test Data :
7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3
Review :
TLE 4个小时,原来是模板有问题,好多细节理解不到位啊!
//----------------------------------------------------------------------------*/
#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 (204)
#define DB /##/
struct EDGE {
int u, v, c, n ;
};
int n, p, t, eCnt ;
int level[MAXN], q[MAXN], vertex[MAXN] ;
EDGE net[MAXN*MAXN*10] ;
struct E {
int u, v, c ;
} ed[MAXN*MAXN*10] ;
inline void init()
{
// MEM (map, INF) ;
}
inline void insert (int u, int v, int c)
{
net[eCnt].u = u ;
net[eCnt].v = v ;
net[eCnt].c = c ;
net[eCnt].n = vertex[u] ;
vertex[u] = eCnt++ ;
net[eCnt].u = v ;
net[eCnt].v = u ;
net[eCnt].c = c ;
net[eCnt].n = vertex[v] ;
vertex[v] = eCnt++ ;
}
void makegraph (int lim)
{
int i ;
MEM(vertex, -1) ;
eCnt = 0 ;
for (i = 1 ; i <= p ; ++i)
if (ed[i].c <= lim)
insert (ed[i].u, ed[i].v, 1) ;
}
void out ()
{
int i, j ;
for (i = 1 ; i <= n ; ++i)
{
for (j = 1 ; j <= n ; ++j)
printf ("%d ", net[i].c) ;
puts ("") ;
}
}
int dinic (const int beg, const int end)
{
int sum, u, v, head, tail, i ;
int e ;
sum = 0 ;
while (true)
{
MEM (level, -1) ;
head = tail = 0 ;
q[tail++] = beg ;
level[beg] = 0 ;
while (head < tail)
{
u = q[head++] ;
for (e = vertex[u] ; e != -1 ; e = net[e].n)
{
v = net[e].v ;
if (net[e].c > 0 && -1 == level[v])
{
level[v] = level[u] + 1 ;
if (end == v)
{
head = tail ;
break ;
}
q[tail++] = v ;
}
}
}
if (-1 == level[end])
break ;
u = beg ;
tail = 0 ;
while (true)
{
if (end == u)
{
int flow = INF, qbreak ;
for (i = 0 ; i < tail ; ++i)
{
e = q[i] ;
// flow >= net[e].c 会消耗更多时间
if (flow > net[e].c)
{
flow = net[e].c ;
qbreak = i ;
}
}
sum += flow ;
for (i = 0 ; i < tail ; ++i)
{
e = q[i] ;
net[e].c -= flow ;
net[e^1].c += flow ;
}
// 这样写超时:
// e = q[qbreak] ;
// tail = qbreak + 1 ;
u = net[q[qbreak]].u ;
tail = qbreak ;
}
for (e = vertex[u] ; e != -1 ; e = net[e].n)
if (net[e].c > 0 && level[u]+1 == level[net[e].v])
break ;
if (-1 == e)
{
if (tail == 0)
break ;
level[net[q[--tail]].v] = -1 ;
u = net[q[tail]].u ;
}
else
{
u = net[e].v ;
q[tail++] = e ;
}
}
}
return sum ;
}
int main()
{
int i ;
int ans, tmpans, low, hig, mid ;
while (scanf ("%d%d%d", &n, &p, &t) != EOF)
{
init();
hig = 0 ;
low = 1000000 ;
for (i = 1 ; i <= p ; ++i)
{
scanf ("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].c) ;
low = min(ed[i].c, low) ;
hig = max(ed[i].c, hig) ;
}
while (low <= hig)
{
mid = (low + hig) / 2 ;
makegraph (mid) ;
if ((tmpans = dinic(1, n)) >= t)
{
ans = mid ;
hig = mid - 1 ;
}
else
low = mid + 1 ;
}
printf ("%d\n", ans) ;
}
return 0 ;
}
分享到:
相关推荐
最大流的Dinic算法,时间复杂度O(EV^2),代码简单而高效
最大流的Dinic算法与SAP算法的实现,分别包括递归与非递归版本,对稀疏图效果较好。
图论- 网络流- 最大流- Dinic 算法.rar
[Din70]Algorithm for solution of a problem of maximum flow in a network with power estimation.pdf 最大流最高标号法(DINIC法)的论文原文
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
用于计算最大网络流的经典的Dinic算法,代码自带例子,边权支持double类型。
用DINIC方法实现最大流算法,亲测可以运行!VS2008环境下编辑运行通过!
Dinic算法的基本思路: 1.根据残量网络计算层次图。 2.在层次图中使用DFS进行增广直到不存在增广路 3.重复以上步骤直到无法增广
网络流dinic模板,非本人原创。网络流dinic模板,非本人原创
网络流Dinic
在图论中的网络流部分,使用Dinic算法求解网络中的最大流。
最大流模板.cpp dinic
该模板应该是非递归dinic中代码最短、时间最优的了,适合十分绿色,别告诉我你不知道“最大流”是干什么的?
poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 isap 最快(ek会超时) poj2832 并查集边的计算 sgu218 hcraft 二分图匹配验证 二分答案
给师弟师妹们讲网络流Dinic算法与可行流用到的讲义,感觉还是不错,分享一下~
最大流的 Dinic 算法的 C++ 实现。 以下是操作摘要: FlowNetwork f(n, m) :具有 n 个顶点(0 到 n-1)和 m 个有向边的新网络, f.add(x, y, c) :添加从节点 x 到节点 y 的有向边,容量为 c, f.flow(s, t) :...
本文是dinic网络流算法的源程序,是一套模板,经过本人测试,适合参加ACM的同志!
北京大学2011年暑期acm培训课件 课程内容共八个专题,除理论知识外还包括精选例题讲解(先后次序可能调整): 1) 数据结构(一): 线段树,树状数组,二维线段树 2) 动态规划:状态压缩,树形动归,平行四边形法则 ...
Dinic多路增广pascal源码 poj 1273格式