NOI2011 道路修建

题目连接：http://221.192.240.123:8586/JudgeOnline/showproblem?problem_id=1670

题意自便。

相关知识：树的遍历，非递归DFS写法。

分析：因为树的边给定，所以从哪个点开始求都是一样的。递归求出每个点的的子树个数，计算每条边的费用。BFS和DFS其实是一样的，只不过我感觉DFS的实现更精巧一些...不知道为什么出题人要卡DFS，自我感觉BFS要更好写，莫不是它原意是考非递归...囧视。

虽然DFS不能AC，但还是贴一下代码吧（70分）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define MaxN 2000010
struct atp
{
int y,next,cost;
    }a[MaxN*2];
int first[MaxN],dur[MaxN];
bool b[MaxN]={false};
int n,m,tot=0,Maxdur=0;
long long ans;

void add(int x,int y,int z)
{
    tot++;
    a[tot].y=y;
    a[tot].cost=z;
    a[tot].next=first[x];
    first[x]=tot;
    }

void init()
{
int x,y,z;
    scanf("%d",&n);
for (int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        dur[x]++;
        dur[y]++;
if (dur[x]>dur[Maxdur]) Maxdur=x;
if (dur[y]>dur[Maxdur]) Maxdur=y;
        add(x,y,z);
        add(y,x,z);
        }
        add(0,Maxdur,0);
    }

int dfs(int u,int d,int v)
{
int t,tans=0;
    b[u]=true;
for (int p=first[u];p;p=a[p].next)
    {
        t=d+1;
if (!b[a[p].y])  tans+=dfs(a[p].y,t,p)-d;
        }

    ans+=(long long)a[v].cost*abs( (tans+1)*2-n);
//printf("  %d  %d %lld \n",tans,a[v].cost,ans);
    return tans+d;
}

int main()
{
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    init();
    b[0]=true;
    dfs(Maxdur,1,tot);
    printf("%I64d",ans);
    fclose(stdin);fclose(stdout);
    }

AC代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define MaxN 1000010
struct atp
{
int y,next,cost;
    }a[MaxN*2];
struct node
{
int cost,x,father;
       };
struct queue
{
int h,t,size;
       node d[MaxN];
       inline void init()
       {
            h=0;t=0,size=0;
            memset(d,0,sizeof(d));
            }
       inline void Push(int x,int z,int f)
       {
            size++; 
            d[++t].x=x;
            d[t].cost=a[z].cost;
            d[t].father=f;
            }
       inline node Pop()
       {
           size--;
           h++;
return d[h];
           }
       };
int first[MaxN],dur[MaxN];
int f[MaxN];
bool b[MaxN];
int n,m,tot=0,Maxdur=0;
int ch[MaxN];
long long ans;
queue q;
void add(int x,int y,int z)
{
    tot++;
    a[tot].y=y;
    a[tot].cost=z;
    a[tot].next=first[x];
    first[x]=tot;
    }
void init()
{
int x,y,z;
    scanf("%d",&n);
for (int i=1;i<=n;i++) ch[i]=1;
    ch[0]=0;
    memset(f,0,sizeof(0));
for (int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        dur[x]++;
        dur[y]++;
if (dur[x]>dur[Maxdur]) Maxdur=x;
if (dur[y]>dur[Maxdur]) Maxdur=y;
        add(x,y,z);
        add(y,x,z);
        }
        add(0,Maxdur,0);
    }
void bfs()
{

     q.init();
     b[0]=true;
     q.Push(Maxdur,tot,0);

while (q.size)
     {
           node t=q.Pop();
           f[t.x]=t.father;
           b[t.x]=true;
for (int p=first[t.x];p;p=a[p].next)
           {
if (!b[a[p].y]) q.Push(a[p].y,p,t.x);
               }
           }
     }
void work()
{
for (int i=q.t;i>=1;i--)
     {
         ch[f[q.d[i].x]]+=ch[q.d[i].x];
         ans+=(long long) q.d[i].cost*abs((ch[q.d[i].x])*2-n);
         }
     }
int main()
{
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    init();
    bfs();
    work();
    printf("%I64d",ans);
return 0;
    }