9/5 二维费用背包+基环树+01变型背包

二维费用背包

int n,V,M,v[N],w[N],val[N],f[N][N];

void solve()
{
    cin>>n>>V>>M;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i]>>val[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=v[i];j--)
        {
            for(int k=M;k>=w[i];k--)
                f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+val[i]);
        }
    }
    cout<<f[V][M]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

基环树

定义：基环树可看作是比树多了一条边，从而形成一个环。基环树可看作是以环点为根的一颗颗子树构成。
思路：
1.深搜找环。
2.断环成树，对树深搜计算。
断边技巧：标记端点或标记边
预备知识：树形dp

P2607 [ZJOI2008] 骑士

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e6+5;;
const int inf=1e18;
const int mod=19980829;
int n,cnt,head[N],f[N][2],a[N],r1,r2,sum;
bool vis[N];
struct node
{
    int to,nxt,w;
}e[N];
void add(int from,int to)
{
    e[++cnt].to=to;
    //e[cnt].w=w;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
void fd(int u,int rt)
{
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==rt)
        {
            r1=u,r2=v;return;
        }
        if(vis[v]) continue;
        fd(v,rt);
    }
}
int dfs(int u,int rt)
{
    f[u][0]=0,f[u][1]=a[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==rt) continue;
        dfs(v,rt);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
    }
    return f[u][0];
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int u;cin>>a[i]>>u;
        add(u,i); //一个人可被多个人讨厌
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            r1=r2=0;
            fd(i,i);
            if(r1)
                sum+=max(dfs(r1,r1),dfs(r2,r2));
        }
    }
    cout<<sum<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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

P1453 城市环路

基环树+树形dp(类似没有上司的舞会)
本题只存在一个基环树，而骑士那题可能存在基环树森林

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=2e5+5;;
const int inf=1e18;
const int mod=19980829;
int n,cnt,head[N],f[N][2],a[N],r1,r2,ans,flag;
double k;
bool vis[N];
struct node
{
    int to,nxt,w;
}e[N];
void add(int from,int to)
{
    e[++cnt].to=to;
    //e[cnt].w=w;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
int dfs(int u,int pre,int rt)
{
    f[u][0]=0,f[u][1]=a[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==pre||v==rt) continue;
        dfs(v,u,rt);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
    }
    return f[u][0];
}
void fd(int u,int pre)
{
    if(flag) return;
    if(!vis[u]) vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==pre) continue;
        if(!vis[v]) fd(v,u);
        else
        {
            flag=1;
            int mx1=dfs(u,v,u);
            int mx2=dfs(v,u,v);
            ans=max(mx1,mx2);
        }
    }
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int u,v;cin>>u>>v;
        u++,v++;
        add(u,v),add(v,u);
    }
    cin>>k;
    fd(1,1);
    double sum=ans*k;
    printf("%.1lf\n",sum);
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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

另一个写法，大同小异：

void fd(int u,int pre)
{
    if(flag)
        return;
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==pre) continue;
        if(vis[v])
        {
            flag=1;
            r1=u,r2=v;return;
        }
        fd(v,u);
    }
}
int dfs(int u,int pre,int rt)
{
    f[u][0]=0,f[u][1]=a[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==pre||v==rt) continue;
        dfs(v,u,rt);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
    }
    return f[u][0];
}
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

P1417 烹调方案

化简公式，对食物进行排序。由于美味值会衰减，因此并非越靠后要好，所以要对所有f[1~t]进行枚举取最大值。

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=2e5+5;;
const int inf=1e18;
const int mod=19980829;
int t,n,f[N],ans;
struct node
{
    int a,b,c;
}e[N];
bool cmp(node x,node y)
{
    return x.b*y.c>y.b*x.c;
}
void solve()
{
    cin>>t>>n;
    for(int i=1;i<=n;i++) cin>>e[i].a;
    for(int i=1;i<=n;i++) cin>>e[i].b;
    for(int i=1;i<=n;i++) cin>>e[i].c;
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=t;j>=e[i].c;j--)
            f[j]=max(f[j],f[j-e[i].c]+e[i].a-j*e[i].b);
    }
    for(int i=1;i<=t;i++)
        ans=max(ans,f[i]);
    cout<<ans<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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