| 题目名称 | 165. [USACO Mar07] 奶牛交通 |
|---|---|
| 输入输出 | cowtraffic.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-10-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：108， 提交：267， 通过率：40.45% | ||||
 面对疾风吧 疾风 疾风吧 |
100 | 0.000 s | 0.00 MiB | C++ |
 HeHe |
100 | 0.000 s | 0.00 MiB | C++ |
 LCWhiStLe |
100 | 0.000 s | 0.00 MiB | C++ |
 Fisher. |
100 | 0.002 s | 0.49 MiB | C++ |
 梦那边的美好ET |
100 | 0.002 s | 0.51 MiB | C++ |
|
HeHe |
100 | 0.003 s | 0.65 MiB | C++ |
 JSX |
100 | 0.003 s | 1.48 MiB | C++ |
 巭孬嫑夯昆 |
100 | 0.003 s | 1.55 MiB | C++ |
 Furyton |
100 | 0.003 s | 2.65 MiB | C++ |
 ☪Repentance soul |
100 | 0.004 s | 0.46 MiB | C++ |
| 本题关联比赛 | |||
| 假期找点事儿做题吧 | |||
| 关于 奶牛交通 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
C++这么慢吗？
| ||||
|
if(!out[E[i].to])S.push(E[i].to);写成了if(!out[E[i].to])S.push(out[E[i].to]);还有6个点可以a...
| ||||
|
第一个dfs不能用bfs代替。。
强行把两个dfs压成一个，很舒服 | ||||
|
回复 @派大大 :
继续论n m打翻的意义  Foenix
2014-10-26 15:39
3楼
| ||||
|
状态
* F[i] 为入度为0的点到i的路径条数 * G[i] 为i到N的路径条数 状态转移方程 * 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)  →震世逆空波→
2014-10-26 06:03
2楼
| ||||
|
用静表一直边点不分
| ||||
ZooxTark➲
CSU_Turkey
kZime
乌龙猹- 第一行:两个用空格隔开的整数:N,M.
- 第二行到第M+1行:每行两个用空格隔开的整数ai,bi,表示一条道路从ai到bi.
- 第一行: 一个整数,表示所有路径中通过某条道路的最大次数.
译: zqzas
【题目描述】
农场中,由于奶牛数量的迅速增长,通往奶牛宿舍的道路也出现了严重的交通拥堵问题.FJ打算找出最忙碌的道路来重点整治.
这个牧区包括一个由M (1 ≤ M ≤ 50,000)条单行道路(有向)组成的网络,以及 N (1 ≤ N ≤ 5,000)个交叉路口(编号为1..N),每一条道路连接两个不同的交叉路口.奶牛宿舍位于第N个路口.每一条道路都由编号较小的路口通向编号较大的路 口.这样就可以避免网络中出现环.显而易见,所有道路都通向奶牛宿舍.而两个交叉路口可能由不止一条边连接.
在准备睡觉的时候,所有奶牛都从他们各自所在的交叉路口走向奶牛宿舍,奶牛只会在入度为0的路口,且所有入度为0的路口都会有奶牛.
帮助FJ找出最忙碌的道路,即计算所有路径中通过某条道路的最大次数.答案保证可以用32位整数存储.
【输入格式】
【输出格式】
【输入样例】
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