[dp+graph] CodeForces - 721C

题意

给定一个有向无环图DAG，之后问从点$1$走到点$n$中，在一定的费用要求下，最多能经过多少个点。并给出经过的点。

题解

$n \leq 5000$

我们可以考虑一下二维dp，定义一个dp数组

• $dp[i][j]$代表着在$i$这个点到终点，经过$j$个点所需要花费的最少时间。

之后利用dfs进行更新。因为是深度优先，所以经过的点不用在遍历一遍。

对于记录经过的点，可以用一个二维数组代表，第$j$个点的时候下一个点是什么。

---

错误的思想。 WA14

定义两个数组，一个记录已知这个点到达$n$最少耗-费的时间，一个记录已知这个点到达$n$最多的点数。之后利用这两个数组进行剪枝，但是已知wa14的点，我也不知道为什么。可能是dfs的顺序有关。

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e3+10;
int n,m,T,cnt;
int head[maxn],vis[maxn];
struct node{
    int to,next;
    ll val;
}G[maxn];
void init(){
    memset(head,-1,sizeof(head));
    cnt = 1;
}
void addedge(int u,int v,int val){
    G[cnt].to = v;
    G[cnt].val = val;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
int dp[maxn][maxn], bef[maxn][maxn];
void dfs(int u){   
    vis[u] = 1;
    if(u==n) return;
    for(int i=head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(vis[v]==0) dfs(v);
        rep(j,1,n){
            if(dp[v][j] + G[i].val < dp[u][j+1]){
                dp[u][j+1] = dp[v][j] + G[i].val;
                bef[u][j+1] = v;
            }
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&T);
    init();
    memset(dp,0x3f,sizeof(dp));
    rep(i,1,m+1){
        int u,v,val; scanf("%d%d%d",&u,&v,&val);
        addedge(u,v,val);
    }
    dp[n][1] = 0;
    dfs(1);
    int idx = 1;
    per(i,1,n+1){
        if(dp[1][i] <= T){
            printf("%d\n",i);
            idx = i;
            break;
        }
    }
    printf("1 ");
    int cnt = 1;
    while(idx > 1){
        printf("%d ",bef[cnt][idx]);
        cnt = bef[cnt][idx--];
    }
    return 0;
}