首页 > 搜索 > DFS搜索 > HDU 3289-Magic tree -DFS-[解题报告]HOJ
2014
03-13

HDU 3289-Magic tree -DFS-[解题报告]HOJ

Magic tree

问题描述 :

Sailormoon girls have a beautiful garden, though there is only a tree in it. The tree is quite magic that it will grow different fruits to fit gilrs’ demands (xq likes bananas best, wj prefers to kiwi fruits and lff loves tomatoes).
Besides these, the tree has N forks which are connected by branches, girls mark the forks by 1 to N and the root is always marked by 1. Fruits will grow on the forks and every fork will grow several fruits. But the tree is too strange that it has many branches(even between two nodes may have more than one branch). In order to pick fruits more convenient and watch more clearly, Sailormoon girls want to cut extra branches by using minimum cost, after that, they also want to know how many fruits are there in a sub-tree. The trouble is that the tree will grow new fruits and girls will pick up some ones from the tree. Can you help them?

输入:

Input contains multiple cases. Each case contains several lines.
The first line contains two integers N, M(N<=100,000, M<=151,000), representing the number of forks and the number of branches in the tree.
The following M lines each has three integers u, v and c, which means fork u and fork v are connected by a branch, if you want to cut it, you have to cost c (arbitrary two c will be different, c<=200,000).
The next line contains an integer P, representing the operations following.
"G x y" which means the fork x will grow y more fruits ;
"C x" which means girls will pick all fruits on the fork x;
"Q x" which means girls want to know the number of fruits in the sub-tree above the fork x, including the fruits (if exists) on the fork x.
Note the tree is empty at the beginning, every number will not exceed the range of integer.

输出:

Input contains multiple cases. Each case contains several lines.
The first line contains two integers N, M(N<=100,000, M<=151,000), representing the number of forks and the number of branches in the tree.
The following M lines each has three integers u, v and c, which means fork u and fork v are connected by a branch, if you want to cut it, you have to cost c (arbitrary two c will be different, c<=200,000).
The next line contains an integer P, representing the operations following.
"G x y" which means the fork x will grow y more fruits ;
"C x" which means girls will pick all fruits on the fork x;
"Q x" which means girls want to know the number of fruits in the sub-tree above the fork x, including the fruits (if exists) on the fork x.
Note the tree is empty at the beginning, every number will not exceed the range of integer.

样例输入:

3 2
1 2 4
1 3 5
7
G 1 1
G 2 1
G 3 1
Q 1
C 2
Q 2
Q 3

样例输出:

3
0
1

题意:对一棵树上的点进行实时的增减权值和询问子树的权值和

首先:单点修改以及子树查询。对整棵树dfs一遍,记录下欧拉序列。这样有一个好处,就是每一棵子树在这个序列中都是连续的,同时记录下每一棵子树的起始序列号,这样,对子树的查询就变成了一个连续区间的查询了,运用树状数组就可以解决了。

那最大生成树呢?“Sailormoon girls want to cut extra branches by using minimum cost, after that…”额,这里要将多余的边减掉,用最小cost,也就是减掉之后,变成了一棵最大生成树。郁闷呀,一开始以为题目所给的cost是没用…………

Magic tree View Code

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 100010;
int spos[MAXN],epos[MAXN],sum[MAXN],w[MAXN];
int n,f[MAXN],index;
bool vis[MAXN];
struct edge
{
    int u,v,w;
    edge(int a=0,int b=0,int c=0):u(a),v(b),w(c){}
    bool friend operator<(const edge a,const edge b)
    {
        return a.w<b.w;
    }
};
priority_queue<edge> Q;
vector<int> g[MAXN];
void init()
{
    for(int i=0;i<=n;i++)
    {
        f[i]=i;
        w[i]=sum[i]=0;
        g[i].clear();
    }
}
int find(int x)
{
    if(x==f[x])
        return f[x];
    f[x]=find(f[x]);
    return f[x];
}
void Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b) return ;
    f[a]=b;
    g[x].push_back(y);//重新构建树
    g[y].push_back(x);
}
void Kruskal()//将所有边压入优先队列,再取出所有边合并,求最大生成树
{
    while(!Q.empty())
    {
        Union(Q.top().u,Q.top().v);
        Q.pop();
    }
}
int lowbit(int x)//这里往下三个函数就是树状数组的模板函数了,就不多说了
{
    return x&(-x);
}
void modify(int x,int add)
{
    while(x<=n)
    {
        sum[x]+=add;
        x+=lowbit(x);
    }
}
int get_sum(int x)
{
    int ret=0;
    while(x!=0)
    {
        ret+=sum[x];
        x-=lowbit(x);
    }
    return ret;
}
void dfs(int u)
{
    spos[u]=index;//记录子树的起始位置
    vis[u]=true;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(!vis[v])
        {
            index++;
            dfs(v);
        }
    }
    epos[u]=index;//记录子树的终点位置
}
int main()
{
    int m,k,a,b,c;
    char str[5];
    while(scanf("%d %d",&n,&m)==2)
    {
        init();
        while(m--)
        {
            scanf("%d %d %d",&a,&b,&c);
            Q.push(edge(a,b,c));
        }
        Kruskal();
        index=1;
        memset(vis,false,sizeof(vis));
        dfs(1);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%s",str);
            if(str[0]=='G')
            {
                scanf("%d %d",&a,&c);
                modify(spos[a],c);
                w[a]+=c;
            }
            else if(str[0]=='C')
            {
                scanf("%d",&a);
                modify(spos[a],-w[a]);
                w[a]=0;
            }
            else {
                scanf("%d",&a);
                int ans=get_sum(epos[a])-get_sum(spos[a]-1);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

 

参考:http://www.cnblogs.com/nanke/archive/2012/02/26/2368818.html


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  3. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  4. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。