首页 > 代码库 > 2013 ACM-ICPC长沙赛区全国邀请赛——Travel in time

2013 ACM-ICPC长沙赛区全国邀请赛——Travel in time

2024-07-03 13:32:59   225人阅读

题目链接

  • 题意：
    给n个点，m条边的无向图，一个起点和一个终点。每边都有消耗，经过就要付出代价；每个点有消耗和价值，只有消耗了才会获得价值，如果不消耗就不会获得价值，且下一次消耗的点的价值一定要严格大于之前消耗过的点的价值
    求：起点到终点消耗不超过给定值T时的价值最大值
    1 < N < 100，0 < M < 1000，0 < T <= 300
  • 分析：
    对于不进行点的消耗的操作，就是求两点的最短路，floyd求

    表示一下状态：
    可以粗率表示为：当前所在点、总消耗值、总价值、最近消耗的点的价值。可以发现，总价值是可以贪心取max的，不妨设之为顶标；由于题目的限制，下一个消耗点的价值一定比上一个点大，所以最近消耗点的价值这个其实可以用提前排序来消除，即保证下一个使用的点的价值比上一个大即可。
    所以状态：当前所在点，总消耗值  
    顶标：总价值

    分析一下转移操作：
    对于所在点：直接转向下一个即可
    对于总消耗值：有两种处理，一种是不改变或者改变（即只是到达这个点），一种是必须改变（必须在下一个点消耗）。
    1.对于第一种方法：也就是说，a(消耗)->b(不消耗)->c(消耗)，可以分成a(消耗)->b(不消耗)、b(不消耗)->c(消耗)，可以发现，计算消耗时，距离的计算会出问题：a到b再到c的距离不小于a到c，所以这个方法不可行。
    2.第二种方法：这样的话就需要n*n的转移了，但是对于题目数据完全足够。细节比较多：对于起点和终点就需要单独处理，需要加一个超级源点和超级汇点，并且注意对这两个点的价值、花费、和其他点的距离的初始化；对于排序后价值相同的点需要特判
const int MAXN = 110;

int T, n, m, t, s, e, ee;
int cost[MAXN], val[MAXN], dis[MAXN][MAXN];
int pt[MAXN], dp[MAXN][310];

bool cmp(int a, int b)
{
    return val[a] < val[b];
}

int main()
{
    //    freopen("in.txt", "r", stdin);
    int a, b, c;
    RI(T);
    FE(kase, 1, T)
    {
        scanf("%d%d%d%d%d", &n, &m, &t, &s, &e); s++; e++;
        cost[0] = val[0] = cost[n + 1] = val[n + 1] = 0;
        FE(i, 0, n + 1)
        {
            FF(j, 0, 310)
                dp[i][j] = -INF;
            pt[i] = i;
        }
        FE(i, 1, n)
        {
            FE(j, 1, n)
                dis[i][j] = INF;
            dis[i][i] = 0;
        }
        dp[0][0] = 0;

        FE(i, 1, n) RI(cost[i]);
        FE(i, 1, n) RI(val[i]);
        REP(i, m)
        {
            RIII(a, b, c); a++; b++;
            dis[a][b] = min(dis[a][b], c);
            dis[b][a] = min(dis[b][a], c);
        }
        FE(k, 1, n) FE(i, 1, n) FE(j, 1, n)
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        FE(i, 1, n)
        {
            dis[0][i] = dis[s][i];
            dis[i][n + 1] = dis[i][e];
        }
        dis[0][n + 1] = dis[s][e];
        sort(pt + 1, pt + n + 1, cmp);
        FE(i, 0, n) FE(j, i + 1, n + 1)
        {
            int a = pt[i], b = pt[j];
            if (i > 0 && j <= n && val[a] == val[b]) continue;
            FE(k, 0, t)
            {
                if (k + dis[a][b] + cost[b] > t) break;
                int& next = dp[b][k + dis[a][b] + cost[b]];
                next = max(next, dp[a][k] + val[b]);
            }
        }
        int ans = 0;
        FE(i, 0, t)
        {
            ans = max(ans, dp[n + 1][i]);
        }
        printf("Case #%d:\n%d\n", kase, ans);
    }
    return 0;
}


联系
我们