DAG上的dp：Codeforces 721C Journey

题目描述

https://codeforces.com/problemset/problem/721/C

Irina来到了城市Berlatov。该城市中有n个景点，编号从1至n，其中一些景点被单向道路连接。图中没有环路。最初Irina站在景点1，她的旅行终点是景点n。Irina想要游玩尽可能多的景点，但是，Irina在这座城市中的停留时间是有限的，她不能在这里呆超过T时间。帮助Irina规划在不超过T时间内，她可以游玩多少个景点。保证在T时间内至少有一条路径可以从景点1到达景点n。

Input

第一行：n，m，T——景点数量，道路的数量，游玩时间限制(2 ≤ n ≤ 5000, 1 ≤ m ≤ 5000, 1 ≤ T ≤ 109)

下面m行，每行u，v，t从u到v有一条路，且该条道路需要花费t时间通过。保证道路不会形成回路。数据保证有解。

Output

第一行输出数字k(2 ≤ k ≤ n)——Irina最多可游玩的景点

第二行按游玩顺序输出k个不同的景点的编号

如果有多种方案，输出其中一种

Examples

input

4 3 13

1 2 5

2 3 7

2 4 8

output

1 2 4

input

6 6 7

1 2 2

1 3 3

3 6 3

2 4 2

4 6 2

6 5 1

output

1 2 4 6

input

5 5 6

1 3 3

3 5 3

1 2 2

2 4 3

4 5 2

output

1 3 5

题解

该题要求在时间限制内走尽量多的点，由此联想到01背包的模型，不难想到要在DAG上dp求解。

一般在DAG上的dp数组设置为d[i]（必要时可多加维数），d[i]既可以定义成从i出发，也可以定义成以i结束，视题目类型而定。

本题中，我们定义d[i][j]表示以i为终点，从1经过j个点到达i点的路径长度，其中j是游玩景点的数量。

既然该图是有向无环图，意味着可以做一遍拓扑排序使经过的每个点只能往编号更大的点走，而不往编号更小的点走，这就可以让dp无后效性。

因此，我们只需要从1开始，做一遍拓扑排序，在排序的过程中不断地用当前的点u更新u指向的下一个点v的路径值，到u时经过了j-1个点的最短路径+u，v连边的边权小于d[v][j]时，就更新d[v][j]，转移方程如下：

变量定义

in[i]:第i个点的入度

dp[i][j]:以i为终点，从1经过j个点到达

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=5010;
const int INF=0x3f3f3f3f;
int n,m,T;

struct node{
    int to,next,cost;
}e[maxn];

int dp[maxn][maxn];
int head[maxn],pos;
int pre[maxn][maxn];
int st[maxn],top;
int in[maxn];

void add(int x,int y,int z)
{
    e[++pos].next=head[x];
    e[pos].to=y;
    e[pos].cost=z;
    head[x]=pos;
}

queue<int> q;

void solve()
{
    for(int i=1;i<=n;i++) if(in[i]==0) q.push(i);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            in[v]--;
            if(in[v]==0) q.push(v);
            for(int j=2;j<=n;j++)
            {
                if(dp[v][j]>(ll)dp[u][j-1]+e[i].cost)
                {
                    dp[v][j]=dp[u][j-1]+e[i].cost;
                    pre[v][j]=u;
                }
            }
        }
    }
}

void show(int i,int j)
{
    if(pre[i][j]==-1)
    {
        printf("1 ");
        return;
    }
    show(pre[i][j],j-1);
    printf("%d ",i);
}

int main()
{
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=m;i++)
    {
        int u,v,t;
        scanf("%d%d%d",&u,&v,&t);
        add(u,v,t);
        in[v]++;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=INF;
    dp[1][1]=0;
    pre[1][1]=-1;
    solve();
    for(int i=n;i>=1;i--)
        if(dp[n][i]<=T)
        {
            printf("%d\n",i);
            show(n,i);
            break;
        }
    return 0;
}

景点

【图论】DAG上的dp：Codeforces 721C Journey

DAG上的dp：Codeforces 721C Journey

题目描述

题解

变量定义

代码