62 条题解

  • 3
    @ 2017-08-17 00:08:46

    并查集+分组背包
    #include<bits/stdc++.h>
    using namespace std;
    #define xyf main

    int n,Wmax,k,root[1010],ans;
    vector<int>edges[1010];
    int dp[1010];
    struct node
    {
    int p,w;
    }robot[1010];
    inline int getRoot(int x)
    {
    return root[x]==x?x:root[x]=getRoot(root[x]);
    }
    inline bool sameRoot(int x,int y)
    {
    x=getRoot(x);
    y=getRoot(y);
    if(x==y)
    return 1;
    return 0;
    }
    inline void myunion(int x,int y)
    {
    if(sameRoot(x,y))
    return;
    x=getRoot(x);
    y=getRoot(y);
    root[x]=y;
    }
    int xyf()
    {
    ios::sync_with_stdio(false);
    cin>>n>>Wmax>>k;
    for(int i=1;i<=n;++i)
    {
    cin>>robot[i].p>>robot[i].w;
    root[i]=i;
    }
    for(int i=1;i<=k;++i)
    {
    int a,b;
    cin>>a>>b;
    myunion(a,b);
    }
    for(int i=1;i<=n;++i)edges[getRoot(i)].push_back(i);
    for(int i=1;i<=n;++i)
    for(int j=Wmax;j>=0;--j)
    for(int o=0;o<edges[i].size();++o)
    {
    int now=edges[i][o];
    if(j>=robot[now].w)
    dp[j]=max(dp[j],dp[j-robot[now].w]+robot[now].p);
    }
    cout<<dp[Wmax]<<endl;
    return 0;
    }
    题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题
    题题题题题题题题题题题题题题题题题题题题题题题题题题题题水水水水题题题题题
    题题题题题题题题题题题题题题题题题题题题题题题题水水水水水水水水水题题题题
    题题题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题
    题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题题题
    题题题题题题题题题题题水水水水题水水水水水水水水水水水题题题题题题题题题题
    题题题题题题题题水水水水水水水题水水水题题水水水水水题题题题题题题题题题题
    题题题水水水水水水水水水水水水题题题题题题水水水水题题题题题题题题题题题题
    题水水水水水水水水水水水水水水题题题题题题水水水水题题题题题题题题题题题题
    题水水水水水水水水水水水水题题题题题题题水水水水水水水水水水水题题题题题题
    题水水水水水水水水水水水水题题题题题题水水水水水水水水水水水水水水题题题题
    题题水水水水水水水水水水题题题题题水水水水水水题题题水水水水水水水题题题题
    题题题题题题题题水水水水题题题题题水水水水题题题题题题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水水题题水水题题题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水水题题水水水水题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水水题题水水水水题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水水题题水水水题题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水水题题水水水题题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题
    题题题题题题题题水水水水题题题题水水水题题水水水水题题水水水水水题题题题题
    题题水水题题题水水水水水题题题题水水水题题水水水题题题水水水水水题题题题题
    题题水水水水水水水水水水题题题题题水水题题水水题题题题水水水水水题题题题题
    题题题水水水水水水水水水题题题题题题题题水水水题题题题水水水水题题题题题题
    题题题题题水水水水水水水题题题题题题题题水水水题水水水水题题题题题题题题题
    题题题题题题水水水水水水题题题题题题题水水水水题题水水水水题题题题题题题题
    题题题题题题题题题水水水题题题题题题水水水水水题题题水水水水水水水题题题题
    题题题题题题题题题题题题题题题题水水水水水水题题题题题水水水水水水题题题题
    题题题题题题题题题题题题题题题水水水水水水题题题题题题水水水水水水水题题题
    题题题题题题题题题题题题题题水水水水水题题题题题题题题题水水水水水水题题题
    题题题题题题题题题题题题题水水水水水题题题题题题题题题题题水水水水题题题题
    题题题题题题题题题题题题水水水题题题题题题题题题题题题题题题水水水题题题题
    题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题

  • 2
    @ 2017-01-23 22:09:40
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int n,w,b,fa[1001],cn[1001],c[1001][1000],f[1001][10001],g=0;
    
    struct node1
    {
        int p,w;
    }a[1001];
    
    int find_fa(int x)
    {
        if (fa[x]==x)
            return x;
        else
        {
            fa[x]=find_fa(fa[x]);
            return fa[x];
        }
    }
    
    void union_fa(int x,int y)
    {
        fa[x]=find_fa(x);
        if (fa[x]!=find_fa(y))
            fa[find_fa(y)]=fa[x];
    }
    
    void p_c()
    {
        int cx[1001];
        memset(cx,0,sizeof(cx));
        memset(cn,0,sizeof(cn));
        for (int i=1;i<=n;i++)
            if (fa[i]==i||fa[i]==0)
            {
                g++;
                c[g][++cn[g]]=i;
                cx[i]=g;
            }
        for (int i=1;i<=n;i++)
            if (!(fa[i]==i||fa[i]==0))
            {
                int x=cx[find_fa(i)];
                c[x][++cn[x]]=i;
            }
    }
    
    int main()
    {
        scanf("%d%d%d",&n,&w,&b);
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].p,&a[i].w);
            fa[i]=i;
        }
        for (int i=1;i<=b;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            union_fa(x,y);
        }
        p_c();
        memset(f,0,sizeof(f));
        for (int i=1;i<=g;i++)
            for (int j=w;j>=0;j--)
                for (int k=1;k<=cn[i];k++)
                {
                    f[i][j]=max(f[i-1][j],f[i][j]);
                    if (j>=a[c[i][k]].w)
                        f[i][j]=max(f[i][j],f[i-1][j-a[c[i][k]].w]+a[c[i][k]].p);
                }
        printf("%d\n",f[g][w]);
    }
    
  • 0
    @ 2019-08-05 14:25:03

    并查集+物品合并

    #include <iostream>
    
    using namespace std;
    
    int n,mw,m;
    int fa[1000];
    int re[1000][1001]={0};
    int dp[1001]={0};
    
    int fi(int x)
    {
        if(fa[x]==x)
        {
            return x;
        }
        else
        {
            return fa[x]=fi(fa[x]);
        }
    }
    
    int main()
    {
        cin>>n>>mw>>m;
        int i,j,k,a,b,af,bf;
        for(i=0;i<n;i++)
        {
            cin>>a>>b;
            fa[i]=i;
            for(j=mw;j>=b;j--)
            {
                re[i][j]=re[i][j-b]+a;
            }
        }
        for(i=0;i<m;i++)
        {
            cin>>a>>b;
            a--;
            b--;
            af=fi(a);
            bf=fi(b);
            fa[bf]=af;
            for(j=mw;j>=0;j--)
            {
                re[af][j]=max(re[af][j],re[bf][j]);
            }
        }
        for(i=0;i<n;i++)
        {
            if(i==fi(i))
            {
                for(j=mw;j>=0;j--)
                {
                    for(k=0;k<=j;k++)
                    {
                        dp[j]=max(dp[j],dp[k]+re[i][j-k]);
                    }
                }
            }
        }
        cout<<dp[mw]<<endl;
        return 0;
    }
    
  • 0
    @ 2017-07-18 20:00:04

    看来要去补一补背包知识了。

    #include<algorithm>
    #include<iostream>
    #include<vector>
    using namespace std;
    struct DA {int p,w;} da[1010];
    int n,mxw,k;
    int fa[1010];
    int dp[1010];
    vector<int> eg[1010];
    int find(int p) {return fa[p]==p?p:fa[p]=find(fa[p]);}
    void uin (int pa,int pb) {int fpa=find(pa),fpb=find(pb);if (fpa==fpb) return;fa[fpa]=fpb;}
    int main () {
        
        ios::sync_with_stdio(false);
        cin>>n>>mxw>>k;
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=n;i++) cin>>da[i].p>>da[i].w;
        for(int i=1;i<=k;i++) {int a,b;cin>>a>>b,uin(a,b);}
        for(int i=1;i<=n;i++) eg[find(i)].push_back(i);
        int ans=0;
        for(int i=1;i<=n;i++) 
          for(int j=mxw;j>=0;j--) 
            for(int o=0;o<eg[i].size();o++) {
                int now=eg[i][o];
                if (j>=da[now].w) dp[j]=max(dp[j],dp[j-da[now].w]+da[now].p);
                ans=max(ans,dp[j]);
            }
        cout<<ans<<endl;  
        return 0;
        
    }
    

  • 0
    @ 2017-01-23 22:48:37

    分组(并查集)背包
    #include <bits/stdc++.h>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;

    typedef pair<int, int> PII;
    const int N = 1000 + 5;

    int n, w, k, pa[N], pos[N], dp[N][N];
    PII a[N];
    vector<int> zu[N];

    int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }

    int main() {
    scanf("%d%d%d", &n, &w, &k);
    for (int i = 1; i <= n; i++)
    scanf("%d%d", &a[i].first, &a[i].second);
    for (int i = 1; i <= n; i++) pa[i] = i;
    for (int i = 1; i <= k; i++) {
    int a, b; scanf("%d%d", &a, &b);
    pa[findset(a)] = findset(b);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    if (!pos[findset(i)]) {
    pos[findset(i)] = ++cnt;
    zu[cnt].push_back(i);
    } else zu[pos[findset(i)]].push_back(i);
    for (int i = 1; i <= cnt; i++)
    for (int j = w; j >= 0; j--) {
    dp[i][j] = dp[i - 1][j];
    for (int q = 0; q < zu[i].size(); q++) {
    if (j - a[zu[i][q]].second < 0) continue;
    dp[i][j] = max(dp[i][j], dp[i - 1][j - a[zu[i][q]].second] + a[zu[i][q]].first);
    }
    }
    printf("%d\n", dp[cnt][w]);
    return 0;
    }

  • 0
    @ 2016-10-22 10:26:27

    经过十几次的提交终于过了,之后的10几次都是错在并查集的合并上
    找到a,b的父亲ai,bi后应该是两个父亲节点合并:fa[ai]=bi;(或fa[ai]=b;)f而不是fa[a]=b;或者fa[a]=bi;
    前两个都可以,后两个是错误的
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int f[1001]={0},w[1001]={0},p[1001]={0},fa[1001]={0},n,Wmax,k,zu[1001][1001]={0};
    int find(int a)
    {
    if(fa[a]!=a) return fa[a]=find(fa[a]);
    else return a;
    }
    void merge(int a,int b)
    {
    int x=find(a),y=find(b);
    if(x!=y) fa[y]=x;
    }
    void scan()
    {
    int a,b,tem;
    scanf("%d%d%d",&n,&Wmax,&k);
    for(int i=1;i<=n;i++)
    {
    scanf("%d%d",&p[i],&w[i]);
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=k;i++)
    {
    scanf("%d%d",&a,&b);
    merge(a,b);
    }
    for(int i=1;i<=n;i++)
    {
    tem=find(i);
    zu[tem][ ++zu[tem][0] ]=i;
    }
    }
    void work()
    {
    for(int i=1;i<=n;i++)
    {
    if(zu[i][0]!=0)
    for(int j=Wmax;j>=0;j--)
    for(int q=1;q<=zu[i][0];q++)
    {
    int aa=zu[i][q];
    if(j>=w[aa]) f[j]=max(f[j],f[j-w[aa]]+p[aa]);
    }
    }
    printf("%d",f[Wmax]);
    }
    int main()
    {
    // freopen("x.in","r",stdin);
    scan();
    work();
    return 0;
    }

  • 0
    @ 2016-02-03 10:43:14

    少打了一个0,居然改了一上午。。。我也是醉了。
    并不会大神们的vector,自己编了个struct,道理是一样的吧。。。另外,背包九讲是好东西,分组背包一定要看
    不说了,心累,上代码
    #include<iostream>
    using namespace std;
    int bi[1007] = {0}, f[1007] = {0};//bi:找到祖先,f:背包
    int p[1007] = {0}, w[1007] = {0}, bom[1007][2] = {0};//价值,重量,爆炸
    int n, wmax, k;
    int count = 0, cnt[1007] = {0};
    struct g{int pi[1007], wi[1007], flag;} group[1007];
    int find(int x)
    {
    if(bi[x] == x)
    return x;
    else bi[x] = find(bi[x]);
    return bi[x];
    }

    int main()
    {
    cin >> n >> wmax >> k;
    for(int i = 1; i <= n; i++)
    cin >> p[i] >> w[i];
    for(int i = 1; i <= n; i++)
    bi[i] = i;
    for(int i = 1; i <= k; i++)
    {
    cin >> bom[i][0] >> bom[i][1];
    bi[find(bom[i][0])] = find(bom[i][1]);
    }
    for(int i = 1; i <= n; i++)
    {
    int x = 0;
    for(int j = 1; j <= count; j++)
    {
    if(find(i) == group[j].flag)
    {
    cnt[j]++;
    group[j].pi[cnt[j]] = p[i];
    group[j].wi[cnt[j]] = w[i];
    x++;
    break;
    }
    }
    if(x == 0)
    {
    count++;
    group[count].pi[1] = p[i], group[count].wi[1] = w[i], group[count].flag = find(i);
    cnt[count] = 1;
    }
    }
    for(int i = 1; i <= count; i++)
    for(int j = wmax; j >= 0; j--)
    for(int k = 1; k <= cnt[i]; k++)
    f[j] = j >= group[i].wi[k] ? max(f[j], f[j - group[i].wi[k]] + group[i].pi[k]) : f[j];
    cout << f[wmax];
    return 0;
    }

  • 0
    @ 2015-11-04 18:17:47

    写getf的时候写错了,容量为负数的时候是不存在,而非直接取容量为零,而且并查集总是会出现各种诡异的错误T_T
    #include <cstdio>
    #include <cstdlib>
    #include <vector>
    #include <algorithm>

    using namespace std;

    int n, wmax, k;
    int p[1005], w[1005];
    int father[1005];
    vector<int> q[1005];
    bool vis[1005];
    int f[2][10005];

    int max0(int a, int b, int c) {
    return max(a, max(b, c));
    }
    int getroot(int x) {
    return (father[x] == x ? x : father[x] = getroot(father[x]));
    }
    void merge(int x, int y) {
    if (getroot(x) != getroot(y))
    father[getroot(x)] = y;
    }
    int getf(int x, int y) {
    if (y < 0)
    return -2000000000;
    return f[x][y];
    }
    int main(int argc, const char *argv[]) {
    scanf("%d %d %d", &n, &wmax, &k);
    for (int i = 1; i <= n; ++i) {
    scanf("%d %d", &p[i], &w[i]);
    }
    int x, y;
    for (int i = 1; i <= n; ++i) father[i] = i;
    for (int i = 1; i <= k; ++i) {
    scanf("%d %d", &x, &y);
    merge(x, y);
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
    if (vis[i])
    continue;
    ++cnt;
    for (int j = i; j <= n; ++j) {
    if (vis[j]) continue;
    if (getroot(i) == getroot(j)) {
    vis[j] = true;
    q[cnt].push_back(j);
    }
    }
    }
    int now, prev;
    now = 1;
    prev = 0;
    for (int i = 1; i <= cnt; ++i) {
    int qsize = q[i].size();
    for (int j = 0; j < qsize; ++j) {
    for (int k = 0; k <= wmax; ++k) {
    f[now][k] = max0(f[now][k], f[prev][k], getf(prev, k - w[q[i][j]]) + p[q[i][j]]);
    }
    }
    swap(now, prev);
    }
    printf("%d\n", f[prev][wmax]);
    return 0;
    }

    • @ 2015-11-04 18:22:58

      刚才想明白了。我直接写的是father[x] = y;一想如果那么做,那么原先x的祖先就会被覆盖掉,所以是father[getroot(x)] = y;

  • 0
    @ 2015-11-04 10:18:38

    并查集秒写,然而分组背包......
    program p1250;
    var
    father,p,w,f:array[0..1200] of longint;
    a:array[1..1200,0..1200] of longint;
    n,wm,k,i,j,v,x,y,num,num1:longint;
    function fmax(x,y:longint):longint;
    begin
    if x>=y then
    exit(x)
    else exit(y);
    end;
    function getfather(x:longint):longint;
    begin
    if father[x]=x then
    exit(x)
    else begin
    father[x]:=getfather(father[x]);
    exit(father[x]);
    end;
    end;
    procedure merge(x,y:longint);
    var
    fa1,fa2:longint;
    begin
    fa1:=getfather(x);
    fa2:=getfather(y);
    father[fa1]:=fa2;
    end;
    function judge(x,y:longint):boolean;
    var
    fa1,fa2:longint;
    begin
    fa1:=getfather(x);
    fa2:=getfather(y);
    if fa1=fa2 then
    judge:=true
    else judge:=false;
    end;
    begin
    readln(n,wm,k);
    for i:=1 to n do
    readln(p[i],w[i]);
    for i:=1 to n do
    father[i]:=i;
    for i:=1 to k do
    begin
    readln(x,y);
    merge(x,y);
    end;
    num:=0;
    for i:=1 to n do
    if father[i]=i then
    begin
    inc(num);
    num1:=0;
    for j:=1 to n do
    begin
    if judge(i,j) then
    begin
    inc(num1);
    a[num,num1]:=j;
    end;
    end;
    a[num,0]:=num1;
    end;
    {for i:=1 to num do
    for j:=1 to a[i,0] do
    for v:=wm downto w[a[i,j]] do
    f[v]:=fmax(f[v],f[v-w[a[i,j]]]+p[a[i,j]]);}
    for i:=1 to num do
    for v:=wm downto 0 do
    for j:=1 to a[i,0] do
    if w[a[i,j]]<=v then
    f[v]:=fmax(f[v],f[v-w[a[i,j]]]+p[a[i,j]]);
    writeln(f[wm]);
    end.

  • 0
    @ 2015-04-24 14:34:50

    #include<cmath>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define sz 1010
    #define for1(v,a,b) for (int v=a;v<=b;v++)
    #define for2(v,a,b) for (int v=a;v>=b;v--)
    using namespace std;
    int n,num,maxn;
    int w[sz],f[sz],fa[sz],p[sz];
    vector<int>team[sz];
    int find(int x){
    int t,tt;
    t=x;
    while (fa[x]!=x)
    x=fa[x];
    while (fa[t]!=t){
    tt=fa[t];
    fa[t]=x;
    t=tt;
    }
    return x;
    }
    int main(){
    //freopen("p1.in","r",stdin);
    scanf("%d%d%d",&n,&maxn,&num);
    for1(i,1,n){
    scanf("%d%d",&p[i],&w[i]);
    fa[i]=i;
    }
    for1(i,1,num){
    int a,b;
    scanf("%d%d",&a,&b);
    a=find(a);
    b=find(b);
    if (a!=b) fa[a]=b;
    }
    for1(i,1,n){
    int x=find(i);
    team[x].push_back(i);
    }
    int cnt=0;
    for1(i,1,n)
    if (!team[i].empty()){
    for2(j,maxn,0)
    for (int k=0;k<team[i].size();k++){ //就这句,偷懒惹的祸。。。
    int pp=team[i][k];
    if (j>=w[pp])
    f[j]=max(f[j-w[pp]]+p[pp],f[j]);
    }
    }

    printf("%d\n",f[maxn]);
    return 0;
    }

  • 0
    @ 2014-08-28 20:26:54

    思路楼上的各位大神都说了,我就贴代码了

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <map>
    #include <queue>
    #include <cctype>
    #define MP(a, b) make_pair(a, b)
    using namespace std;
    const int MAXN = 1000 + 5;
    const int INF = 0x3f3f3f3f;
     
    struct EQP
    {
        int val, w;
    }eqp[MAXN];
     
    vector<int> ve[MAXN];
    int dp[MAXN][10000], pa[MAXN];
     
    int Find(int x)
    {
        return pa[x] == x ? x : pa[x] = Find(pa[x]);
    }
     
    int main()
    {
        //freopen("input.txt", "r", stdin);
        int n, wMax, k, i, j;
        scanf("%d%d%d", &n, &wMax, &k);
        for (i = 1; i <= n; i++)
            scanf("%d%d", &eqp[i].val, &eqp[i].w);
        for (i = 1; i <= n; i++)
            pa[i] = i;
        for (i = 0; i < k; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            int x = Find(a), y = Find(b);
            if (x != y)
                pa[x] = y;
        }
        for (i = 1; i <= n; i++)
        {
            int x = Find(i);
            ve[x].push_back(i);
        }
        int cnt = 0;
        for (i = 1; i <= n; i++)
        {
            if (!ve[i].empty())
            {
                cnt++;
                for (j = 0; j <= wMax; j++)
                {
                    dp[cnt][j] = dp[cnt - 1][j];
                    for (int k = 0; k < ve[i].size(); k++)
                        if (j >= eqp[ve[i][k]].w)
                            dp[cnt][j] = max(dp[cnt][j], dp[cnt - 1][j - eqp[ve[i][k]].w] + eqp[ve[i][k]].val);
                }
            }
        }
        printf("%d\n", dp[cnt][wMax]);
        return 0;
    }
    
  • 0
    @ 2014-08-04 17:56:11

    很明显的并查集+背包
    但是注意找同一个集合的元素时不能直接调用father数组(路径压缩后的也不行吧)
    要用getfather找到祖先
    贴个AC代码
    program vj;
    var n,w,tt,k,a,b,i,j,z,t1,t2:longint;
    f,p,ww,father,use,son:array[0..2000] of longint;
    num:array[0..2000,0..2000] of longint;

    function max(a,b:longint):longint;
    begin
    if a>b then exit(a) else exit(b);
    end;

    function getfather(k:longint):longint;
    var tip:longint;
    begin
    if father[k]=k then exit(k);
    tip:=father[k];
    father[k]:=getfather(tip);
    exit(father[k]);
    end;

    begin
    readln(n,w,k);
    for i:=1 to n do
    readln(p[i],ww[i]);
    for i:=1 to n do
    father[i]:=i;
    for i:=1 to k do
    begin
    readln(a,b);
    t1:=getfather(a);
    t2:=getfather(b);
    father[t1]:=t2;
    end;
    for i:=1 to n do
    begin
    use[i]:=getfather(i);
    inc(son[use[i]]);
    num[use[i],son[use[i]]]:=i;
    end;
    for i:=1 to n do
    if son[i]<>0 then
    for j:=w downto 1 do
    for z:=1 to son[i] do
    if j-ww[num[i,z]]>=0 then
    f[j]:=max(f[j],f[j-ww[num[i,z]]]+p[num[i,z]]);
    writeln(f[w]);
    end.

  • 0
    @ 2014-05-24 12:30:36

    试一试能不能发出去

  • 0
    @ 2014-01-16 18:00:20

    并查集+dp
    n^2搞定
    分析,首先并查集并集,然后就是dp
    dp思路如下
    f[i][j]表示前i个集合中,(也就是说把一个集合看做一个元素去更新f的值,当然可以这个集合中的一个也不上。一开始忘了这一点)花费为j可得的最大价值
    所以容易得到状态转移方程(这个自己推导)
    代码如下。
    #include<cstdlib>
    #include<cstdio>
    #include<cstring>
    #define N 1000
    #define P 1000
    int fa[N],v[N],c[N];
    int n,p,cmax;
    int f[2][P];
    int get_fa(int a)
    {
    if (a == fa[a]) return a; else return fa[a] = get_fa(fa[a]);
    }

    int max(int x,int y)
    {
    if (x > y) return x; else return y;
    }

    void swap_intp(int **a,int **b)
    {
    int *t;
    t = *a; *a = *b; *b = t;
    }

    void dp()
    {
    int cost,i,j,fa_v;
    int *f1,*f2;
    memset(f,0,sizeof(int)*2*P);
    //for (i = 0;i < cmax;i++) f[0][i] = f[1][i] = 0;
    f1 = f[0]; f2 = f[1];
    for (j = 0;j < n;j++) {
    if (fa[j] >= 0) fa_v = fa[j]; else continue;
    //memset(f2,0,sizeof(int)*P);注意我注释掉了这一行,第一次就是由于这一行出错
    for (i = 0;i < cmax;i++) *(f2+i) = *(f1+i); //这一行是第二次加上去得。因为可以这个集合中的一个也不选。若是没有。也就是说这个集合中的元素选了只有比之前的更差的份,如果不先把之前的状态copy回来。那么就会出现错误。例如前4个集合中花费1就可以最多得到100000,而如果不copy,可能就会算出这个集合的元素中所能获得的最优值是100,然后就错误的得出前5个集合花费1就可以最多得到100(这显然错误)
    for (i = 0;i < n;i++) {
    if (fa[i] != fa_v) continue; else fa[i] = -1;
    for (cost = 1;cost <= cmax;cost++)
    if (cost > c[i])
    (f2+cost-1) = max((f1+cost-c[i]-1)+v[i],*(f2+cost-1));
    else if (cost == c[i]) (f2+cost-1) = max(v[i],(f2+cost-1));
    }
    swap_intp(&f1,&f2);
    }
    for (i = 0,j = 0;i < cmax;i++) j = max(j,*(f1+i));
    printf("%d\n",j);
    printf("%d\n",*(f1+cmax-1));
    }
    int main()
    {
    void init();
    init(); dp();
    return 0;
    }

    void init()
    {
    int x,y;
    scanf("%d%d%d",&n,&cmax,&p);
    for (int i = 0;i < n;i++) {
    fa[i] = i; scanf("%d%d",v+i,c+i);
    }
    for (int i = 0;i < p;i++) {
    scanf("%d%d",&x,&y); fa[get_fa(x-1)] = get_fa(y-1);
    }
    for (int i = 0;i < n;i++) get_fa(i);
    }

  • 0
    @ 2013-05-03 19:44:02

    测试数据 #0: Accepted, time = 3 ms, mem = 4380 KiB, score = 10

    测试数据 #1: Accepted, time = 2 ms, mem = 4384 KiB, score = 10

    测试数据 #2: Accepted, time = 1 ms, mem = 4376 KiB, score = 10

    测试数据 #3: Accepted, time = 1 ms, mem = 4376 KiB, score = 10

    测试数据 #4: Accepted, time = 3 ms, mem = 4376 KiB, score = 10

    测试数据 #5: Accepted, time = 3 ms, mem = 4380 KiB, score = 10

    测试数据 #6: Accepted, time = 3 ms, mem = 4376 KiB, score = 10

    测试数据 #7: Accepted, time = 5 ms, mem = 4380 KiB, score = 10

    测试数据 #8: Accepted, time = 7 ms, mem = 4380 KiB, score = 10

    测试数据 #9: Accepted, time = 1 ms, mem = 4376 KiB, score = 10

    Accepted, time = 37 ms, mem = 4384 KiB, score = 100

    一个并查集加背包。。。
    #include <cstdio>
    #include <algorithm>

    using namespace std;

    #define MAXN 1001
    #define MAXW 1001

    int f[MAXW][2];
    int father[MAXN];

    int n,maxw,k;
    int w[MAXN],p[MAXN];
    int Kind[MAXN][MAXN];

    int Find(int x){
    int i=x;
    while (father[i]){
    i=father[i];
    }
    int j=x;
    while (father[j]){
    int k=father[j];
    father[j]=i;
    j=k;
    }
    return i;
    }

    void Insert(int x,int y){
    father[Find(x)]=Find(y);
    }

    int main(){
    scanf("%d %d %d",&n,&maxw,&k);
    for (int i=0;i++<n;){
    scanf("%d %d",&p[i],&w[i]);
    }
    for (int i=0;i++<n;){
    father[i]=0;
    }
    while (k--){
    int x,y;
    scanf("%d %d",&x,&y);
    if (Find(x)!=Find(y)){
    Insert(x,y);
    }
    }
    for (int i=0;i++<n;){
    Kind[i][0]=0;
    }
    for (int i=0;i++<n;){
    Kind[Find(i)][++Kind[Find(i)][0]]=i;
    }
    for (int i=0;i<=maxw;i++){
    f[i][0]=f[i][1]=0;
    }
    int z=0;
    for (int i=0;i++<n;){
    if (Kind[i][0]){
    for (int j=0;j<=maxw;j++){
    f[j][(k+1)%2]=f[j][k];
    }
    }
    for (int j=0;j++<Kind[i][0];){
    int x=Kind[i][j];
    for (int h=maxw;h>=w[x];h--){
    f[h][(k+1)%2]=max(f[h][(k+1)%2],f[h-w[x]][k]+p[x]);
    }
    }
    if (Kind[i][0]){
    k+=1;
    k%=2;
    }
    }
    printf("%d\n",f[maxw][k]);
    return 0;
    }

  • 0
    @ 2012-11-08 11:33:46

    #include

    #include

    #include

    #include

    using namespace std;

    int tmp,ans,n,wmax,k;

    int w[1001],p[1001],father[1001],f[1001];

    bool flag[1001];

    int save[1001][1001];

    int getfa(int i)

    {

    if (i==father[i])

    return i;

    father[i]=getfa(father[i]);

    return father[i];

    }

    int getmax(int i,int j)

    {

    if (i>j) return i; else return j;

    }

    int main()

    {

    ans=0;

    memset(flag,0,sizeof(flag));

    cin>>n>>wmax>>k;

    memset(f,0xff,sizeof(f));

    f[0]=0;

    for (int i=1;i>p[i]>>w[i];

    father[i]=i;

    }

    int a,b,lx,ly;

    for (int i=1;i>a>>b;

    lx=getfa(a);

    ly=getfa(b);

    if (lx != ly)

    father[lx]=ly;

    }

    for (int i=1;i

  • 0
    @ 2009-11-18 19:41:00

    并查集要这样写,否则会栈溢出(交3次栈溢出)

    function parent(nd:longint):longint;

    var f,x:longint;

    begin

    x:=nd;

    while true do

    begin

    if p[x]=x then

    begin

    p[nd]:=x;

    exit(x);

    end;

    x:=p[x];

    end;

    end;

  • 0
    @ 2009-11-11 20:21:47

    var t,n,z,m:integer;

    f:array[0..1000] of longint;

    a:array[1..1000,1..1000] of integer;

    p,w,l,b,h:array[1..1000] of integer;

    v:array[1..1000] of boolean;

    procedure ready;

    var i,j,x,y,x1,y1,q:integer;

    begin

    readln(n,z,m);

    for i:=1 to n do begin readln(p[i],w[i]); h[i]:=i; end;

    for i:=1 to m do

    begin

    readln(x,y);

    x1:=h[x]; y1:=h[y];

    if x1=0 then

    if f[j-w]+p>f[j] then f[j]:=f[j-w]+p;

    end;

    end;

    writeln(f[z]);

    end;

    begin

    ready;

    work;

    end.

  • 0
    @ 2009-11-09 19:20:11

    1 次AC

    背包问题 想清楚就好

  • 0
    @ 2009-11-09 19:08:54

    循环顺序的改变就可以处理不同的问题,牛!!

    0 to maxw 无限背包

    max downto 0 有限背包

    ///

    maxw downto 0

    1 to t

    分组

    1 to t

    maxw downto 0

    不分组

信息

ID
1250
难度
6
分类
动态规划 | 背包数据结构 | 并查集 点击显示
标签
递交数
2430
已通过
687
通过率
28%
被复制
3
上传者