/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=2433
Name : 2433 Travel
Date : Wednesday, January 25, 2012
Time Stage : 4 hours
Result:
5292805 2012-01-25 14:24:31 Accepted 2433
656MS 324K 2494 B
C++ pyy
Test Data :
Review :
不说了,直接上大牛的解题报告:
http://isomer.me/2011/08/hdu-2433-%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%A2%84%E5%A4%84%E7%90%86/
http://hi.baidu.com/novosbirsk/blog/item/5c26bffbd04d4d6c034f56b7.html
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <CSTRING>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std ;
#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 102
struct EDGE {
int u, v ;
} ;
bool used[MAXN], bCnet, bInit ;
int n, m ;
int dist[MAXN], map[MAXN][MAXN], sum_d[MAXN], pre[MAXN][MAXN] ;
EDGE e[30*MAXN] ;
int bfs (int beg)
{
int i, t ;
queue<int> q ;
MEM (used, 0) ;
MEM (dist, 0) ;
used[beg] = 1 ;
// dist[beg] = 0 ;
q.push (beg) ;
while (!q.empty ())
{
t = q.front() ;
q.pop () ;
for (i = 1 ; i <= n ; ++i)
{
if (!used[i] && map[t][i])
{
used[i] = 1 ;
dist[i] = dist[t] + 1 ;
// 只有要第一次 bfs 计算各边的时候才用到
if (bInit)
pre[beg][i] = t ;
q.push (i) ;
}
}
}
int tmpSum = 0 ;
// 从 beg+1 开始 和从 1 开始,效果差不多
for (i = beg + 1 ; i <= n ; ++i)
{
if (!dist[i])
return INF ;
tmpSum += dist[i] ;
}
return tmpSum ;
}
int main ()
{
int i, j ;
int u, v, sum, res ;
while (scanf ("%d%d", &n, &m) != EOF)
{
MEM (map, 0) ;
MEM (pre, 0) ;
for (i = 1 ; i <= m ; ++i)
{
scanf ("%d%d", &u, &v) ;
e[i].u = u ;
e[i].v = v ;
map[u][v] = ++map[v][u] ;
}
sum = 0 ;
bCnet = true ;
bInit = true ;
for (i = 1 ; i <= n ; ++i)
{
sum_d[i] = bfs (i) ;
sum += sum_d[i] ;
// 优化……很显然效果不大
if (sum >= INF)
{
bCnet = false ;
break ;
}
}
bInit = false ;
for (i = 1 ; i <= m ; ++i)
{
u = e[i].u ;
v = e[i].v ;
// map[u][v] 判断有无重边,可以优化300多MS
if (bCnet && map[u][v] == 1)
{
res = 0 ;
for (j = 1 ; j <= n ; ++j)
{
// 最重要的剪枝,否则直接超时
if (pre[j][u] != v && pre[j][v] !=u)
res += sum_d[j] ;
else
{
--map[u][v] ;
--map[v][u] ;
res += bfs (j) ;
++map[u][v] ;
++map[v][u] ;
if (res >= INF)
break ;
}
}
}
else // 一开始漏了这句,一直无限WA,气死了,思维漏洞啊!
res = sum ;
if (res >= INF)
puts ("INF") ;
else
printf ("%d\n", res * 2) ;
}
}
return 0 ;
}
分享到:
相关推荐
ACM_DFS+BFS
动态内存+BFS #include #include #include #include using namespace std; void BFS(list<int> *the_a,int the_N,int the_S,int *the_b){ int *m=new int[the_N]; for(int k1=0;k1;k1++) m[k1]=0; m[the_S-1]=1; ...
DFS+BFS深度+广度优先遍历.cpp
标准C的图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现,纯手写!下载后如有疑问可以私信联系!全部手撸,一键运行,都封装成函数了,易读性很强
图的相关算法比较全面的总结,包括了图的深度和广度遍历算法,prim和kruskal两种最小生成树的算法,邻接矩阵和邻接表两种储存结构,做课程设计、实验报告或者数据结构学习者可以参考参考啊``源代码都是我亲手打的,...
用邻接矩阵来存储图,Floyed算法求任意两点间的最短路径并输出,广度优先遍历,深度优先遍历
This program uses a int type number to represent the Eight Puzzle Problem. number 1,2,3,…,8 stand for the eight numbers,0 stand for blank space. row from top to bottom,column from left to right. ...
1.包含了8个文档。 2.大部分为集训队文档。 3.部分算法详解文档。 4.文库搜索,全部下载需要十几分。
列表实现岛屿数量(DFS+BFS) ** 给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被...
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度...
本篇文章是对优先队列+BFS进行了详细的分析介绍,需要的朋友参考下
BFS++ 是西门子一个优秀的资产管理软件。主要应用于电厂等大型资产密集型企业。
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
降群法解魔方 哈哈师大 使用双向BFS搜素
题解:Bfs找最短路径(正解,绝对正确)这是c++中一道题的题解
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
this is code for bfs in c++
节点维护各自主链,有更新套用现成BFS广度搜索算法,预先遍历整个连通节点。最终结果导致空间溢出,只有80分,有点小遗憾。 下面展示一些 内联代码片。 #include using namespace std; const int maxn=501; ...
BFS++是以网络为支撑、数据库为核心,以设备的运行和维修管理为主要对象的一套综合性的电厂生产管理系统。它提供的主要功能包括:基本系统、设备数据、维修管理、运行管理、备件管理、文档管理等六个部分。