树的点分治（poj 1741， 1655（树形dp））

poj 1655:http://poj.org/problem?id=1655

题意：给无根树，找出以一节点为根，使节点最多的树，节点最少。

题解：一道树形dp，先dfs 标记所有节点的子树的节点数。再dfs 找出以某节点为根的最大子树，节点最少。复杂度（n）

/***Good Luck***/

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <stack>

#include <map>

#include <queue>

#include <vector>

#include <set>

#include <functional>

#include <cmath>

#define Zero(a) memset(a, 0, sizeof(a))

#define Neg(a)  memset(a, -1, sizeof(a))

#define All(a) a.begin(), a.end()

#define PB push_back

#define inf 0x7fffffff

#define inf2 0x7fffffffffffffff

#define ll long long

using namespace std;

const int maxn = ;

int n, k, e, head[maxn];

int mx[maxn], sum[maxn], ansn, ansb;

struct Node {

    int next, v;

}node[maxn];

void input(int u, int v) {

    node[e].next = head[u];

    node[e].v = v;

    head[u] = e++;

}

int dfssize(int b, int fa) {

    sum[b] = ;

    mx[b] = ;

    int tmpmx;

    for (int i = head[b]; ~i; i = node[i].next) {

        int v = node[i].v;

        if (fa != v) {

            tmpmx = dfssize(v, b);

            sum[b] +=tmpmx;

            if (tmpmx > mx[b]) mx[b] = tmpmx;

        }

    }

    return sum[b];

}

void solve(int b, int fa) {

    int tmpmx;

    tmpmx = max(mx[b], n - sum[b]);

    if (tmpmx <= ansb) {

        if (tmpmx < ansb) {

            ansn = b;

            ansb = tmpmx;

        } else if (b < ansn) {

            ansn = b;

            ansb = tmpmx;

        }

    }

    for (int i = head[b]; ~i; i = node[i].next) {

        int v = node[i].v;

        if (fa != v) {

            solve(v, b);

        }

    }

}

int main() {

    int u, v;

    int T;

    scanf("%d", &T);

    while (T-- ) {

        scanf("%d", &n);

        e = ;

        Neg(head);

        for (int i = ; i < n - ; ++i) {

            scanf("%d%d", &u, &v);

            input(u, v);

            input(v, u);

        }

        dfssize(, );

        ansb = inf;

        solve(, );

        printf("%d %d\n", ansn, ansb);

    }

    return ;

}

poj 1741:http://poj.org/problem?id=1741

题意：给一值k，在带权无向图G中，找出两节点相距不大于k的数。

　　qzc论文的第一题（膜拜q神 orz），根据论文写的代码，先写了一题树形dp（1655），再开始写这的，搞了一晚上具体的还是看论文吧。

找根（n），计算（logn），一共执行 logn次总复杂度（n*logn*logn）

 /***Good Luck***/

 #define _CRT_SECURE_NO_WARNINGS

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <stack>

 #include <map>

 #include <queue>

 #include <vector>

 #include <set>

 #include <functional>

 #include <cmath>

 #define Zero(a) memset(a, 0, sizeof(a))

 #define Neg(a)  memset(a, -1, sizeof(a))

 #define All(a) a.begin(), a.end()

 #define PB push_back

 #define inf 0x3f3f3f3f

 #define inf2 0x7fffffffffffffff

 #define ll long long

 using namespace std;

 const int maxn = ;

 int head[maxn], n, k, e;

 int ans, sum[maxn], mx[maxn];

 bool vis[maxn];

 int dis[maxn], a[maxn], an;

 struct Node {

     int w;

     int v, next;

 }edge[maxn];

 void init() {

     e = ;

     ans = ;

     Neg(head);

     Zero(vis);

 }

 void add(int u, int v, int w) { //邻接表储存

     edge[e].v = v;

     edge[e].w = w;

     edge[e].next = head[u];

     head[u] = e++;

 }

 int dfssize(int u, int fa) {  //标记子树的节点数

     sum[u] = ;

     mx[u] = ;

     int tmpmx;

     for (int i = head[u]; ~i; i = edge[i].next) {

         int v = edge[i].v;

         if (v != fa && !vis[v]) {

             tmpmx = dfssize(v, u);

             sum[u] += tmpmx;

             if (tmpmx > mx[u]) mx[u] = tmpmx;

         }

     }

     return sum[u];

 }

 int ansn, mxshu;

 void find_root(int u, int fa, int nn) {  // 找出符合条件的根。

     int tmpmx = max(mx[u], nn - sum[u]);

     if (tmpmx < mxshu) {

         ansn = u;

         mxshu = tmpmx;

     }

     for (int i = head[u]; ~i; i = edge[i].next) {

         int v = edge[i].v;

         if (v != fa && !vis[v]) {

             find_root(v, u, nn);

         }

     }

 }

 void dfsdis(int u, int fa) {

     a[an++] = dis[u];

     for (int i = head[u]; ~i; i = edge[i].next) {

         int v = edge[i].v;

         if (fa != v && !vis[v]) {

             dis[v] = dis[u] + edge[i].w;

             dfsdis(v, u);

         }

     }

 }

 int cal(int u, int fa, int beg) {  //  这个方法太神奇了 复杂度只有 （logn）

     an = ;

     int ret = ;

     dis[u] = beg;

     dfsdis(u, fa);

     sort(a, a + an);

     int l = , r = an - ;

     while (l < r) {

         if (a[r] + a[l] <= k )

             ret += r - l++;

         else

             r--;

     }

     return ret;

 }

 void solve(int u) {

     dfssize(u, );

     mxshu = inf;

     find_root(u, , sum[u]);

     vis[ansn] = true;

     ans += cal(ansn, , );

     for (int i = head[ansn]; ~i; i = edge[i].next) {

         int v = edge[i].v;

         if (!vis[v]) {

             ans -= cal(v, ansn, edge[i].w);

             solve(v);

         }

     }

 }

 int main() {

     //freopen("data.out", "w", stdout);

     //freopen("data.in", "r", stdin);

     int u, v, w;

     while (scanf("%d%d", &n, &k), n&&k) {

         init();

         for (int i = ; i < n - ; ++i) {

             scanf("%d%d%d", &u, &v, &w);

             add(u, v, w);

             add(v, u, w);

         }

         solve();

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

树的点分治（poj 1741， 1655（树形dp））

最新文章

热门文章

巴特西

树的点分治 （poj 1741， 1655（树形dp））

最新文章

热门文章

树的点分治（poj 1741， 1655（树形dp））