数据程序结构设计实践 树

Question

数据结构与算法题

有一块很大的农场！农场里分成了 n 块农田,编号为 1-n，这些农田由 n-1 个沟渠联通 着。 这些沟渠中的一些已经干涸了，农场主想要让所有沟渠都保持有水。但是他只能在农田 里浇水。如果他在某块农田里浇了水，那么从这块农田到 1 号农田简单路径上的沟渠都会处 于有水的状态。显然，这样的路径只会有一条。 这个农场主想知道，他最少要浇几块农田，才能让所有沟渠都有水。

★数据输入

第一行输入一个整数 n。 接下来 n-1 行，每行三个整数 u，v，s(1<=u,v <=n)描述一条沟渠的状态，表示 u，v 之间有一条沟渠，s = 1 表示这条沟渠里有水，s = 2 表示这条沟渠干了。

★数据输出

第一行输出一个整数 k 表示最少的浇灌次数
20%：n < 10
40%: n < 100
100%:n < 100000

输入示例
5
1 2 2
2 3 2
3 4 2
4 5 2
输出示例
1
输入示例
5
1 2 1
2 3 2
2 4 1
4 5 1
输出示例
1

疑问

这个问题属于树的问题，这是为什么呢？n个点由n-1条线相连，我为什么会觉得是一长串的节点用n-1根线连接在一起？
不知道这个问题如何下手

我想要达到的结果

希望有代码的参考
可以使用C+STL

Answer 1

#include
#include
#include
#include
#include<math.h>
#include
#include<map>
#include
#include
#define E 2.718281828459
#define sf scanf
#define scf(x) scanf("%d",&x)
#define scfff(x,y,z) scanf("%d%d%d",&x,&y,&w)
#define pf printf
#define prf(x) printf("%d\n",x)
#define mm(x,b) memset((x),(b),sizeof(x))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
void in(int &x){int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f;}
typedef long long ll;
const ll mod=1e9+100;
const double eps=1e-8;
using namespace std;
const double pi=acos(-1.0);
const int inf=0xfffffff;
const int N=1e5+5;
int vis[N];
struct Edge
{
int w,to;
Edge(int x=0,int y=0){to=x;w=y; }
}t;
vector v[N];
int dfs(int x,int w)//这个节点的编码，和到这个点的沟是不是干的
{
vis[x]=1;
int ans=0;
rep(i,0,v[x].size())
{
int tt=0;
t=v[x][i];
if(vis[t.to]) continue;如果找过
if(v[t.to].size()==0&&t.w==2)//如果是叶子节点了，且到这个节点的沟没水，那么答案加一
{
ans++;
w=0;
}else if(v[t.to].size())
{
if(t.w== 1)
tt=dfs(t.to,0);
else
tt=dfs(t.to,1);
if(tt)
w=0;//如果下一个浇过水了，那么之前这条沟就有水了
}
ans+=tt;
}
if(w)
ans++;
return ans;
}</map>

int main()
{
mm(vis,0);
int n;
scf(n);
rep(i,1,n)
{
int x,y,w;
in(x);in(y);in(w);
v[x].pb(Edge(y,w));
v[y].pb(Edge(x,w));
}
int ans=dfs(1,0);
prf(ans);
return 0;
}