[USACO Mar07] 奶牛交通
农场中,由于奶牛数量的迅速增长,通往奶牛宿舍的道路也出现了严重的交通拥堵问题.FJ打算找出最忙碌的道路来重点整治.
这个牧区包括一个由M (1 ≤ M ≤ 50,000)条单行道路(有向)组成的网络,以及 N (1 ≤ N ≤ 5,000)个交叉路口(编号为1..N),每一条道路连接两个不同的交叉路口.奶牛宿舍位于第N个路口.每一条道路都由编号较小的路口通向编号较大的路 口.这样就可以避免网络中出现环.显而易见,所有道路都通向奶牛宿舍.而两个交叉路口可能由不止一条边连接.
在准备睡觉的时候,所有奶牛都从他们各自所在的交叉路口走向奶牛宿舍,奶牛只会在入度为0的路口,且所有入度为0的路口都会有奶牛.
帮助FJ找出最忙碌的道路,即计算所有路径中通过某条道路的最大次数.答案保证可以用32位整数存储.
输入格式:
- 第一行:两个用空格隔开的整数:N,M.
- 第二行到第M+1行:每行两个用空格隔开的整数ai,bi,表示一条道路从ai到bi.
输出格式:
- 第一行: 一个整数,表示所有路径中通过某条道路的最大次数.
样例输入:
7 7 1 3 3 4 3 5 4 6 2 3 5 6 6 7
样例输出
4
样例说明:
1 4
/
3 6 -- 7
/ /
2 5
通向奶牛宿舍的所有路径:
1 3 4 6 7
1 3 5 6 7
2 3 4 6 7
2 3 5 6 7
通过某一条路的次数就是通过某一条路两端点路径条数的乘积
f[i]代表从一个入度为0的点到f[i]的路径条数
g[i]代表从n到i点的路径条数
f[i]=Sum{ f[j] } 存在边(j,i)
g[i]=Sum{ g[j] } 存在边(i,j)
f[k]=1 k为入度为0的点
g[n]=1;
ans=Max{ f[a]*g[b] } 存在边(a,b)
1 #include <cctype> 2 #include <cstdio> 3 4 const int MAXN=5010; 5 6 int n,m; 7 8 int f[MAXN],g[MAXN]; 9 10 struct node { 11 int to; 12 int next; 13 node() {} 14 node(int to,int next):to(to),next(next) {} 15 }; 16 node e[MAXN*10],r[MAXN*10]; 17 18 int head[MAXN],Head[MAXN],tot; 19 20 inline void read(int&x) { 21 int f=1;register char c=getchar(); 22 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 23 for(;isdigit(c);x=x*10+c-48,c=getchar()); 24 x=x*f; 25 } 26 27 inline int max(int a,int b) {return a<b?b:a;} 28 29 inline void add(int x,int y) { 30 e[++tot]=node(y,head[x]); 31 head[x]=tot; 32 r[tot]=node(x,Head[y]); 33 Head[y]=tot; 34 } 35 36 int hh() { 37 freopen("cowtraffic.in","r",stdin); 38 freopen("cowtraffic.out","w",stdout); 39 read(n);read(m); 40 int x,y; 41 for(register int i=1;i<=m;++i) { 42 read(x);read(y); 43 add(x,y); 44 if(x>y) x^=y^=x^=y;//其实没必要 45 } 46 g[n]=1; 47 for(register int i=1;i<=n;++i) 48 if(!Head[i]) f[i]=1; 49 50 for(register int i=1;i<=n;++i) 51 for(register int j=head[i];j;j=e[j].next) 52 f[e[j].to]+=f[i]; 53 54 for(register int i=n;i>=1;--i) 55 for(register int j=Head[i];j;j=r[j].next) 56 g[r[j].to]+=g[i]; 57 58 int ans=-1; 59 for(register int i=1;i<=n;++i) 60 for(register int j=head[i];j;j=e[j].next) 61 ans=max(ans,f[i]*g[e[j].to]); 62 printf("%d ",ans); 63 return 0; 64 } 65 66 int sb=hh(); 67 int main(int argc,char**argv) {;}