POJ 3272Cow Traffic /洛谷 P2883 [USACO07MAR]牛交通 双向拓扑排序

本文主要是介绍POJ 3272Cow Traffic /洛谷 P2883 [USACO07MAR]牛交通 双向拓扑排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

The bovine population boom down on the farm has caused seriouscongestion on the cow trails leading to the barn. Farmer John has decided toconduct a study to find the bottlenecks in order to relieve the 'traffic jams'at milking time.

The pasture contains a network of M (1 ≤ M ≤ 50,000) one-waytrails, each of which connects exactly two different intersections from the setof N (1 ≤ N ≤ 5,000) intersections conveniently numbered 1..N; the barn is atintersection number N. Each trail connects one intersection point to anotherintersection point with a higher number. As a result, there are no cycles and,as they say on the farm, all trails lead to the barn. A pair of intersectionpoints might be connected by more than one trail.

During milking time rush hour, the cows start from theirrespective grazing locations and head to the barn. The grazing locations areexactly those intersection points with no trails connecting into them. Each cowtraverses a 'path', which is defined as a sequence of trails from a grazinglocation to the barn.

Help FJ finding the busiest trail(s) by computing the largestnumber of possible paths that contain any one trail. The answer is guaranteedto fit in a signed 32-bit integer.

随着牛的数量增加,农场的道路的拥挤现象十分严重,特别是在每天晚上的挤奶时间。为了解决这个问题,FJ决定研究这个问题,以能找到导致拥堵现象的瓶颈所在。

牧场共有M条单向道路,每条道路连接着两个不同的交叉路口,为了方便研究,FJ将这些交叉路口编号为1..N,而牛圈位于交叉路口N。任意一条单向道路的方向一定是是从编号低的路口到编号高的路口,因此农场中不会有环型路径。同时,可能存在某两个交叉路口不止一条单向道路径连接的情况。

在挤奶时间到来的时候,奶牛们开始从各自的放牧地点回到牛圈。放牧地点是指那些没有道路连接进来的路口(入度为0的顶点)。

现在请你帮助fj通过计算从放牧点到达牛圈的路径数目来找到最繁忙的道路(答案保证是不超过32位整数)。

输入输出格式

输入格式:

Line 1: Two space-separated integers: N and M.

Lines 2..M+1: Two space-separated intersection points.

输出格式:

Line 1: The maximum number of paths passing through any onetrail.

输入输出样例

输入样例#1 复制

7 7
1 3
3 4
3 5
4 6
2 3
5 6
6 7

输出样例#1 复制

4

说明

Here are the four possible paths that lead to the barn:

1 3 4 6 7

1 3 5 6 7

2 3 4 6 7

2 3 5 6 7

算法分析:

题意:求从每个入度为零的点走到唯一的一个出度为零的点的所有走法中,经过次数最多的一条边被经过的次数,输入为点数和边数

分析:进行正反两次拓扑排序,标记出每个节点正向路径数和反向路径数,连接两点的正反向路径数,最大值即为答案

代码实现:

 

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list>  
using namespace std;  
const double eps = 1e-8;  
typedef long long LL;  
typedef unsigned long long ULL;  
const int INT_INF = 0x3f3f3f3f;  
const int INT_M_INF = 0x7f7f7f7f;  
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;  
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;  
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};  
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};  
const int MOD = 1e9 + 7;  
const double pi = acos(-1.0);  
const int MAXN = 1e5 + 10;  
const int MAXT = 10000 + 10;  
#define N 5005
int n,m;  
vector<int>g[N];//g[i]表示i节点所指向的其他节点 
vector<int>fg[N]; 
int in[N],d[N],fd[N];   //节点入读
int out[N];  
int topsort()  //正向拓扑排序
{  queue<int>q;for(int i=1;i<=n;i++)  if(in[i]==0){d[i]=1;q.push(i);}  while(!q.empty())  {  int u=q.front();  q.pop();  for(int i=0;i<g[u].size();i++)  {  int v=g[u][i];d[v]+=d[u];   //记录当前点的正向路径数 if(--in[v]==0)  q.push(v);  }  }  return 0; } 
int ftopsort()    //反向拓扑排序
{  queue<int>q;//保证小值先出队列(题目要求没办法)  fd[n]=1;q.push(n);while(!q.empty())  {  int u=q.front();  q.pop();  for(int i=0;i<fg[u].size();i++)  {  int v=fg[u][i]; fd[v]+=fd[u];  //记录当前点的正向路径数 if(--out[v]==0)  q.push(v);  }  }  return 0;
}  
int main()  
{  while(scanf("%d%d",&n,&m)!=EOF)  {  memset(in,0,sizeof(in));  memset(out,0,sizeof(out));memset(d,0,sizeof(d)); memset(fd,0,sizeof(fd));  for(int i=0;i<=n;i++) g[i].clear(); for(int i=0;i<=n;i++) fg[i].clear(); for(int i=0;i<m;i++)  {  int u,v;  scanf("%d%d",&u,&v);  g[min(u,v)].push_back(max(u,v)); //正向建图 fg[max(u,v)].push_back(min(u,v)); //反向建图in[max(u,v)]++;  //入度out[min(u,v)]++;  //出度}  topsort();ftopsort();int ans=0;for(int i=1;i<=n;i++)  for(int j=0;j<g[i].size();j++){//cout<<i<<d[i]<<" "<<g[i][j]<<fd[g[i][j]]<<endl;ans=max(ans,d[i]*fd[g[i][j]]);}printf("%d\n",ans);}  return 0;  
}  

这篇关于POJ 3272Cow Traffic /洛谷 P2883 [USACO07MAR]牛交通 双向拓扑排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/379912

相关文章

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig