Problem B. Cards Game Google Kickstart Round G 2017

題意：有一組卡片，正反面的值是R[i],B[i]，每次選擇兩個卡片i,j把min(R[i]^B[j],B[i]^R[j])加到value中，再将其中一個卡片放回，直到隻剩一張卡片。問最優政策下最小的value是多少。

small input可以用dp，狀态用二進制數表示，比如N=5,10101表示餘下第0,2,4個卡片，狀态轉移時枚舉選取其中兩個卡片，再放回去一個。

large input真心想不到最小生成樹上面去。切入點是假設最優解中的操作次序是選擇卡片a,b,移除卡片b，那麼說明a把b移除了，接下來選擇卡片a,c,移除卡片a，a又被c移除，不可能出現的情況就是同時選了b,c，b把c移除或者c把b移除。Then 如果卡片之間連一條邊，最優解中不可能出現環。是以就是個求最小生成樹的問題。

卡片i,j之間連一條無向邊，weight=min(R[i]^B[j],B[i]^R[j])。再求最小生成樹即可。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<string>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<windows.h>
using namespace std;

//Kcikstart 2017 Round D Problem B. Cards Game
const int maxn=110;
int T;
int N;
long long R[maxn];
long long B[maxn];
long long mp[maxn][maxn];
int p[maxn*maxn];// disjoint-sets forest
int E;
long long ans;
class edge
{
public:
    int a;
    int b;
    long long weight;
    edge()
    {
        a=0;
        b=0;
        weight=0;
    }
    edge(int a0,int b0,long long w0)
    {
        a=a0;
        b=b0;
        weight=w0;
    }
    bool operator < (edge other) const
    {
        return weight<other.weight;
    }
    bool operator > (edge other) const
    {
        return weight>other.weight;
    }
    bool operator == (edge other) const
    {
        return weight==other.weight;
    }
};
edge edge_set[maxn*maxn];

int init()
{
    for (int i=0;i<maxn*maxn;++i)
    {
        p[i]=i;
    }
}
int find(int x)
{
    if(x==p[x])
    {
        return x;
    }
    else
    {
        return p[x]=find(p[x]);
    }
}
void Union(int x,int y)
{
    p[find(x)]=find(y);
}

void Kruskal()
{
    init();
    sort(edge_set, edge_set+E);
//    for(int i=0;i<E;i++)
//    {
//        cout<<edge_set[i].a<<" "<<edge_set[i].b<<" "<<edge_set[i].weight<<endl;
//    }
    int j=0;
    while(j<E)
    {
        while(find(edge_set[j].a)==find(edge_set[j].b))
        {
//            cout<<edge_set[j].a<<" "<<edge_set[j].b<<" "<<p[edge_set[j].a]<<" "<<p[edge_set[j].b]<<endl;
            j++;
            if(j>=E)
            {
                return;
            }
//            cout<<j<<endl;
        }
        Union(edge_set[j].a,edge_set[j].b);
//        cout<<"add edge "<<edge_set[j].a<<" "<<edge_set[j].b<<endl;
        ans+=edge_set[j].weight;
        j++;
    }
}
int main()
{
//    freopen("input.txt","r",stdin);

    freopen("B-small-practice.in","r",stdin);
    freopen("B.txt","w",stdout);
    cin>>T;

    for(int ca=1;ca<=T;ca++)
    {
        memset(R,0,sizeof(R));
        memset(B,0,sizeof(B));
        memset(mp,0,sizeof(mp));
        memset(p,0,sizeof(p));
        memset(edge_set,0,sizeof(edge_set));
        scanf("%d",&N);
        E=0;
        ans=0;
        for(int i=0;i<N;i++)
        {
            scanf("%lld",&R[i]);
        }
        for(int i=0;i<N;i++)
        {
            scanf("%lld",&B[i]);
        }
//        for(int i=0;i<N;i++)
//        {
//            cout<<R[i]<<" "<<B[i]<<endl;
//        }
        for(int i=0;i<N;i++)
        {
            for(int j=i+1;j<N;j++)
            {
                int weight=min(R[i]^B[j],R[j]^B[i]);
//                cout<<weight<<" "<<(R[i]^B[j])<<" "<<(R[j]^B[i])<<endl;
                mp[i][j]=weight;
                mp[j][i]=weight;
                edge_set[E++]=edge(i,j,weight);
            }
        }
//        for(int i=0;i<N;i++)
//        {
//            for(int j=0;j<N;j++)
//            {
//                cout<<mp[i][j]<<" ";
//            }
//            cout<<endl;
//        }
        Kruskal();
        printf("Case #%d: %lld\n",ca,ans);


    }
    return 0;
}
           

附dp code for small input

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<string>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<climits>
using namespace std;

//kickstart 2017 Round G Problem B
int T;
const int maxn=1<<6;
int N;
int M;
long long ans;
long long dp[maxn];
int used[maxn];
long long R[10];
long long B[10];
long long dfs(int state)
{
    //cout<<"state "<<bitset<5>(state)<<endl;
    if(used[state]==true)
    {
        return dp[state];
    }
    int cardnum=0;
    int cardidx[N];
    memset(cardidx,0,sizeof(cardidx));
    for(int i=0;i<N;i++)
    {
        //cout<<"check "<<bitset<5>((1<<i))<<" "<<((1<<i)&state)<<endl;
        if(((1<<i)&state)!=0)
        {
            cardnum++;
            cardidx[i]=1;
            //cout<<i<<endl;
        }
    }
    if(cardnum==1)
    {
        dp[state]=0;
        return 0;
    }
    int card1=0;
    int card2=0;
    long long minret=LLONG_MAX;
    //bool chg=false;
    for(int i=0;i<N;i++)
    {
        if(cardidx[i]==1)
        {
            card1=i;
            for(int j=i+1;j<N;j++)
            {
                if(cardidx[j]==1)
                {
                    card2=j;
                    long long curr=min(R[card1]^B[card2],R[card2]^B[card1]);
                    //cout<<curr<<" "<<minret<<" "<<(minret-curr)<<endl;
                    int nextstate=state^(1<<card1);
                    minret=min(minret,curr+dfs(nextstate));
                    nextstate=state^(1<<card2);
                    minret=min(minret,curr+dfs(nextstate));

                    //chg=true;
                }
            }
        }
    }
//    if(chg==false)
//    {
//        cout<<"unchanged "<<bitset<5>(state)<<endl;
//    }
    //cout<<bitset<5>(state)<<" "<<minret<<endl;
    dp[state]=minret;
    used[state]=true;
    return minret;
}
int main()
{
//    long long sminret=LLONG_MAX;
//    cout<<sminret<<endl;
    //cout<<(872031131^582064085)<<" "<<0x3f3f3f3f<<endl;
    freopen("B-small-attempt2.in","r",stdin);
    //freopen("input.txt","r",stdin);
    freopen("b1.txt","w",stdout);
    scanf("%d",&T);
    for(int ca=1;ca<=T;ca++)
    {
        ans=0;
        memset(R,0,sizeof(R));
        memset(B,0,sizeof(B));
        memset(dp,0,sizeof(dp));
        memset(used,false,sizeof(used));
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            dp[(1<<i)]=0;
            used[(1<<i)]=true;
            scanf("%lld",&R[i]);
        }
        for(int i=0;i<N;i++)
        {
            scanf("%lld",&B[i]);
        }
        //cout<<"init "<<((1<<N)-1)<<endl;
        ans=dfs((1<<N)-1);

        printf("Case #%d: %lld\n",ca,ans);

    }

    return 0;
}