/*
  先求补图Init()，再黑白染色Calc()，然后Dp()，最后Print()
*/
#include<iostream>
using namespace std;
#define maxn 105
#define Inf 1000000
int n,m,v[maxn],s[maxn][2],f[maxn][maxn],p[maxn][maxn];
bool g[maxn][maxn];

void Init() {
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        int j;
        while (scanf("%d",&j),j) g[i][j]=true;
    }
    for (int i=1; i<=n-1; i++)
        for (int j=i+1; j<=n; j++)
            g[i][j]=g[j][i]=!(g[i][j] && g[j][i]);
}

bool Dye(int i,int flag) {
    v[i]=(flag)?-m:m,s[m][flag]++;
    for (int j=1; j<=n; j++) if (g[i][j])
        if (v[i]==v[j] || !v[j] && !Dye(j,flag^1)) return false;
    return true;
}

bool Calc() {
    for (int i=1; i<=n; i++) if (!v[i]) {
        m++;
        if (!Dye(i,0)) return false;
    }
    return true;
}

void Dp() {
    fill_n(f[0],maxn*maxn,-Inf);
    for (int j=0; j<=n/2; j++) f[0][j]=0;
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n/2; j++)
            if (s[i][1]) {
                if (j>=s[i][0]) f[i][j]=f[i-1][j-s[i][0]]+s[i][0];
                if (j>=s[i][1] && f[i-1][j-s[i][1]]+s[i][1]>f[i][j]) {
                    f[i][j]=f[i-1][j-s[i][1]]+s[i][1];
                    p[i][j]=1;
                }
            } else {
                f[i][j]=f[i-1][j],p[i][j]=-1;
                if (j>=s[i][0] && f[i-1][j-s[i][0]]+s[i][0]>f[i][j]) {
                    f[i][j]=f[i-1][j-s[i][0]]+s[i][0];
                    p[i][j]=0;
                }
            }
}

bool ans[maxn];
int rec[maxn];
void Print() {
    int limit=n/2,now=m;
    while (now>0) {
        rec[now]=p[now][limit];                         //一开始打成p[limit][now] ， 郁闷了好半天
        if (rec[now]>-1) limit-=s[now][rec[now]];
        now--;
    }
    for (int i=1; i<=n; i++)
        if (v[i]>0 && rec[v[i]]==0) ans[i]=true;
        else if (v[i]<0 && rec[-v[i]]==1) ans[i]=true;
    printf("%d",f[m][n/2]);
    for (int i=1; i<=n; i++) if (ans[i]) printf(" %d",i); printf("\n");
    printf("%d",n-f[m][n/2]);
    for (int i=1; i<=n; i++) if (!ans[i]) printf(" %d",i); printf("\n");
}

int main() {
    Init();
    if (!Calc()) {
        puts("No solution");
        return 0;
    }
    Dp();
    Print();
    return 0;
}

• Re:xxxxxxxxxxxxxxx (2441) hookun 2008-09-27 18:01:30
• Re:xxxxxxxxxxxxxxx (2430) flatfish 2009-05-05 14:07:23
• Re:xxxxxxxxxxxxxxx (77) flatfish 2009-05-05 14:22:18