Poj Solution 2400

http://poj.org/problem?id=2400

#include<iostream>
#include"string.h"
#include"stdio.h"
using namespace std;


#define valuetype int

#define null 0
const int size=20;


bool maxmatch(int n,int m,bool w[size][size],int *p,bool *setn,bool *setm)
{
    int p_n[size];
    int p_m[size];
    bool sign[size];
    int q[size],from[size],s,t;

    int i,j,link,now,h;
    

    for(i=0;i<n;i++)p_n[i]=-1;
    for(j=0;j<m;j++)p_m[j]=-1;

    for(i=0;i<n;i++)
    if(p_n[i]==-1)
    {
        for(j=0;j<m;j++)sign[j]=0;
                
        s=1;link=-1;

        from[0]=-1;
        q[0]=size-1;
        p_m[size-1]=i;
        
        for(t=0;t<s;t++)
        {
            now=q[t];
            for(j=0;j<m;j++)
            {
                if(w[p_m[now]][j]!=null&&sign[j]==0)
                {
                    sign[j]=1;
                    q[s]=j;
                    from[s++]=t;
                    
                    if(p_m[j]==-1)
                    {
                        link=s-1;
                        break;
                    }
                }
            }
            
            if(j<m)break;
        }

        if(t<s)
        {
            while(from[link]!=-1)
            {
                h=from[link];
                p_m[q[link]]=p_m[q[h]];
                
                p_n[p_m[q[h]]]=q[link];
                link=h;
            }

        }
        else
        {
            for(j=0;j<n;j++)setn[j]=0;
            
            for(j=0;j<m;j++)setm[j]=0;

            for(j=0;j<s;j++)
            {
                setn[p_m[q[j]]]=1;
                if(j)setm[q[j]]=1;
            }
    
            return 0;
        }
    }


    for(i=0;i<n;i++)
    {
        if(p)p[i]=p_n[i];
        
    }
    
    return 1;
}


valuetype maxvaluematch(int l,valuetype w[][size])
{
    valuetype x[size],y[size],af;
    bool edge[size][size],setn[size],setm[size];
    int i,j,p[size];
    
    for(i=0;i<l;i++)y[i]=0;

    for(i=0;i<l;i++)
    {
        x[i]=0;
        for(j=0;j<l;j++)
            if(w[i][j]>x[i])x[i]=w[i][j];
    }

    do
    {    
        for(i=0;i<l;i++)
        for(j=0;j<l;j++)
            if(w[i][j]==x[i]+y[j])edge[i][j]=1;
            else edge[i][j]=0;

        if(maxmatch(l,l,edge,p,setn,setm))
        {
            valuetype answer=0;
            for(i=0;i<l;i++)
                answer+=w[i][p[i]];
            
            return answer;
        }
        
        af=0;
        for(i=0;i<l;i++)
        {
            if(setn[i])
                for(j=0;j<l;j++)
                    if(!setm[j])
                    {
                        if(af==0||x[i]+y[j]-w[i][j]<af)af=x[i]+y[j]-w[i][j];
                    }
        }

        for(i=0;i<l;i++)if(setn[i])x[i]-=af;

        for(j=0;j<l;j++)if(setm[j])y[j]+=af;
    }while(1);

    return 0;
}

//////////////////////////////////////////////////////////////


int v;
int e[20][20],n,cas;
int p[20];

void del_copy(int a[20][20],int b[20][20],int c,int d,int sn)
{
    int i,j;
    
    for(i=0;i<c;i++)
    {
        for(j=0;j<d;j++)
            a[i][j]=b[i][j];
        for(j=d+1;j<sn;j++)
            a[i][j-1]=b[i][j];
    }
    
    for(i=c+1;i<sn;i++)
    {
        for(j=0;j<d;j++)
            a[i-1][j]=b[i][j];
        for(j=d+1;j<sn;j++)
            a[i-1][j-1]=b[i][j];
    }
}

void print()
{
    int sign[20],i,j,k;
    cas++;
    printf("Best Pairing %dn",cas);
    
    
    for(i=0;i<n;i++)
        sign[i]=1;
    
    for(i=0;i<n;i++)
    {
        for(j=0,k=0;j<n;j++)
        {
            if(sign[j])k++;
            if(k==p[i]+1)break;
        }
        
        printf("Supervisor %d with Employee %dn",i+1,j+1);
        sign[j]=0;
    }
}



void search(int b,int sn,int e0[20][20],int value)
{
    int temp,ee[20][20];
    if(sn==0)print();
    
    for(p[b]=0;p[b]<sn;p[b]++)
    {
        del_copy(ee,e0,0,p[b],sn);
        temp=value+maxvaluematch(sn-1,ee)+e0[0][p[b]];
        if(temp==v)
            search(b+1,sn-1,ee,value+e0[0][p[b]]);

    }
    return;
}



int main()
{
    int t,i,j,s,k;
    cin>>t;
//    freopen("txt.txt","w",stdout);
    for(k=0;k<t;k++)
    {
        cin>>n;
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            e[i][j]=0;

        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            cin>>s;
        //    e[i][s-1]+=-j;
            e[s-1][i]+=-j;
        }

        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            cin>>s;
        //    e[s-1][i]+=-j;
            e[i][s-1]+=-j;
        }

        v=maxvaluematch(n,e);
        
        
        printf("Data Set %d, Best average difference: %.6lfn",k+1,(double)-v/2/n);
        
        cas=0;
        search(0,n,e,0);
        printf("n");
    }
    return 0;
}