首页 > 搜索 > DFS搜索 > HDU 3274-City Planning-DFS-[解题报告]HOJ
2014
03-13

HDU 3274-City Planning-DFS-[解题报告]HOJ

City Planning

问题描述 :

Recently Bob received a job. It’s to reform the city’s transport system. Since the city has so many villages, and the transportation network is so large that the government want to reduce the roads number. The government has just choose some of them, your duty is to build a transportation network between them to make them link with each other directly or indirectly. Meanwhile you should use the least money. You may suppose that the initial transportation network makes up a tree.

输入:

There are several test cases.
Each case starts with two integers n and m in a line. n stands for the number of all villages, m stands for the number of villages the government has chosen.( 0 < n < 1000, 0 < m <= n)
Then follow m integers in a line which means the chosen villages.
Then n – 1 lines follow, each line contains three integers a, b, c, indicating that between a and b there is a road available which costs c. (1 <= a, b <= n, a! = b, c <= 2000)

输出:

There are several test cases.
Each case starts with two integers n and m in a line. n stands for the number of all villages, m stands for the number of villages the government has chosen.( 0 < n < 1000, 0 < m <= n)
Then follow m integers in a line which means the chosen villages.
Then n – 1 lines follow, each line contains three integers a, b, c, indicating that between a and b there is a road available which costs c. (1 <= a, b <= n, a! = b, c <= 2000)

样例输入:

6 3
2 3 4
1 2 3
1 3 1
3 6 4
2 5 4
2 4 2

样例输出:

6

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn=2001;
int n,m,root,sum,NE=0,vis[maxn],head[maxn];
struct node
{
    int u,v,w,next;
} Edge[maxn];
void addEdge(int u,int v,int w)
{
    Edge[NE].u=u,Edge[NE].v=v,Edge[NE].w=w,Edge[NE].next=head[u];
    head[u]=NE++;
}
void dfs(int u,int fa)
{
    int i,j;
    for(i=head[u];i!=-1;i=Edge[i].next)
    {
        int v=Edge[i].v;
        if(v==fa)continue;
        dfs(v,u);
        if(vis[v])
        {
             sum+=Edge[i].w;
             vis[u]=1;
        }

    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j,a,b,c;
        sum=NE=0;
        memset(vis,0,sizeof(vis));
        memset(head,-1,sizeof(head));
        for(i=1; i<=m; i++)
        {
            scanf("%d",&root);
            vis[root]=1;
        }
        for(i=1; i<n; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            addEdge(a,b,c);
            addEdge(b,a,c);
        }
        dfs(root,-1);
        cout<<sum<<endl;
    }
    return 0;
}
/*
6 3
2 3 4
1 2 3
1 3 1
3 6 4
2 5 4
2 4 2
*/

参考:http://blog.csdn.net/azheng51714/article/details/8459452


,
  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。