2014-07-06

UVa 1093 - Castles

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

Wars have played a significant role in world history. Unlike modern wars, armies in the middle ages were principally concerned with capturing and holding castles, the private fortified residences of lords and nobles. The size of the attacking army was an important factor in an army’s ability to capture and hold one of these architectural masterpieces.

\epsfbox{p4788.eps}

A certain minimum number of soldiers were required to capture a castle. Some soldiers were expected to die during the attack. After capturing the castle, some soldiers were required to remain in the castle to defend it against attacks from another enemy. Of course, those numbers were different for different castles. Commanders of the armies were obliged to consider the number of soldiers required for victory. For example, there are five castles in the region map shown in Figure 2. The castle at the lower right requires at least 20 soldiers to wage a winning attack. None are expected to perish during the attack, and 10 soldiers must be left in the castle when the army moves on.

In this problem you must determine the minimum size of an army needed to capture and hold all the castles in a particular region. For reasons of security, there is exactly one (bi-directional) route between any pair of castles in the region. Moving into the neighborhood of an uncaptured castle begins an attack on that castle. Any castle can serve as the first castle to be attacked, without regard for how the army got there. Once any castle has been captured, the requisite number of soldiers is left in the castle to defend it, and the remainder of the army moves on to do battle at another castle, if any remain uncaptured. The army may safely pass through the neighborhood of a castle that it has already captured. But because of the potential for attacks, the army may traverse the route between a pair of castles no more than twice (that is, at most once in each direction).

Input

The input contains multiple test cases corresponding to different regions. The description of the castles in each region occupies several lines. The first line contains an integer n$\le$100 that is the number of castles in the region. Each of the next n lines contains three integers a, m, and g (1$\le$a$\le$1000, 0$\le$m$\le$a, 1$\le$g$\le$1000), that give the minimum number of soldiers required to successfully attack and capture a particular castle, the number of soldiers that are expected to die during the attack, and the number of soldiers that must be left at the castle to defend it. The castles are numbered 1 to n, and the input lines describing them are given in increasing order of castle numbers. Each of the remaining n - 1 lines in a test case has two integers that specify the castle numbers of a pair of castles that are connected by a direct route.

A line containing 0 follows the description of the last region.

Output

For each test case, display the case number and the minimum number of soldiers in the army needed to conquer all the castles in the region. Follow the format shown in the sample output.

Sample Input

Sample Output

1 2	Case 1: 22 Case 2: 65

Solution

題目描述：

攻略一個城堡會有幾個需求，第一，戰爭時最少的士兵數，第二，在這場戰爭中犧牲的士兵，第三，離開此城堡時，必須留下多少士兵駐守。

題目特別說明到，要用最少數量的士兵佔領所有的城堡，而每一座城堡之間都有路徑，必且佔領過程中每一條路徑的單一方向只能經過一次，所有城堡構成的圖恰好為一棵樹，每一條路徑為雙向道。

題目解法：

由於給定圖為樹，同時每一個方向只能經過一次，也就是說從某一點當作根開始走訪，一旦選擇一個子樹進行探訪，就必須完整地將子樹的城堡都佔領，才能去佔領其他子樹中的城堡，意味著，每個子樹的最優解將可以合併成整棵樹的最優解。

因此，對於子樹紀錄狀態為 (戰爭時最少士兵數量，佔領後遺失士兵數量)，在做最優解合併的時，採用貪婪的作法。

#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> g[105];
pair<int, int> D[105];
bool cmp(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first)
        return a.first > b.first;
    return a.second < b.second;
}
pair<int, int> dfs(int u, int p) {
    vector< pair<int, int> > branch;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v != p)
            branch.push_back(dfs(v, u));
    }
    sort(branch.begin(), branch.end(), cmp);
    int a, b;
    a = D[u].first, b = D[u].second;
    for(int i = 0; i < branch.size(); i++) {
        a = max(a, b + branch[i].first);
        b += branch[i].second;
    }
    return make_pair(max(a, b), b);
    
}
int main() {
    int cases = 0, a, m, gg, u, v;
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 1; i <= N; i++) {
            scanf("%d %d %d", &a, &m, &gg);	
            D[i] = make_pair(max(a, m+gg), m + gg);
        }
        for(int i = 1; i <= N; i++)
            g[i].clear();
        for(int i = 1; i < N; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        
        pair<int, int> ret = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
        for(int i = 1; i <= N; i++) 
            ret = min(ret, dfs(i, -1));
        printf("Case %d: %d\n", ++cases, ret.first);
    }
    return 0;
}

Morris' Blog