P1305选课

题目描述：

学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

输入：

输入文件的第一行包括两个整数N、M（中间用一个空格隔开），其中1≤N≤300,1≤M≤N。 以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。

输出：

  1. 第一行：只有一个数：实际所选课程的学分总数。
  2. 下面m行：从下到大所选择的课程。

题解：

这道题相对于上一道题不过是多了一种选择的方案输出而已，我们在转化为二叉树的基础上，愉快的再次建立一个bool数组 ans[i] 来表示这个点 i 是否被选中，然后再次一个DFS递归，如果当前的 f[x][y]==f[Borther[x]][y] 那么我们就继续递归 DFS(Brother[x],y) 就行，当前这个点x完全可以扔掉了！如果当前的 if(f[x][y]==f[Brother[x]][i-1]+f[Child[x]][y-i]+Value[x]) ，那么我们就可以判定，当前点x一定是被选中的，然后分别对两个分支进行DFS，一个是儿子，一个是兄弟，然后就可以return了。

记f[x][j]表示以点x为根，选择j个黑点，对答案的最大贡献
为什么是说“对答案的最大贡献呢”？首先我们是从x的子节点y转移过来，那么主要是想到一点，即分别考虑每条边x→y对答案的贡献，也就是“边一侧的黑点数 × 另一侧的黑点数 × 边的长度 + 边一侧的白点数 × 另一侧的白点数 × 边的长度”
我们记sze[x]表示以x为根的子树大小，边x→y对答案的贡献为valx→y，则状态转移方程为：
f[x][j]=Max(f[x][j−k]+f[y][k]+valx→y)
=Max(f[x][j−k]+f[y][k]+k×(j−k)×lenx→y+(sze[y]−k)×(n−m−sze[y]+k)×lenx→y)
看起来我们要枚举x→y,k,j，复杂度为O(n3)，实际上我们会发现枚举的范围为0≤k≤sze[y],0≤j−k≤sze[x]−sze[y]，那么总的枚举次数就为∑(sze[x]−sze[y])×sze[y]，我们不妨把其看作每次在以某一点x为根的子树上任选两个点a,b，使得a,b的最近公共祖先为x的方案数，因此实际复杂度为O(n2)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,Value[600],Brother[600],x;
int f[600][600],Child[600];
bool ans[600];
void DFS(int x,int y)
{
    if(f[x][y]>=0) return;
    if(x==0||y==0)
    {
        f[x][y]=0;
        return;
    }
    DFS(Brother[x],y);
    for(int i=0;i<y;i++)
    {
        DFS(Brother[x],i);
        DFS(Child[x],y-i-1);
        int This=max(f[Brother[x]][y],f[x][y]);
        f[x][y]=max(This,f[Brother[x]][i]+f[Child[x]][y-i-1]+Value[x]);
    }
}
void Find(int x,int y)
{
    if(x==0||y==0) return;
    if(f[x][y]==f[Brother[x]][y])
    Find(Brother[x],y);
    else for(int i=1;i<=y;i++)
    if(f[x][y]==f[Brother[x]][i-1]+f[Child[x]][y-i]+Value[x])
    {
        Find(Brother[x],i-1);
        Find(Child[x],y-i);
        ans[x]=true;
        return;
    }
}
int main()
{
    memset(f,-1,sizeof(f));
    memset(ans,0,sizeof(ans));
    memset(Child,0,sizeof(Child));
    memset(Brother,0,sizeof(Brother));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>Value[i];
        Brother[i]=Child[x];
        Child[x]=i;
    }
    DFS(Child[0],m);
    cout<<f[Child[0]][m]<<endl;
    Find(Child[0],m);
    for(int i=1;i<=n;i++)
    if(ans[i]) cout<<i<<endl;
    return 0;
}

P1306河流

题目描述：

几乎整个Byteland 王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——Bytetown。

  • 在Byteland国，有n个伐木的村庄，这些村庄都座落在河边。目前在Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到Bytetown的伐木场。Byteland 的国王决定，为了减少运输木料的费用，再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown了，它们可以在 运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。 注：所有的河流都不会分叉，形成一棵树，根结点是Bytetown。

国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米1分钱。

输入：

  1. 第一行包括两个数n（2<=n<=100），k（1<=k<=50,且k<=n）。n为村庄数，k为要建的伐木场的数目。除了Bytetown 外，每个村子依次被命名为 1，2，3……n，Bytetown被命名为0。
  2. 接下来n行，每行3个整数： wi——每年 i 村子产的木料的块数。（0<=wi<=10000）vi——离 i 村子下游最近的村子。（即 i 村子的父结点）（0<=vi<=n）di——vi 到 i 的距离(千米)。（1<=di<=10000)
  3. 保证每年所有的木料流到bytetown 的运费不超过2000,000,000分.50％的数据中n不超过20。

输出：

一行，最小的运费。

题解：

拿到这道题，其实我是想了好久的，尝试了各种各种DP的方法，但是一直GG，后来我突然想到了上一道题所用到的多叉树转二叉树的方法，然后用DFS遍历所有的点就可以了，最开始的时候我设置的状态 f[i][j][k] 表示的是对于当前节点i，一共使用j个工厂，然后k表示true或者false表示是否在当前进行建立工厂的最优值。但是发现又不行，因为距离是没有办法进行记录的，也就是说，这样的话记录下来没有办法确定木头的运输距离，也就是不知道距离它最近的工厂的位置，那么我们就更改一下状态的设置，我们表示出来 f[i][j][k] 表示的是对于第i个点，距离他最近有工厂的点为j，其中选择建造了k个工厂。然后在DFS传参数的时候加上距离dis一项，然后我们就可以进行愉快的计算了。

然后对于一个点x，我们有两种选择方法，也就是第一种，自己建造工厂和自己用别人的工厂，那么我们就进行两次DP，然后在其中求出最优值，如果不在这里进行建造工厂的话枚举i从0到k，表示自己的儿子负担i个，然后兄弟们负担 k-i 个。

第二种，如果自己亲自进行建造工厂，那么枚举i从0到k-1，然后表示自己的孩子一共建造i个，然后自己的兄弟们负责建造 k-i-1 个（减去的1表示点x已经建造了一个工厂）

以后看到题想不清楚了，然后仔细推一推看看自己的状态设置是不是少了什么，是不是有些是没有用的，可以用更加强大的进行代替掉，然后就是参数的传递上需要进行传递什么，也要仔细考虑清楚的！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,Child[200],Brother[200],len=0,x,Get;
int f[200][200][200],Weight[200],Distance[200];
bool vis[200];
int DFS(int x,int Root,int k,int dis)
{
    if(x==-1||Root==-1) return 0;
    if(f[x][Root][k]!=Get) return f[x][Root][k];
    int LHH=f[x][Root][k];
    for(int i=0;i<=k;i++) //如果不去建造伐木场
    {
        int First=DFS(Child[x],Root,i,dis+Distance[x]);
        int Second=DFS(Brother[x],Root,k-i,dis);
        int Value=(dis+Distance[x])*Weight[x];
        LHH=min(LHH,First+Second+Value);
    }
    for(int i=0;i<k;i++) //如果选择建造伐木场
    {
        int First=DFS(Child[x],x,i,0);
        int Second=DFS(Brother[x],Root,k-i-1,dis);
        LHH=min(LHH,First+Second);
    }
    f[x][Root][k]=LHH;
    return f[x][Root][k];
}
int main()
{
    memset(Child,-1,sizeof(Child));
    memset(vis,false,sizeof(vis));
    memset(Brother,-1,sizeof(Brother));
    memset(f,120,sizeof(f));
    cin>>n>>m;
    Get=f[0][0][0];
    for(int i=1;i<=n;i++)
    {
        cin>>Weight[i]>>x>>Distance[i];
        Brother[i]=Child[x];
        Child[x]=i;
    }
    cout<<DFS(0,0,m,0)<<endl;
    return 0;
}

P1512软件安装

题目描述：

  • 现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M的计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
  • 但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件吗i依赖软件j）。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么他能够发挥的作用为0。
  • 我们现在知道了软件之间的依赖关系：软件i依赖Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这是只要这个软件安装了，它就能正常工作。

输入:

  1. 第1行：N,M （0<=N<=100,0<=M<=500）
  2. 第2行：W1,W2, … Wi, … ,Wn
  3. 第3行：V1,V2, … Vi, … ,Vn
  4. 第4行：D1,D2, … Di, … ,Dn

输出：

一个整数，代表最大价值。

题解：

这道题也是非常神奇的，一开始我是忽略掉了可能会出现环的情况，然后就开心的当成了选课，多叉转二叉，DFS直接开始深搜……然后就只拿到了40分（省选题暴力搞到40分也是蛮不错的）

然后仔细想了想，发现的确可能出现环的情况，在左右思索无助的时候还是忍不住的看了题解QAQ，然后就来总结一发。

这道题的其实可以通过题目上的一个条件很清楚的看出来，因为题目上已经说过了，如果没有安装他的依赖软件，那么这个软件也是可以安装的，但是权值为0，所以这里就决定了这个图并不是寻常的树规……

对于出现环的关系，也就是1依赖2，2依赖1，那么出现这种情况的时候，我们就可以将2和1看作是一个点了，如果选择这个点那么就是肯定里面的1和2都选择，如果不选择这个点，那么权值和重量就全都是0了。

如果里面只选择1的话，结果就和全部都不选是一样的。那么我们就可以用Tarjan算法求出所有的联通分量，然后将所有的联通分量当成一个点，然后重新建造一个二叉树，在重新建造的二叉树上进行DP，状态设置就是 f[i][j] 表示对于节点i在承受j重量下，所能达到的最大权值。（变量声明的有些多QAQ）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
struct Edge
{
    int Next;
    int Point;
}a[200];
int Value[200],Weight[200],n,m,len=0,This;
int Father,Link_First[200],f[200][600],top=0;
int ind=0,low[200],dfn[200],tot=0,Stack[200];
int Belong[200],Avalue[200],Aweight[200];
int Link_Second[200],Child[200],Brother[200];
bool Vis[200],Get[200],Find[200][600];
void Tarjan(int x)
{
    int This=0;
    low[x]=dfn[x]=++ind;
    Stack[++top]=x;
    Vis[x]=true;
    for(int i=Link_First[x];i;i=a[i].Next)
    {
        int y=a[i].Point;
        if(!dfn[y])
        {
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(Vis[y])
        low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        tot++;//找到一个联通分量缩成一个点
        while(This!=x)
        {
            This=Stack[top--];
            Vis[This]=false;
            Belong[This]=tot;
            Avalue[tot]+=Value[This];
            Aweight[tot]+=Weight[This];
        }
    }
}
void Rebuild()//重新建为二叉树
{
    int Cut=0;
    for(int x=1;x<=n;x++)
    for(int i=Link_First[x];i;i=a[i].Next)
    if(Belong[a[i].Point]!=Belong[x])
    {
        This=a[i].Point;
        Get[Belong[This]]=true;
        Brother[Belong[This]]=Child[Belong[x]];
        Child[Belong[x]]=Belong[This];
    }
}
int DFS(int x,int dis)
{
    if(dis<=0||x<0) return 0;
    if(Find[x][dis]==true) return f[x][dis];
    Find[x][dis]=true;
    for(int i=0;i<=dis-Aweight[x];i++)//如果装x
    {
        int First=DFS(Child[x],i)+Avalue[x];
        int Second=DFS(Brother[x],dis-i-Aweight[x]);
        f[x][dis]=max(f[x][dis],First+Second);
    }
    f[x][dis]=max(f[x][dis],DFS(Brother[x],dis));//不装x
    return f[x][dis];
}
int main()
{
    ios::sync_with_stdio(false);
    memset(Find,false,sizeof(Find));
    memset(Brother,-1,sizeof(Brother));
    memset(Child,-1,sizeof(Child));
    memset(Vis,false,sizeof(Vis));
    memset(Get,false,sizeof(Get));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>Weight[i];
    for(int i=1;i<=n;i++)
    cin>>Value[i];
    for(int i=1;i<=n;i++)
    {
        cin>>Father;
        a[i].Point=i;
        a[i].Next=Link_First[Father];
        Link_First[Father]=i;
    }
    for(int i=0;i<=n;i++)
    if(!dfn[i]) Tarjan(i);//使用Tarjan算法缩点
    Rebuild();
    for(int i=1;i<=tot;i++)
    if(Get[i]==false)//将形成环的点归为没有约束的点
    {
        Get[i]=true;
        Brother[i]=Child[0];
        Child[0]=i;
    }
    cout<<DFS(0,m)<<endl;
    return 0;
}