Bribing FIPA

给出多棵有n个节点的有根树，第i个节点有一个权值\(a_i\)，定义一个点能控制的点为其所有的子节点和它自己，询问选出若干个点的最少的权值之和，并且能够控制大于等于m个点，\(1 ≤ n ≤ 200\)

解

此题卡输入，插点题外话

c++语法讲解：

c++11将gets()函数弃用了，而代以更加安全的fgets()，原因为gets的读入为一定要读完一行，而实际上可以读的数据是无限的，而电脑的内存空间是有限的，用无限的数据去填满有限的内存，那是自然会死机的，于是fgets加了一个限制，一定要按你给的字符数组大小读入，自然不支持string。
fgets(char数组名,sizeof(char数组名),stdin)
streamstring是为了方便读入而引入的，比较老的c++版本是不会支持的，但放心的是oi肯定支持（类似一个类型）
用法（建议运行试一试）

参考代码

#include <iostream>

#include <cstdio>

#include <sstream>

using namespace std;

int main(){

    char s[1000];

    stringstream a;//a为变量名

//读入7 afsfs 0.125

    fgets(s,sizeof(s),stdin);

    a.clear(),a.str(s);//清空a，用s来填充a

    int b;string c;double d;

    a>>b,a>>c,a>>d;

    cout<<b<<' '<<c<<' '<<d;

    return 0;

}

.clear()

清空状态标志，每次用完stringstream一定要清空，但未释放内存，可以做个小测试，打开内存显示，运行一下下面的程序，等待5s

#include <iostream>

#include <cstdio>

#include <sstream>

using namespace std;

int main(){

    register stringstream io;

    while(true)io<<"lsy akioi",io.clear();

    return 0;

}

.str()

用字符串s来重置stringstream,释放了内存

\(>>,<<\)分别表示输入到和输出到

废话完结

回到题目，显然是树形递推，因为是森林，故用一个超级根0连上所有树根，变为一棵树，肯定设两维\(f[i][j]\)表示以i为节点的子树中，控制了j个点的选择权值之和的最小值，显然有

\[f[i][j]=f[i][j-k]+f[l][k]
\]

其中l为i的一个子节点，k为其控制的点，也可以用分组背包来理解，i只不过代替不同的背包，j是容量，而子树就是每一组物品，k就是物品，只是压了子树这一维状态,设\(s[x]\)为x的子树中节点个数。

边界：\(f[x][0]=0,f[x][s[x]]=a_x,x=0,1,2,3,...,n\)特别地\(a_0=INT\_MAX\)。

参考代码：

#include <iostream>

#include <cstdio>

#include <map>

#include <cstring>

#include <sstream>

#define il inline

#define ri register

#define lsytql true

#define intmax 0x7fffffff

using namespace std;

struct point{

    int next,to;

}ar[401];

bool check[201];

int c[201],at,head[201],

    in[201],dp[201][201],

    st[201],mt,n,m;

char s[30000];

stringstream oi;

map<string,int>M;

void dfs(int);

il int min(int,int);

il void link(int,int);

int main(){

    while(true){

        mt&=0,M.clear(),memset(head,0,sizeof(head)),at&=0;

        memset(in,0,sizeof(in)),memset(check,0,sizeof(check));

        memset(dp,2,sizeof(dp)),memset(st,0,sizeof(st));

        fgets(s,sizeof(s),stdin),oi.clear(),oi.str(s),oi>>n>>m;

        if(s[0]=='#')break;for(int i(1),j;i<=n;++i){

            fgets(s,sizeof(s),stdin);

            oi.clear(),oi.str(s),oi>>s;

            if(M.find(s)==M.end())M[s]=++mt;

            j=M[s],oi>>c[j];

            while(oi>>s){

                if(M.find(s)==M.end())M[s]=++mt;

                link(j,M[s]),++in[M[s]];

            }

        }int ans(intmax);

        for(int i(1);i<=n;++i)if(!in[i])link(0,i);dfs(0);

        for(int i(m);i<=n;++i)if(dp[0][i]<ans)ans=dp[0][i];

        printf("%d\n",ans);

    }

    return 0;

}

il int min(int a,int b){

    return a<b?a:b;

}

void dfs(int x){

    check[x]|=true,dp[x][0]=0;

    for(int i(head[x]);i;i=ar[i].next)

        if(!check[ar[i].to]){

            dfs(ar[i].to),st[x]+=st[ar[i].to];

            for(int j(n),k;j>0;--j)

                for(k=1;k<=j;++k)

                    dp[x][j]=min(dp[x][j],dp[x][j-k]+dp[ar[i].to][k]);

        }++st[x],dp[x][st[x]]=min(dp[x][st[x]],c[x]);

}

il void link(int u,int v){

    ar[++at].to=v;

    ar[at].next=head[u],head[u]=at;

}

巴特西

Bribing FIPA

解

最新文章

热门文章