题解 P4645 【[COCI2006-2007 Contest#3] BICIKLI】

chen_zhe · 2018-06-04 17:33:54 · 题解

这个题目的难度中等。

首先要问路径是否有限，那么想到的是有没有环。但是如果是盲目找环是错误的，因为如果环是一个“死路”，那么这个环就没有意义了

例如下图，虽然有一个环，但是有了这个环和没有这个环，在路径上不会有任何根本区别

但是如果我们再在3 1连一条边，那么我们可以无限走这个环，造成无限路径。

为了判定我们的必经之路——或者说可以走这个点到达2的路径上有没有环，比较容易想到的是，正向走一下bfs，然后反向走一下bfs（反向连边），接着对所有点进行判定。如果两次都能走到的，就是说明从这个点可以从1走到2，反之不行，这个时候我们可以进行标记。同时我们也可以找到是否有一个环。

接下来的问题就方便了，我们从1开始，对所有进行标记的点进行一次拓扑排序。

（英语不好，不会很好表达见谅）

接着输出dp_2即可。原来的题目过于繁杂，并且也没有很好地解释什么时候要输出前导0，我干脆删了

代码如下，我的大常数要100ms+才可以过

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int n,m,ind[10050],ord[100050],p=1000000000,cnt=0;

long long ans[10050];

bool visit[10050],visit2[10050],f[10050];

int read()
{
    int x=0;char ch=getchar();
    while (!isdigit(ch)){ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x;
}

vector <int> g[10050],G[10050];

queue <int> q;

bool flag=0;

int main()
{
    n=read();m=read();
    for (int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        g[u].push_back(v);
        G[v].push_back(u);
    }
    q.push(1);
    visit[1]=1;
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if (visit[v]==0)
            {
                //cout << u << "->" << v << endl;
                visit[v]=1;
                q.push(v);
            }
        }
    }
    q.push(2);
    visit2[2]=1;
    //cout << "-------------" << endl;
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if (visit2[v]==0)
            {
                //cout << u << "->" << v << endl;
                visit2[v]=1;
                q.push(v);
            }
        }
    }
    for (int i=1;i<=n;i++)
    {
        //cout << i << " " << visit[i] << " " << visit2[i] << endl;
        if (visit[i] && visit2[i])
            visit[i]=1;
        else visit[i]=0;
        if (visit[i])
            cnt++;
    }
    for (int i=1;i<=n;i++)
    {
        if (visit[i])
        {
            for (int j=0;j<g[i].size();j++)
            {
                int v=g[i][j];
                if (visit[v])
                    ind[v]++;
            }
        }
    }
    ans[1]=1;
    q.push(1);
    int k=0;
    while (!q.empty())
    {
        int u=q.front();
        k++;
        q.pop();
        for (int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if (visit[v])
            {
                //cout << u << "->" << v << " " << ans[u] << " " << ans[v] << endl;
                ans[v]+=ans[u];
                ans[v]%=p;
                ind[v]--;
                if (ind[v]==0)
                    q.push(v);
            }
        }
    }
    if (k<cnt)
        puts("inf");
    else printf("%lld\n",ans[2]);
    return 0;
}