hdu2196
找最长次长。
其实不如直接找直径后倍增。
树DP练手题。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 2e4;
struct E{int v, n, w;}e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
int d[maxn], cd[maxn], s[maxn];
void dfs(int u = 1, int f = 0)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
    {
        dfs(v, u);
        if(d[v] + e[i].w > d[u]) cd[u] = max(cd[u], d[u]), d[u] = d[v] + e[i].w;
        else cd[u] = max(cd[u], d[v] + e[i].w);
    }
}
void dfs2(int u = 1, int f = 0)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
    {
        s[v] = (d[u] == d[v] + e[i].w ? cd[u] + e[i].w : d[u] + e[i].w);
        s[v] = max(s[v], s[u] + e[i].w);
        dfs2(v, u);
    }
}
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        memset(h, 0, sizeof h); ec = 1;
        memset(d, 0, sizeof d); memset(cd, 0, sizeof cd); memset(s, 0, sizeof s);
        for(int i = 2, u, v; i <= n; i++) read(u, v), add_edge(u, i, v), add_edge(i, u, v);
        dfs(); 
        dfs2();
        for(int i = 1; i <= n; i++) printf("%d\n", max(s[i], d[i]));
    }
    return 0;
}

zoj3201
看起来是$ O(n^3) $实际上是 $ O(n^2) $。
树上背包,树依赖性DP。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e3;
struct E{int v, n;} e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v){e[ec] = (E){v, h[u]}; h[u] = ec++;}
int tmp[maxn], size[maxn], dp[maxn][maxn], a[maxn], ans = 0;
int n, k;
void dfs(int u = 0, int f = -1)
{
    size[u] = 1; dp[u][1] = a[u];
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
    {
        dfs(v, u);
        memcpy(tmp, dp[u], sizeof tmp);
        for(int j = 1; j <= size[u]; j++) for(int k = 0; k <= size[v]; k++)
            tmp[j + k] = max(tmp[j + k], dp[u][j] + dp[v][k]);
        size[u] += size[v];
        for(int i = 2; i <= size[u]; i++) dp[u][i] = max(dp[u][i], tmp[i]);
    }
    ans = max(ans, dp[u][k]);
}
int main()
{
    while(~scanf("%d%d", &n, &k))
    {
        memset(h, 0, sizeof h); ec = 1; memset(dp, 0, sizeof dp);
        for(int i = 0; i < n; i++) read(a[i]);
        for(int i = 1, u, v; i < n; i++) read(u, v), add_edge(u, v), add_edge(v, u);
        ans = 0;
        dfs();
        printf("%d\n", ans);
    }
    return 0;
}

HDU4003
dpu表示以u为根子树j机器人停止的总路程。j=0表示有1个(可以证明最多1个)机器人走回父亲。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e5 + 10;
int n, s, k;
struct E{int v, n, w; } e[maxn << 1];
int h[maxn], ec = 1, size[maxn];
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
int dp[maxn][15], tmp[15];
void dfs(int u = s, int f = 0)
{
    size[u] = 1;
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
    {
        dfs(v, u);
         for(int j = k; ~j; j--) 
         {
             dp[u][j] += dp[v][0] + 2 * e[i].w;
             for(int k = 1; k <= j; k++)
                 dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k] + k * e[i].w);
         }
         size[u] += size[v];
    }
}
int main()
{
    while(~scanf("%d%d%d", &n, &s, &k))
    {
        memset(h, 0, sizeof h); ec = 1;
        memset(dp, 0, sizeof dp);
        for(int i = 1, u, v, w; i < n; i++) read(u, v, w), add_edge(u, v, w), add_edge(v, u, w);
        dfs();
        printf("%d\n", dp[s][k]);
    }    
    return 0;
}

poj1848
Sol: dpu represents 0)all in circles; 1)except for the root; 2)except for a certain chain;
Dp[v][0] forall v -> dp[u][1]
Dp[v][2] v=v’ dp[v][0] vneq v’ -> dp[u][0]
Dpv v=v’,v’’ dpv vneq v’,v’’ -> dpu
Dpv v=v’, dpv vneq v’ -> dpu

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e3, INF = 100000;
struct E{int v, n;} e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v){e[ec] = (E){v, h[u]}; h[u] = ec++;}
int dp[maxn][3];
void dfs(int u = 1, int f = 0)
{
    dp[u][1] = 0;
    bool flag = false;
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
    {
        dfs(v, u);
        flag = true;
        dp[u][1] += dp[v][0];
    }
    //dp[u][1] = min(dp[u][1], INF);
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
    {
        dp[u][0] = min(dp[u][0], dp[u][1] - dp[v][0] + dp[v][2] + 1);
        dp[u][2] = min(dp[u][2], dp[u][1] - dp[v][0] + min(dp[v][1], dp[v][2]));
    }
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f) for(int j = e[i].n, w = e[j].v; j; j = e[j].n, w = e[j].v) if(w != f)
    {
        dp[u][0] = min(dp[u][0], dp[u][1] - dp[v][0] - dp[w][0] + min(min(dp[v][1] + dp[w][1], dp[v][1] + dp[w][2]), min(dp[v][2] + dp[w][1], dp[v][2] + dp[w][2])) + 1);
    }
    dp[u][1] = min(dp[u][1], INF);
}
int main()
{
    int n; read(n);
    for(int i = 1; i <= n; i++) dp[i][0] = dp[i][1] = dp[i][2] = INF; 
    for(int i = 1, u, v; i < n; i++) read(u, v), add_edge(u, v), add_edge(v, u);
    dfs();
    printf("%d\n", dp[1][0] >= INF ? -1 : dp[1][0]);
    return 0;
}

hdu3586
二分+Dp

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e4, INF = 1000010;
int n, m, M;
struct E{int v, n, w;} e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
int dp[maxn];
void dfs(int u = 1, int f = 0)
{
    dp[u] = 0; bool flag = false;
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
        dfs(v, u), flag = true, e[i].w > M ? dp[u] += dp[v] : dp[u] += min(dp[v], e[i].w);
    if(!flag) dp[u] = INF; 
}
int main()
{
    while(read(n, m), n || m)
    {
        memset(h, 0, sizeof h); ec = 1;
        memset(dp, 0, sizeof dp);
        int L = 1, R = 0;
        for(int i = 1, u, v, w; i < n; i++) read(u, v, w), add_edge(u, v, w), add_edge(v, u, w), R = max(R, w);
        while(L < R)
        {
            M = (L + R) >> 1;
            dfs();
            if(dp[1] > m) L = M + 1;
            else R = M;
        }
        M = L;
        dfs();
        printf("%d\n", dp[1] > m ? -1 : L);
    }
    return 0;
}

标签: none

添加新评论