IOI2011 热带花园

题目:

   植物学家 Somhed 带着几组学生去泰国最大的热带花园游玩。这个花园中有N个喷泉(编号为 0,1,⋯,N−1)和M条小路。每条小路连接一对不同的喷泉,两个喷泉间最多只有一条小路,小路是可以双向行走的。从任意一个喷泉出发至少有一条小路。每条小路的美丽程度决定了 Somhed 选择走该条小路的优先程度。每组学生可以从任何一个喷泉出发。在任何一个喷泉,Somhed 和他的学生们会选择最美丽的一条小路离开该喷泉,除非最美丽的这条小路是他们刚刚走过的,且还有其它小路可走。在这种情况下,他们会选择第二美丽的小路离开该喷泉。当然,如果没有第二美丽的小路可选,他们会选择刚刚走过的小路再走回去。注意,对于 Somhed 来说没有两条小路是同样美丽的。
   Somhed 的学生们对小路的美丽与否不感兴趣,他们喜欢在喷泉P旁边的豪华餐厅吃午饭。Somhed 知道他的学生在走过恰好K条小路后会感觉饥饿,当然,对于不同组的学生K可以不同。Somhed 想知道在下列条件下,对于每组学生有多少条不同的路径可选。
   每组可以从任意喷泉出发;
   但是接下来的路径必须按照上面描述的规则进行选择;
   每组必须在恰好走过K条小路后到达喷泉P 。
   注意:他们在最终到达喷泉P之前可能曾经到过喷泉P。

思路:

   每个点的后继状态只有两种,可以先考虑把所有点拆成两个(是否从最优路走来),这样每个点就都只有一个后继,那么这样就是一棵基环树了。
   根据基环树的性质,这个图中有且只有一个环,可以先找出环。如果终点不在环上,那么走步能到达它的点可以直接一遍dfs得到。
   如果终点在环上,这样走步就可以在环上绕圈。所以可以想到把每个点到终点的距离对环的大小取模,但是可能存在点到终点的距离大于,这时取模就出现了问题,也就是说取模只能能处理的情况。所以可以暴力处理所有的询问(显然)。处理这个可以dfs后一遍递推得到(见代码)。

代码:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
#define erep(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
template<class T> inline bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
const int MN=300005;
int nxt[MN],n;
void addEdge(int a,int b){
    int ta=a+(!~nxt[a])*n;
    int tb=b+(!~nxt[b])*n;
    if(!~nxt[a])
        nxt[a]=tb;
    else if(!~nxt[a+n])
        nxt[a+n]=tb;
    if(!~nxt[b])
        nxt[b]=ta;
    else if(!~nxt[b+n])
        nxt[b+n]=ta;
}
int qry[2005],q,ans[2005],dis[MN];
void dfs(int o,int p){ 
    if(~dis[o])return;
    if(nxt[o]==p)return (void)(dis[o]=1);
    dis[o]=-1e9;
    dfs(nxt[o],p);
    if(dis[nxt[o]]>0)
        dis[o]=dis[nxt[o]]+1;
}
int cnt[MN],cnt2[MN];
void calc(int p){
    memset(dis,-1,sizeof dis);
    memset(cnt,0,sizeof cnt);
    memset(cnt2,0,sizeof cnt2);
    rep(i,0,n-1)dfs(i,p);
    dfs(p,p);
    rep(i,0,n-1)
        if(dis[i]>0){
            cnt[dis[i]]++;
            if(dis[p]>0)cnt2[dis[i]%dis[p]]++;
        }
    if(dis[p]<0){
        rep(i,1,q)
            if(qry[i]<(n<<1))
                ans[i]+=cnt[qry[i]];
    }
    else {
        rep(i,dis[p],(n<<1)-1)
            cnt[i]+=cnt[i-dis[p]];
        rep(i,1,q){
            if(qry[i]<(n<<1))
                ans[i]+=cnt[qry[i]];
            else
                ans[i]+=cnt2[qry[i]%dis[p]];
        }
    }
}
int main(){
    int m,p;
    scanf("%d%d%d",&n,&m,&p);
    memset(nxt,-1,sizeof nxt);
    rep(i,1,m){
        int a,b;
        scanf("%d%d",&a,&b);
        addEdge(a,b);
    }
    rep(i,0,n-1)
        if(!~nxt[i+n])
            nxt[i+n]=nxt[i];
    scanf("%d",&q);
    rep(i,1,q)
        scanf("%d",qry+i);
    calc(p);calc(p+n);
    rep(i,1,q)
        printf("%d\n",ans[i]);
    return 0;
}