[dp+graph] CodeForces - 721C

[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代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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;
}