本文主要是介绍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]牛交通 双向拓扑排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
