2015年2月18日 星期三

[TIOJ 1557] 馬可波羅的奇想曲

作法:

一般的DP,但要注意題目沒有保證他是個DAG,只有保證起點到終點的路上不會出現還,所以要在DFS時特別處理還的情形。

code :

#include<bits/stdc++.h>
#define MOD 1073741824
using namespace std;
const int maxn=10000+10 ;
vector<int> v[maxn] ;
bool vis[maxn] ;
int d[maxn] ;
 
int dp(int x)
{
    if(d[x]!=-1) return d[x] ;
    vis[x]=1 ;
    int &ans=d[x] ; ans=0 ;
    for(auto i : v[x])
    {
        if(vis[i]) return ans=0 ;
        ans=(ans+dp(i))%MOD ;
    }
    vis[x]=0 ;
    return ans ;
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
    }
    int st,ed ; scanf("%d%d",&st,&ed) ;
    memset(d,-1,sizeof(d)) ;
    d[ed]=1 ;
    printf("%d\n",dp(st)) ;
}
 

2 則留言:

  1. 請問如果測資是:
    9 11
    1 2
    2 3
    3 4
    4 5
    5 6
    6 7
    3 10
    10 9
    9 8
    8 2
    8 7
    1 7
    時,是不是會出錯?

    回覆刪除
    回覆
    1. Hi
      這樣起點到終點的路上就會有環了 (3 -> 10 -> 9 -> 8 -> 2 -> 3),不符合題目條件

      刪除