HDU-3339-In Action

ACM模版

描述

題解

最短路+背包。第一次做将這兩種算法組合的題，好題。

要求最少油耗使得系統癱瘓，而癱瘓的要求是控制的能量超過一半，那麼前者很容易想到需要先求最短路，但是求過最短路後并不是每一個電廠都要占領，要保證占領的電廠的總能量超過一半并且耗油最少，這就是01背包的問題了~~~

代碼

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

/*
 *  單源最短路徑，Dijkstra算法，鄰接矩陣形式，複雜度為O(n^2)
 *  求出源beg到所有點的最短路徑，傳入圖的頂點數和鄰接矩陣cost[][]
 *  傳回各點的最短路徑lowcost[]，路徑pre[]，pre[i]記錄beg到i路徑上的父節點，pre[beg] = -1
 *  可更改路徑權類型，但是權值必須為非負，下标0~n-1
 */
const int MAXN = ;
const int INF = ; //  表示無窮
bool vis[MAXN];
int pre[MAXN];

void Dijkstra(int cost[][MAXN], int lowcost[], int n, int beg)
{
    for (int i = ; i < n; i++)
    {
        lowcost[i] = INF;
        vis[i] = false;
        pre[i] = -;
    }
    lowcost[beg] = ;
    for (int j = ; j < n; j++)
    {
        int k = -;
        int min = INF;
        for (int i = ; i < n; i++)
        {
            if (!vis[i] && lowcost[i] < min)
            {
                min = lowcost[i];
                k = i;
            }
        }
        if (k == -)
        {
            break;
        }
        vis[k] = true;
        for (int i = ; i < n; i++)
        {
            if (!vis[i] && lowcost[k] + cost[k][i] < lowcost[i])
            {
                lowcost[i] = lowcost[k] + cost[k][i];
                pre[i] = k;
            }
        }
    }
}

int cost[MAXN][MAXN];
int lowcost[MAXN];
int power[MAXN];
int dp[MAXN * MAXN];

int main()
{
    int T;
    scanf("%d", &T);

    int n, m;
    while (T--)
    {
        memset(cost, , sizeof(cost));

        scanf("%d%d", &n, &m);

        int st, ed, val;
        while (m--)
        {
            scanf("%d%d%d", &st, &ed, &val);
            if (val < cost[st][ed])
            {
                cost[st][ed] = cost[ed][st] = val;
            }
        }

        int sum = ;
        for (int i = ; i <= n; i++)
        {
            scanf("%d", &power[i]);
            sum += power[i];
        }

        Dijkstra(cost, lowcost, n + , );

        memset(dp, , sizeof(dp));
        dp[] = ;

        for (int i = ; i <= n; i++)
        {
            for (int j = sum; j >= power[i]; j--)
            {
                dp[j] = min(dp[j], dp[j - power[i]] + lowcost[i]);
            }
        }

        int mid = sum /  + ;  //  大于一半
        int res = INF;
        for (int i = mid; i <= sum; i++)
        {
            if (dp[i] < res)
            {
                res = dp[i];
            }
        }

        if (res == INF)
        {
            printf("impossible\n");
        }
        else
        {
            printf("%d\n", res);
        }
    }

    return ;
}
           

參考

《最短路》