1011 - MARRIAGE CEREMONIES (Lightoj)

During solving this problem i was feeling like a "match maker" ha ha ha .....    :)

I'm sharing my idea.

Here each groom  may be matched with one bride from the the set of  brides & vice versa..

So i need a state to refer to groom & another state to refer to bride that who are married or not.

Bitmask Function will look like below------

int bitmask(int groom,int mask)

Here i've propagated groom and for a specific groom corresponding mask says which brides are available yet for marriage.

For your convenience my Source code is given below:



#include<bits//stdc++.h>
using namespace std;
int n;
int priority[20][20],dp[20][1<<15+2];

//--------------- check,set,reset funtion------------

int Set(int N,int pos)
{
    return N=N | (1<<pos);
}

bool check(int N,int pos)
{
    return (bool) (N & (1<<pos));
}

//---------------bitmask function-------------------

int bitmask(int groom,int mask)
{
    //------------base case
    if(groom>=n)    return 0;

    //------------stop repeatation
    if(dp[groom][mask]!=-1)    return dp[groom][mask];

    //--------------
    int mx=0;
    for(int i=0;i<n;i++)
    {
        if(check(mask,i)==0)        //if this element not married before
        {
           int ans=priority[groom][i]+bitmask(groom+1,Set(mask,i));

           mx=max(mx,ans);
        }
    }
    return dp[groom][mask]=mx;
}

//------------------main function-----------------------

int main()
{
    int T;
    scanf("%d",&T);
    for(int tt=1;tt<=T;tt++)
    {
        memset(dp,-1,sizeof(dp));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%d",&priority[i][j]);
            }
        }
        int ans=bitmask(0,0);
        printf("Case %d: %d\n",tt,ans);
    }
    return 0;
}