本文共 6697 字，大约阅读时间需要 22 分钟。

DAG上DP

先对图进行预处理，再进行DP。一般都有两种套路，拓扑序或如Dijkstra或SPFA的最短路算法。

拓扑序

题意：一个有向图中，1->2之间有多少条不同路径。（有可能是0或inf）

思路：在1->2的任意路径上有环即为inf。但是环若是在死路上就没影响。所以先在正向图从1开始DFS所有点，并标记1。在反向图从2开始DFS所有点，并标记为2。最后，被1和2都标记过的点即为路径上的点。其他点不参与后面运算。

后面直接按拓扑序DP即可，若最后2的入度不为0，说明路径上有环，inf。否则输出dp[2].

#include
   
    #define endl '\n'#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);using namespace std;const int N = 1e5 +5, mod = 1e9;const double eps = 1e-10;using LL = long long;int n, m;vector
    
      G[N], NG[N];int vis[N], nvis[N], f[N], in[N];void dfs(vector
     
       Path[], int flag[], int u){
       flag[u] = 1;    for(int v : Path[u]){
           if(!flag[v]){
               dfs(Path, flag, v);        }    }}void topoSort(){
       for(int i = 1; i <= n; ++i){
           if(!vis[i])continue;        for(int u : G[i]){
               if(!vis[u])continue;            ++in[u];        }    }    queue
      
        Q;    for(int i = 1; i <= n; ++i){
           nvis[i] = 0;        if(vis[i] && !in[i]) Q.push(i);    }    f[1] = 1;    while(!Q.empty()){
           int u = Q.front();        Q.pop();        if(u == 2)return;        for(int v : G[u]){
               if(!vis[v])continue;            f[v] = (f[v] + f[u]) % mod;            if(--in[v] == 0)Q.push(v);        }    }    cout << "inf" << endl;    exit(0);}int main(){
       IOS;    cin >> n >> m;    for(int x, y, i = 1; i <=  m; ++i){
           cin >> x >> y;        G[x].push_back(y);        NG[y].push_back(x);    }    dfs(G, vis, 1);    dfs(NG, nvis, 2);    for(int i = 1; i <= n; ++i){
           //cout << i << ": " << vis[i] << " " << nvis[i] << endl;        vis[i] = vis[i] + nvis[i] == 2 ? 1 : 0;    }    if(!vis[2]){
           cout << 0 << endl;        exit(0);    }    topoSort();    cout << f[2] << endl;}
      
     
    
   

SPFA

普通图上DP

普通的图上面DP，由于有环的存在，一部分DP具有后效性，故需要用最短路算法（Dijkstra或SPFA）来解决。另一部分DP，则有可能是图上DFS，记忆化搜索。

SPFA

题意：求1->2->1的路径，使得路过的点最少。如下图，路过6个点。 思路：定义$f[i][j]$为$1\to i\to j\to 1$的最少经过点数。$d[i][j]$为$i$和$j$之间的最短路。则$f[a][b]$即$1\to a\to b\to 1$可以通过$1\to x\to y\to a\to b\to x\to y\to 1$更新，即$f[a][b]=f[x][y]+d[y][a]+d[a][b]+d[b][x]-1$。这样就可囊括以下几种情况。

• $1->2$和$2->1$上都包含$x\to y$。如上图中的$3\to 4$
• $1->2$包含$x\to y$，$2->1$上包含$y\to x$，如下图。
  $1\to 2\to 2\to 1$通过$1\to y\to y\to 2\to 2\to y\to y\to 1$更新，即通过$1\to y\to y\to 1$得到。
  而$1\to y\to y\to 1$同理，通过$1\to x\to x\to y\to y\to x\to x\to 1$更新，即通过$1\to x\to x\to 1$得到。

做法：通过Floyd得到$d[i][j]$。初始化$f[1][1]=1$，由于DP的后效性，使用SPFA进行DP，每次DP都更新$f[1\cdots n][1\cdots n]$所有的点（不包括f[x][y]），直到所有f都无法更新。最后答案就是$f[2][2]$

#include
   
    #define endl '\n'#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);using namespace std;const int N = 1e3 +5, mod = 1e9;int n, m;vector
    
      G[N];int d[N][N], f[N][N], in[N][N];struct Node{
       int x, y;    Node(int x = 0, int y = 0):x(x), y(y) {
   }};int main(){
       IOS;    int n, m;    cin >> n >> m;    memset(d, 0x0f, sizeof(d));    for(int x, y, i = 1; i <= m; ++i){
           cin >> x >> y;        G[x].push_back(y);        d[x][y] = 1;    }    for(int i = 1; i <= n; ++i)        d[i][i] = 0;    for(int k = 1; k <= n; ++k)        for(int i = 1; i <= n; ++i)            for(int j = 1; j <= n; ++j)                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);    memset(f, 0x7f, sizeof(f));    queue
     
       pq;    f[1][1] = 1;    pq.emplace(1, 1);    in[1][1] = 1;    while(!pq.empty()){
           int x = pq.front().x, y = pq.front().y;        in[x][y] = 0;        pq.pop();        for(int a = 1; a <= n; ++a){
               for(int b = 1; b <= n; ++b){
                   if(a==x && b==y)continue;                if(f[a][b] > f[x][y] + d[y][a] + d[a][b] + d[b][x] - 1){
                       f[a][b] = f[x][y] + d[y][a] + d[a][b] + d[b][x] - 1;                    if(in[a][b])continue;                    in[a][b] = 1;                    pq.emplace(a, b);                }            }        }    }    cout << f[2][2] << endl;}
     
    
   

记忆化搜索

题意：设1->n之间的最短路为d，求1->n之间长度不超过d+k的不同路径数量。（有边权为0的边） 思路：形式明显是$f[v][w]$，其中v是点，w是超出d的长度。但具体意义比较难。代表从$1$到$v$的距离为$dis[v]+w$的路径数。求解过程就是在反向图上记忆化搜索。 $$f[u][ex]=\sum _{v\to u}f[v][dis[u]+ex-dis[v]-C_{v\to u}]$$ 特别的，有可能有零环，即DFS到$u,ex$时，访问到了DFS树上的祖先节点，故当进入DFS时，标记$f[u][ex]=-2$，若最后访问到了-2节点则证明有零环。

#include
   
    #define endl '\n'#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);using namespace std;typedef long long LL;const int N = 1e5 +5, mod = 1e9;vector
    
     
       > G[N], NG[N];LL dis[N], f[N][55];int in[N];LL n, m, k, p, flag;void spfa(int s, int t){
       memset(dis, 0x0f, sizeof(dis));    dis[s] = 0;    queue
      
        Q;    Q.push(s);    while(!Q.empty()){
           int u = Q.front();        in[u] = 0;        Q.pop();        for(auto it : G[u]){
               int c = it.second, v = it.first;            if(dis[u] + c < dis[v]){
                   dis[v] = dis[u] + c;                if(in[v])continue;                in[v] = 1;                Q.emplace(v);            }        }    }}int dfs(int u, int ex){
       if(~f[u][ex])return f[u][ex];    f[u][ex] = -2;    LL ans = u == 1 && ex == 0;    for(auto it : NG[u]){
           int c = it.second, v = it.first;        if(dis[u] + ex - dis[v] - c < 0)continue;        if(f[v][dis[u] + ex - dis[v] - c] == -2){
               flag = 0;            return 0;        }        ans += dfs(v, dis[u] + ex - dis[v] - c);        ans %= p;    }    return f[u][ex] = ans;}int main(){
       IOS;    int T;    cin >> T;    while(T--){
           cin >> n >> m >> k >> p;        for(int i = 1; i <= n; ++i){
               G[i].clear();            NG[i].clear();        }        for(int i = 1, x, y, z; i <= m; ++i){
               cin >> x >> y >> z;            G[x].emplace_back(y, z);            NG[y].emplace_back(x, z);        }        spfa(1, n);        LL ans = 0;        memset(f, -1, sizeof(f));        flag = 1;        for(int i = 0; i <= k && flag; ++i){
               ans += dfs(n, i);            ans %= p;        }        cout << (flag ? ans : -1) << endl;    }}
      
     
    
   

转载地址：http://cwuzi.baihongyu.com/