poj 1112 Team Them Up!（건 도+dp)

http://poj.org/problem?id=1112
Team Them Up!
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 6368
 
Accepted: 1706
 
Special Judge
Description
Your task is to divide a number of persons into two teams, in such a way, that: 
everyone belongs to one of the teams; 
every team has at least one member; 
every person in the team knows every other person in his team; 
teams are as close in their sizes as possible. 
This task may have many solutions. You are to find and output any solution, or to report that the solution does not exist.
Input
For simplicity, all persons are assigned a unique integer identifier from 1 to N. 
The first line in the input file contains a single integer number N (2 <= N <= 100) - the total number of persons to divide into teams, followed by N lines - one line per person in ascending order of their identifiers. Each line contains the list of distinct numbers Aij (1 <= Aij <= N, Aij != i) separated by spaces. The list represents identifiers of persons that ith person knows. The list is terminated by 0.
Output
If the solution to the problem does not exist, then write a single message "No solution" (without quotes) to the output file. Otherwise write a solution on two lines. On the first line of the output file write the number of persons in the first team, followed by the identifiers of persons in the first team, placing one space before each identifier. On the second line describe the second team in the same way. You may write teams and identifiers of persons in a team in any order.
Sample Input

5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0

Sample Output

3 1 3 5
2 2 4

Source
Northeastern Europe 2001
제목:N 명,N 명 을 두 조로 나 누 어 팀 내 사람들 이 서로 알 고 두 팀 의 인원 이 가능 한 한 접근 하도록 합 니 다.
팀 내 사람들 이 서로 알 아야 하 는데 사실은 한 팀 이다.그래서 구 단의 사고 로 그림 을 만 들 고 두 사람 이 서로 알 지 못 하면 한 쪽 을 만든다.분명히 만들어 진 그림 이 이분 도가 아니라면 틀림없이 풀 리 지 않 을 것 이다.자세히 분석 하면 2 분 그림 의 모든 연결 블록 에 대한 사람 은 2 분 그림 의 서로 다른 변 에 있 는 사람 은 반드시 한 그룹 에 두 어 서 는 안 된다.그래서 우 리 는 모든 연결 블록 이 2 분 그림 의 서로 다른 변 에 있 는 수의 수 를 구하 고 x 와 y 로 표시 합 니 다.그러면 모든 연결 블록 에 대응 하 는 x 와 y 값 이 있 습 니 다.그러면 우 리 는 dp 로 두 그룹의 인원 이 가장 얼마 에 가 까 운 지 구 할 수 있다.dp 과정 에서 경 로 를 기록 하면 프로젝트 를 출력 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<vector>
#define nn 110
#define inff 0x3fffffff
typedef long long LL;
using namespace std;
int n;
bool tu[nn][nn];
int vis[nn];
bool dp[nn][nn][nn];
int pre[nn][nn][nn];
struct node
{
    int en,next;
}E[2*nn*nn];
int p[nn],num,cnt;
bool ok;
vector<int>ve[nn][2];
vector<int>ans[2];
void init()
{
    ans[0].clear();
    ans[1].clear();
    memset(p,-1,sizeof(p));
    memset(pre,-1,sizeof(p));
    memset(dp,false,sizeof(dp));
    num=0;
    cnt=0;
    ok=true;
    memset(vis,-1,sizeof(vis));
    for(int i=0;i<=n;i++)
    {
        ve[i][0].clear();
        ve[i][1].clear();
    }
}
void add(int st,int en)
{
    E[num].en=en;
    E[num].next=p[st];
    p[st]=num++;

    E[num].en=st;
    E[num].next=p[en];
    p[en]=num++;
}
void dfs(int id,int co)
{
    if(!ok)
        return ;
    vis[id]=co;
    ve[cnt][co].push_back(id);
    int i,w;
    for(i=p[id];i+1;i=E[i].next)
    {
        w=E[i].en;
        if(vis[w]==-1)
            dfs(w,1-co);
        else if(vis[w]==co)
        {
            ok=false;
        }
        if(!ok)
            return ;
    }
}
int main()
{
    int i,x,j,g;
    while(scanf("%d",&n)!=EOF)
    {
        memset(tu,false,sizeof(tu));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&x);
            while(x)
            {
                tu[i][x]=true;
                scanf("%d",&x);
            }
        }
        init();
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                if(!tu[i][j]||!tu[j][i])
                {
                    add(i,j);
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            if(vis[i]==-1)
            {
                cnt++;
                dfs(i,0);
                if(!ok)
                    break;
            }
        }
        if(!ok)
        {
            puts("No solution");
            continue;
        }
        dp[0][0][0]=true;
        int i1,i2;
        for(i=1;i<=cnt;i++)
        {
            i1=ve[i][0].size();
            i2=ve[i][1].size();
            for(j=0;j<=n;j++)
            {
                for(g=0;g+j<=n;g++)
                {
                    if(j-i1>=0&&g-i2>=0)
                    {
                        if(dp[i-1][j-i1][g-i2])
                        {
                            dp[i][j][g]=true;
                            pre[i][j][g]=0;
                            continue;
                        }
                    }
                    if(j-i2>=0&&g-i1>=0)
                    {
                        if(dp[i-1][j-i2][g-i1])
                        {
                            dp[i][j][g]=true;
                            pre[i][j][g]=1;
                        }
                    }
                }
            }
        }
        for(i=n/2;i>=0;i--)
        {
            if(dp[cnt][i][n-i])
            {
                break;
            }
        }
        i1=i,i2=n-i;
        while(cnt)
        {
            if(pre[cnt][i1][i2]==0)
            {
                i1-=ve[cnt][0].size();
                i2-=ve[cnt][1].size();
                for(i=0;i<(int)ve[cnt][0].size();i++)
                {
                    ans[0].push_back(ve[cnt][0][i]);
                }
                for(i=0;i<(int)ve[cnt][1].size();i++)
                {
                    ans[1].push_back(ve[cnt][1][i]);
                }
                cnt--;
            }
            else
            {
                i1-=ve[cnt][1].size();
                i2-=ve[cnt][0].size();
                for(i=0;i<(int)ve[cnt][1].size();i++)
                {
                    ans[0].push_back(ve[cnt][1][i]);
                }
                for(i=0;i<(int)ve[cnt][0].size();i++)
                {
                    ans[1].push_back(ve[cnt][0][i]);
                }
                cnt--;
            }
        }
        printf("%d",(int)ans[0].size());
        for(i=0;i<(int)ans[0].size();i++)
        {
            printf(" %d",ans[0][i]);
        }
        puts("");
        printf("%d",(int)ans[1].size());
        for(i=0;i<(int)ans[1].size();i++)
        {
            printf(" %d",ans[1][i]);
        }
        puts("");
    }
    return 0;
}