学步园

/*
 * poj1112 AC
 * DP 背包问题 与poj1636 prison rearrangement如出一辙。
 * 问题挺经典，重点在于构造模型。
 * 首先考虑将所有人分为互斥的若干部分，这便是背包问题中物品了。
 * 之后，要将每个"物品"分为放在A和放在B的两个部分，然后进行DP。
 *
 * I. 求补图，将表示两个人相互认识的边去除，连接所有互相不认识，
 *    或单方面认识的边。
 * II.对每个处于同一连通分量的人进行染色，同时将每一个联通分量
 *    构造成类似于二分图的形式，分为两个部分。
 *III.类似与poj1636的方式进行DP，每个“物品”分为两种放法，想象一
 *    下堆积木，得到最小的差值，记录下选择的路径。
 *
 * 注意:不要MLE了，使用char来替代short。
 *
 * */
#include<cstdio>
#include<algorithm>
#include<memory.h>
using namespace std;

int n,tot;
bool map[105][105],flag,dp[105][105][105];
int node[10005],next[10005],head[105];
short a[105][2],label[105]; 
char pre[105][105][105][4],rec[105][105][105],fir[105],sec[105],col[105];

void addnode(int x,int y)
{
    node[++tot] = y,next[tot] = head[x],head[x] = tot;
}

//void dfs(int x,int team)
void dfs(char x,int team)
{
    a[tot][team]++,rec[tot][team][a[tot][team]] = x,label[(int)x] = tot,col[(int)x] = team;
    int i;
    for(i=head[(int)x];i;i=next[i])
    {
        if(label[node[i]]==0)
        {
            dfs(node[i],1-team);
            if(!flag) return;
        }else if(label[node[i]]==label[(int)x] && col[node[i]]==col[(int)x])
        {
            flag = false;
            return;
        }
    }
    return;
}

int main()
{
    scanf("%d",&n);
//    FILE* fin = fopen("d.in","r");
//    fscanf(fin,"%d",&n);
    int i,j,k;
    memset(map,false,sizeof(map));
    for(i=1;i<=n;i++)
    {
        while(scanf("%d",&j) && j)
//        while(fscanf(fin,"%d",&j) && j)
            map[i][j] = true;
    }
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
        {
            if(map[i][j] && map[j][i])
                map[i][j] = map[j][i] = false;
            else 
                map[i][j] = map[j][i] = true;
        }
    
    memset(head,0,sizeof(head));
    memset(next,0,sizeof(next));
    memset(node,0,sizeof(node));
    for(tot=0,i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j && map[i][j])
                addnode(i,j);

    memset(col,0,sizeof(col));
    memset(label,0,sizeof(label));
    for(tot=0,flag=true,i=1;i<=n;i++)
        if(label[i]==0) 
        {
            tot++;
            dfs(i,0);
            if(!flag) break;
        }

    if(!flag)
        printf("No solution\n");
    else 
    {
        memset(pre,0,sizeof(pre));
        memset(dp,false,sizeof(dp));
        dp[0][0][0] = true;
        for(i=1;i<=tot;i++)
            for(j=n;j>=0;j--)
                for(k=n;k>=0;k--)
                {
                    if(j-a[i][0]>=0 && k-a[i][1]>=0)
                    {
                        if(dp[i-1][j-a[i][0]][k-a[i][1]])
                        {
                            dp[i][j][k] = true;
                            pre[i][j][k][0] = j-a[i][0];
                            pre[i][j][k][1] = k-a[i][1];
                            pre[i][j][k][2] = 0;
                        }
                    }
                    if(j-a[i][1]>=0 && k-a[i][0]>=0)
                    {
                        if(dp[i-1][j-a[i][1]][k-a[i][0]])
                        {
                            dp[i][j][k] = true;
                            pre[i][j][k][0] = j-a[i][1];
                            pre[i][j][k][1] = k-a[i][0];
                            pre[i][j][k][2] = 1;
                        }
                    }
                }

        int num1,num2,min = 0xffff; 
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(dp[tot][i][j] && abs(i-j)<min)
                    num1 = i,num2 = j,min = abs(i-j);

        int tot1,tot2;
        for(tot1=tot2=0,i=tot;i>0;i--)
        {
            if(pre[i][num1][num2][2]==0)
            {
                for(j=1;j<=a[i][0];j++)
                    fir[++tot1] = rec[i][0][j];
                for(j=1;j<=a[i][1];j++)
                    sec[++tot2] = rec[i][1][j];
            }else if(pre[i][num1][num2][2]==1)
            {
                for(j=1;j<=a[i][1];j++)
                    fir[++tot1] = rec[i][1][j];
                for(j=1;j<=a[i][0];j++)
                    sec[++tot2] = rec[i][0][j];
            }
            int t = num1;
            num1 = pre[i][num1][num2][0];
            num2 = pre[i][t][num2][1];
        }

        sort(fir+1,fir+tot1+1);
        sort(sec+1,sec+tot2+1);
        printf("%d ",tot1);
        for(i=1;i<=tot1;i++)
            printf("%d ",fir[i]);
        printf("\n%d ",tot2);
        for(i=1;i<=tot2;i++)
            printf("%d ",sec[i]);
        printf("\n");
    }
    return 0;
}