Hdu4582-DFS spanning tree VS Pku2152-Fire 범주 트리 최소 덮어쓰기 문제

Pku2152-Fire
제목: 어느 나라의 N 개 도시 사이에 나무형 교통망이 형성된다.현재 일부 도시에 소방소를 건설해야 하는데 요구: 각 도시 i는 자신의 소방소가 있거나 가장 가까운 소방소가 있는 도시에서 Di를 초과하지 않는다(각 도시의 요구는 모두 같지 않다).아울러 도시별로 소방소를 짓는 비용인 Wi가 알려진 것도 모두 같지 않다.소방서 건설 총 비용을 묻다.해법: 트리 동적 기획.DP로 문제를 푸는 것이 어렵지 않다는 것을 생각하면 어려운 것은 DP를 어떻게 푸는지 생각해 내는 것이다.상태의 디자인에 대해 우리는 이것이 2차원 상태를 사용해야 한다는 것을 짐작할 수 있다. 그 중에서 1차원은 Dp 과정 중의 현재 도시 i를 나타내고 다른 1차원은 i와 어떤 소방서(어느 것이 가장 가까운 것으로 치자)의 거리(거리가 hash일 수 있다)거나 도시 번호 j로 소방서를 건설한 것이고 i에서 j까지의 거리는 Di를 초과하지 않는다.가능한 Dp 이전 방안을 종합해 보면 이 두 가지 표현이 모두 어색하거나 정확한 상태를 효과적으로 표현하지 못할 것 같아 복잡도가 걱정된다.자, 잔소리 그만하고 왜 두 번째가 가능한지 말해 봐.우선 우리는 이 뿌리 없는 나무를 마음대로 뿌리를 하나 세워 뿌리 있는 나무로 바꾸자.dp[j][i]는 j에 소방소를 건설하여 i를 뿌리로 하는 자수 중의 노드 도시에 모두 사용할 수 있는 소방소가 있음을 만족시키고dis(i, j)<=Di의 최소 건설 비용(j의 비용 포함하지 않음)을 충족시켰다고 밝혔다.여기서 우리는 i가 j(j가 i에게 소방소를 제공한다고 가정한다).우선, 우리는 어느 도시에 대해 Di 범위 내에 역을 건설했다는 것을 알아야 한다. 가장 가까운 역이 어디에 서 있든 상관하지 마라. 또한 Dp 과정에서 가장 좋은 결과를 놓치지 않을 것을 보증하면 우리는 상태를 옮길 때 반드시 가장 좋은 상태가 될 수 없는 하위 상태를 버리는 것이 가능하다.상태 전이 방정식은 dp[i][u]=sigma(min{dp[i][v], dp[j][v]+W[j]})이다.그 중에서 v는 u의 아들 노드이다. 디스(i, v)<=Dv라면 dp[i][u]에 dp[i][v]를 더해야 한다. 그렇지 않으면 v는 i에 의지할 수 없고 다른 도시 j만 의지할 수 있으며 총 비용(W[j] 포함)이 가장 적다는 뜻이다.보기 쉬운 dp[][]의 초기 값은 infinity로 설정해야 합니다.국부적 최우성을 확보했다. dp[i][v]->dp[i][u]는 나무랄 데가 없다. 관건은 u가 여러 아들 노드가 있을 때, 예를 들어 v와 v가 있을 때 모두 dp[j]+W[j], dp[v]+W[j], 즉 두 시에 같은 점에 의존하면 W[j]가 중복되지 않겠는가?이 걱정은 조금도 불필요하지 않다. 그것은 실제로 존재하기 때문에 이런 예를 쉽게 들 수 있다.그러나 이렇게 하면 실행할 수 있다. 이렇게 계산된 상태는 최우해에 영향을 주지 않을 것이다. 이런 상태는 방정식의 통일성을 옮기기 위해 희생된 비최우해 상태이다.다음은 왜 최우해에 영향을 주지 않는지 설명해 드리겠습니다.이런 상황이 발생하는 데는 두 가지 가능성이 있다. 하나는 j가 u의 어떤 아들 나무에 있는 것이고 다른 하나는 j가 u의 아버지 대, 심지어 조상이다. 그러나 모두 특징이 있다. v(v'또는 다른 j에 의존하는 u의 아들 노드)에서 j까지의 경로는 반드시 u를 통과한다. 그리고 j에서 u까지의 거리는 i에서 u까지의 거리보다 작다. 그렇지 않으면 v들은 반드시 i에 의존할 수 있다.이때 당신은 이런 조건에서 u도 j에 의존할 수 있다는 것을 알게 될 것입니다. j가 더 가깝기 때문에 (i처에 사이트를 건설하든 안 건설하든) dp[i][u]의 비용은 dp[j][u]보다 우수하지 않을 것입니다. 그리고 dp[j][u]에서 어떤 W 중복 계산이 나타나지 않을 것입니다. 우선 W[j]는 그렇지 않습니다. 다른 유사한 j'(i 포함),dis(j',u)>=dis(j,u)도 틀림없습니다.이런 효과적인 dp[j][u]만 있으면 충분하다.또한min{dp[j][v]+W[j]}를 계산할 때 dp[i][v]를 구하면서 계산할 수 있어 복잡도를 낮출 수 있다.

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1002;
const int INF = 0x3f3f3f3f;

int n, W[N], D[N], fa[N], dis[N][N], dp[N][N], best[N];
vector<pair<int, int> > e[N];

void getDis(int rt, int u, int curDis) {
    dis[rt][u] = curDis;
    for (int i = 0; i != (int)e[u].size(); i++) {
        int v = e[u][i].first;
        if (v == fa[u]) continue;
        fa[v] = u;
        getDis(rt, v, curDis + e[u][i].second);
    }
}

void DP(int u) {
    for (int i = 0; i != (int)e[u].size(); i++) {
        int v = e[u][i].first;
        if (v == fa[u]) continue;
        DP(v);
    }

    best[u] = INF;
    for (int i = 0; i < n; i++) if (dis[i][u] <= D[u]) {
        dp[i][u] = 0;
        for (int j = 0; j != (int)e[u].size(); j++) {
            int v = e[u][j].first;
            if (v == fa[u]) continue;
            dp[i][u] += min(best[v], dp[i][v]);
        }
        best[u] = min(best[u], dp[i][u] + W[i]);
    }
}

int main() {
    int cas, u, v, w;
    scanf("%d", &cas);
    while (cas--) {
        for (int i = 0; i < N; i++) e[i].clear();
        memset(dp, 0x3f, sizeof(dp));

        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", &W[i]);
        for (int i = 0; i < n; i++) scanf("%d", &D[i]);
        for (int i = 1; i < n; i++) {
            scanf("%d%d%d", &u, &v, &w);
            u--, v--;
            e[u].push_back(make_pair(v, w));
            e[v].push_back(make_pair(u, w));
        }
        for (int i = n-1; i >= 0; i--) fa[i] = i, getDis(i, i, 0);
        DP(0);
        printf("%d
", best[0]);
    }
    return 0;
}

Hdu4582-DFS spanning tree
제목: 생략
분석: 각 T-simple환의 나무 가장자리에 있는 점의 깊이가 순서대로 줄어들거나 커지지 않을 뿐만 아니라 특정한 점 x의 다른 하위 나무에서 오지 않을 것이다. 이것은 나무형 DP에 조건을 제공했다.고리는 고리에서 깊이가 가장 큰 점 v와 깊이가 가장 작은 점 u로 나타낼 수 있다. v와 같은 고리에 대해 우리는 가장 작은 것만 처리하면 된다. 왜냐하면 작은 고리의 나무 가장자리가 모두 큰 고리 안에 있기 때문이다.그리고 우리는 어떤 고리에 대해 v~u 경로의 변으로 이 고리를 덮을 수 있음을 알 수 있다. 답은 고리의 최소 변수를 덮어쓰는 것이다.더 나아가 우리는 v~u 경로의 가장자리로 v점을 덮어쓰는 것으로 이해할 수 있다.그리고 우리는 이 문제가 이전 문제와 매우 비슷하다는 것을 알 수 있다. 내가 여기서 그것이 비슷하다고 말하는 것은 모두 덮어쓰는 것이 아니라 특정한 점 v의 다른 점은 반드시 v의 부근에서 연결된 블록을 형성하는 것이다. 이것이야말로 이런 문제를 DP해석하는 관건적인 부분이다.그러나 이전 문제는 모든 점을 덮어씌워야 한다. 이 문제는 링의 밑에 있지 않은 부분이 있을 수 있다. 이런 점은 특별히 처리해야 한다. 세부 부분은 코드를 볼 수 있다.항저우에서 현장에서 시합을 할 때 어떻게 해야 할지 전혀 몰랐다. 시합 후에 과대의 신우에게 물었는데 결과는 알아듣지 못했고 다시 물어보지도 못했다. 이제 드디어 할 수 있게 되었다. 매우 약하다.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
using namespace std;

typedef double DB;
typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<bool> VB;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<VI> VVI;
typedef vector<PII> VPII;

#define PB push_back
#define MP make_pair
#define CLR(a, x) memset(a, x, sizeof(a))
#define FOR(i, s, t) for (int i = (s); i < (int)(t); i++)
#define FORD(i, s, t) for (int i = (t) - 1; i >= (int)(s); i--)
#define VREP(i, v) for (int i = 0; i < (int)(v).size(); i++)
#define REP(i, t) for (int i = 0; i < (int)(t); i++)
#define REPD(i, t) for (int i = (t) - 1; i >= 0; i--)
#define REP2(i, j, n, m) for (int i = 0; i < (int)(n); i++) for (int j = 0; j < (int)(m); j++)
#define REP3(i, j, k, n, m, l) for (int i = 0; i < (int)(n); i++) for (int j = 0; j < (int)(m); j++) for (int k = 0; k < (int)(l); k++)
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)

template <class T> inline void checkMin(T& a, T b) { if (b < a) a = b; }
template <class T> inline void checkMax(T& a, T b) { if (b > a) a = b; }
inline int& RD(int& x) { scanf("%d", &x); return x; }
inline int& RD(int& x, int& y) { scanf("%d%d", &x, &y); return x; }
inline int& RD(int& x, int& y, int& z) { scanf("%d%d%d", &x, &y, &z); return x; }
inline DB& RD(DB& x) { scanf("%lf", &x); return x; }
inline DB& RD(DB& x, DB& y) { scanf("%lf%lf", &x, &y); return x; }
inline DB& RD(DB& x, DB& y, DB& z) { scanf("%lf%lf%lf", &x, &y, &z); return x; }
inline void WT(int x) { printf("%d
", x); }
inline void WT(int x, int y) { printf("%d %d
", x, y); }
inline void WT(int x, int y, int z) { printf("%d %d %d
", x, y, z); }

const int N = 2005;
const int INF = 0x3f3f3f3f;
const LL LINF = 1ll << 62;
const DB DINF = 1e20;
const int MOD = 1000000007;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int en, head[N], fa[N], dep[N], top[N];
bool cir[N];
struct Edge { int to, next; } e[N * 2];

void dfsDep(int u) {
    for (int i = head[u]; i != -1; i = e[i].next) if (e[i].to != fa[u]) {
        fa[e[i].to] = u; dep[e[i].to] = dep[u] + 1;
        dfsDep(e[i].to);
    }
}

VI rely[N];
int dp[N][N], best[N];
void DP(int u) {
    for (int i = head[u]; i != -1; i = e[i].next) if (e[i].to != fa[u]) DP(e[i].to);

    best[u] = 0;
    for (int i = head[u]; i != -1; i = e[i].next) if (e[i].to != fa[u]) best[u] += best[e[i].to];
    if (cir[u]) best[u]++;
    for (int x = u; x != top[u]; x = fa[x]) {
        dp[u][x] = 0;
        for (int i = head[u]; i != -1; i = e[i].next) if (e[i].to != fa[u]) dp[u][x] += min(best[e[i].to], dp[e[i].to][x]);
        checkMin(best[u], dp[u][x] + 1);
    }
}

int main() {
    int n, m; while (RD(n, m)) {
        en = 0; CLR(head, -1);
        REP(i, n-1) {
            int u, v; RD(u, v); u--, v--;
            e[en] = (Edge) {v, head[u]}; head[u] = en++;
            e[en] = (Edge) {u, head[v]}; head[v] = en++;
        }

        dep[0] = 0; CLR(cir, false); CLR(top, 0);
        dfsDep(0);
        FOR(i, n-1, m) {
            int u, v; RD(u, v); u--, v--;
            if (dep[u] > dep[v]) swap(u, v);
            if (dep[u] > dep[top[v]]) top[v] = u; // top[v]  v         
            cir[v] = true; //            
        }

        CLR(dp, 0x3f);
        DP(0);
        WT(best[0]);

    }
    return 0;
}