C++ 洛谷 P1273 有线电视网 题解

 P1273 有线电视网 

很明显，这是一道树形DP（图都画出来了，还不明显吗?)

未做完,持续更新中……

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=3005;
int n,m;
struct edge{
int from,to,money;
int next;
}e[maxn*4];
int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
int cnt=1,head[maxn];
int f1[maxn][maxn],f2[maxn][maxn];
int corn[maxn];
int sum;
void edge(int x,int y,int c)
{
e[cnt].from=x;
e[cnt].to=y;
e[cnt].money=c;
e[cnt].next=head[x];
head[x]=cnt++;
}
void tree_dp(int i)
{
if(i<=n-m)
for (int j=head[u];!j;j=e[j].next)
{
tree_dp(e[i].to);
}
else {
}
}
void work()
{
n=read(),m=read();
for(int i=1;i<=n-m;i++)
{
int q,w;
q=read();
for(int j=1;j<=q;j++)
{
int a,b;
a=read(),b=read();
addedge(i,a,b);
addedge(a,i,b);
}
}
for (int i=1;i<=m;i++)
scanf("%d",c[i]),sum+=c[i];
tree_dp(1);
printf("%d",ans);
}
int main()
{
work();
return 0;
}