学步园

hdu 4118 Holiday's Accommodation 2011 Asia ChengDu Regional Contest

原题连接：http://acm.hdu.edu.cn/showproblem.php?pid=4118

解题思路：

这个题的数据规模是N <= 10^5,这个是很大的，只有O(n)的算法才行，二分匹配之类的都不用想了，最后看到一个思路，就是每一个边，求其两头所连接的点个数的较小值乘以该边的权值乘以2，所有边求和就是所求的解，这个思路我想了一会儿就明白了。我的理解就是，对于每一个边，我们都可以将这个边两头的点交换到另一头，这样的话就是这些点都要走这个边，也就是说这个边要走的次数是2*Min(左头的点数，右边的点数)。对于每一条边这个都是可以实现的，对于整个图来说，也是可以实现的！

然后我就是递归写了一个搜索树的算法，但是，结果返回爆栈。我知道这个是由于递归的太深了，造成系统的栈无法承受，没办法，只好想怎么不用递归写了

这个题让我明白了一点，ACM不仅是考算法的，而且考谁聪明！

代码如下：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
int n;

int kk;
struct note
{
    int v,next;
    long long val;
}edge[200010];
int head[100010];

void add(int son,int fa,int value)
{
    edge[kk].val = value;
    edge[kk].v = son;
    edge[kk].next = head[fa];
    head[fa] = kk++;
}

long long re;

long long dp[100010];

bool vis[100010];
void _dfs(int root)
{
    memset(vis,0,sizeof(vis));
    stack <int> sta;
    sta.push(root);
    int t = head[root];
    vis[root] = 1;
    while(1)
    {
        int y;
        if(t == -1)
        {
            y = sta.top();
            sta.pop();
            if(sta.empty()) break;
            dp[sta.top()] += dp[y];
        }
        y = sta.top();
        for(t = head[y];t != -1;t = edge[t].next)
        {
            int son = edge[t].v;
            if(vis[son] == 1) continue;
            vis[son] = 1;
            sta.push(son);
            break;
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas = 1;cas <= t;cas++)
    {
        memset(head,-1,sizeof(head));
        re = 0;
        kk = 1;
        int x,y,z;
        scanf("%d",&n);
        for(int i = 1;i < n;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        for (int i=1;i<=n;i++) dp[i]=1;
        _dfs(1);

        for (int i=1;i<=2*(n-1);i+=2) {
            x=edge[i].v;
            y=edge[i+1].v;
            long long d=min(dp[x],dp[y]);
            re += min(d,n-d)*2*edge[i].val;
        }
        cout << "Case #" << cas << ": " << re << "\n";
    }
    return 0;
}