【思维·tarjan·技巧-拓扑确定图中递推顺序】jzoj1238 自行车比赛 纪中集训提高B组

Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits

Description

自行车赛在一个很大的地方举行，有N个镇，用1到N编号，镇与镇之间有M条单行道相连，起点设在镇1，终点设在镇2。

问从起点到终点一共有多少种不同的路线。两条路线只要不使用完全相同的道路就被认为是不同的。

Input

一行两个整数：N和M(1<=N<=10000,1<=M<=100000)，表示镇的数量和道路的数量。

接下来M行，每行包含两个不同的整数A和B，表示有一条从镇A到镇B的单行道。

两个镇之间有可能不止一条路连接。

Output

输出不同路线的数量，如果答案超过9位，只需输出最后9位数字。如果有无穷多的路线，输出“inf”。

Sample Input

输入1：
6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4

输入2：
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3

输入3：
31 60
1 3
1 3
3 4
3 4
4 5
4 5
5 6
5 6
6 7
6 7
…
…
…
28 29
28 29
29 30
29 30
30 31
30 31
31 2
31 2

Sample Output

输出1：
3

输出2：
inf

输出3：
073741824

不全的样例：

31 60 
1 3 
1 3 
3 4 
3 4 
4 5 
4 5 
5 6 
5 6 
6 7 
6 7 
7 8
7 8
8 9
8 9
9 10
9 10
10 11
10 11
11 12
11 12
12 13
12 13
13 14
13 14
14 15
14 15
15 16
15 16
16 17
16 17
17 18
17 18
18 19
18 19
19 20
19 20
20 21
20 21
21 22
21 22
22 23
22 23
23 24
23 24
24 25
24 25
25 26
25 26
26 27
26 27
27 28
27 28
28 29 
28 29 
29 30 
29 30 
30 31 
30 31 
31 2 
31 2 

刚开始考试才读完题目的时候，本来打算放弃这道题来着，因为感觉会不好做，就只写了inf；后来考试时间太多了（没有别的意思啊喂），就尝试着去骗其他分。

大概有一个递推的思路吧：就是递推方案数，这个点的方案数就是他的儿子的方案数之和。我们要保证这个点的答案被他的儿子递推完全才能用他去更新别的点，也就是先算出这个点的入度，被递推一次就入度-- ，然后入度为0就进队去递推别的点。有环的情况特判一下，用-1标记，如果一个点存在一个儿子是-1的话，那么他自己也是-1。
考场代码如下：

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<cstdlib>
using namespace std;
#define N 10005
#define M 100005
#define ll long long
#define INF 0x3f3f3f3f
#define MOD 1000000000
int ind[N];
vector<int>G[N];
int n,m,cnt;
ll ans[N];
void lyt()
{queue<int>Q;while(!Q.empty()) Q.pop();for(int i=1;i<=n;i++)if(!ind[i]){Q.push(i);ans[i]=1;cnt++;}while(!Q.empty()){int u=Q.front();Q.pop();for(int i=0;i<G[u].size();i++){int v=G[u][i];if(ans[v]==-1) continue;if(ans[u]==-1) {ans[v]=-1;if(v==2){puts("inf");exit(0);}}else ans[v]=(ans[v]+ans[u])%MOD;ind[v]--;if(ind[v]==0){if(v==2){if(ans[v]!=-1)printf("%lld\n",ans[v]);else puts("inf");exit(0);}else {Q.push(v);cnt++;}}}}if(cnt<n){puts("inf");exit(0);}
}
int main()
{scanf("%d %d",&n,&m);for(int i=1;i<=m;i++){int u,v;scanf("%d %d",&u,&v);G[u].push_back(v);ind[v]++;}if(ind[1]>0){puts("inf");return 0;}lyt();//puts("inf");return 0;
}

其实我以为我只是骗分而已（骗了30分），评讲的时候没有认真听讲（雾==），只听到说要用什么拓扑排序，然后就去问老师，（听我口述自己算法之后）老师说我的方法就是正解的那个方法，他也不知道为什么挂掉。

经过面向数据编程之后发现： 因为我没有考虑到这2种情况：
1.存在一个环，不在1-2的路径上，我的程序会输出inf
2.如图：

（从数据里面搞下来的，这个图画了好久的说）

简化一下这种情况就是：

（嗯，那个环也可以理解为入度永远不会变成4的东西，或者不看括号里面的内容，我们直接看那个图里面的东西就好，嗯）

用我的递推方法推到3那里就会推不动，因为3的入度不可能为0，但是回想一下我们要求去递推别人的点的入度为0的初衷（保证这个点的答案被递推完全），我们就会发现：指向3的那些点都对答案不可能存在贡献，因为他们都不在1-2的路径上，我们是从1开始递推的，1到达不了的点对答案没有什么影响，所以我们根本就不需要从用那些点来推其他点的答案。（这个开始想的时候想到过，但是没想这么深入，只是觉得1反正也只会递推从1开始能到达的点的答案，就没有管这个问题）

综上，我们得到结论：不在1-2的路径上的点，没有递推的必要。

其实这两个问题都可以用一个方法解决，就是我们只在1-2的路径上的那些点做这个算法就可以了。
具体做法呢，其实可以只从1开始搜，然后搜到的点作为进行递推算法的对象，这样也是可以的；如果非要找到在1-2的路径上的那些点，也可以，从1开始搞一遍，从2开始搞一遍，都可以搜到的点就是在1-2的路径上的那些点。

对了，还有就是取最后9位，由于要保留前导零的缘故，不能直接取模1e9，要特殊处理一下。

大概就可以过了：