POJ 1112 Team them up

이번 학기 첫 블로그, 아아아, 죄송합니다.
이 문제는 비교적 복잡하다. 도론은 간단한 DP와 결합되었다.
직접 구할 방법이 없으니 역도를 찾아야만 생각을 찾을 수 있다!
문제 풀이 사고방식: 1.유방향도를 제시하고 무방향도를 구한 다음에 무방향도에 따라 역도를 구한다.DFS는 각 연결 컴포넌트를 구하고 각 연결 컴포넌트를 염색합니다.DP는 가장 좋은 상태를 구하고 경로의 상세한 과정을 기록한다. DP는 모든 상태를 구하기 위해 -------즉 k개의 연결분량을 나누기 전(당연히 첫 번째 연결분량부터 나누는 것)의 모든 가능한 상태를 구한다. 마지막 연결분량을 나누면 n명 중 나눌 수 있는 모든 상태이다!!즉 f[i][j]는 k개의 연결분량을 나누지 않았을 때의 모든 상태를 나타낸다!다음과 같다.if(f[i][j]==1 & & f[i+cnt[k][0]][j+cnt[k]]==0)f[i+cnt[k][0]][j+cnt[k]]]]]=1;if(f[i][j]==1 && f[i+cnt[k][1]][j+cnt[k][0]]==0) f[i+cnt[k][1]][j+cnt[k][0]]=1;더 중요한 것은pre[i][j] 구조체로 이전의 i, j를 기록해야 한다는 것이다.이전 상태부터 이 상태까지 기록합니다. i와 j에 무엇을 넣었습니까?즉, 어느 k의 어느 부분을 추가했는지 기록한다(0&1)!
 

#include <iostream>



using namespace std;



const int MAXN=101;



struct Record

{

	int i,j;

	int id,is;

}pre[MAXN][MAXN];



int map[MAXN][MAXN],n;

int dp[MAXN][MAXN];

int cnt[MAXN][2];

int dataPtr[MAXN][2],data[MAXN],next[MAXN],ind;

//int color[MAXN];

int flag[MAXN];





void addedge(int id,int is,int u)

{

	data[ind]=u;

	next[ind]=dataPtr[id][is];

	dataPtr[id][is]=ind;



	ind++;

}



bool DFS(int v,int id,int is)

{

	cnt[id][is]++;

	flag[v]=is;

	addedge(id,is,v);



	for(int u=1;u<=n;u++)

	{

		if(map[v][u])

		{

			if(flag[u]==-1)

			{

				if(DFS(u,id,!is))	return true;

			}		

			else if(flag[v]==flag[u])

				return true;

		}

	}

	

	return false;

}



void solve()

{



	int i , j , k , l , id ;

	cin>>n;



	//    

	memset(map,0,sizeof(map));

	for(i=1;i<=n;i++)

	{

		cin>>j;

	//	while(j) { map[i][j]=1; }	  ①

		while(j) { map[i][j]=1; cin>>j; }

	}



	for(i=1;i<=n;i++)

	{

		for(j=1;j<i;j++)

		{

			if(map[i][j]==1 && map[j][i]==1)

				map[i][j]=map[j][i]=0;

			else	map[i][j]=map[j][i]=1;

		}

	}

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



	///DFS         

	memset(flag,-1,sizeof(flag));

//	memset(cnt,0,sizeof(cnt));

//	memset(dp,0,sizeof(dp));

	memset(dataPtr,-1,sizeof(dataPtr)); ind=0;



	//  ②：id    

	

	id=0;

	for(i=1;i<=n;i++)

	{

		if(flag[i]==-1)

		{

			if(DFS(i,++id,0))

			{

				cout<<"No solution"<<endl;

				return ;

			}

		}

	}



	///DP         

	int num=0;	dp[0][0]=1;

	for(k=1;k<=id;k++)

	{

		for(i=0;i<=num;i++)

		{

			j=num-i;

			if(dp[i][j]==1)

			{

				int nexti,nextj;

				for(l=0;l<2;l++)

				{

					nexti=i+cnt[k][l];	nextj=j+cnt[k][!l];

					if(dp[nexti][nextj]==0)

					{

						dp[nexti][nextj]=1;

						pre[nexti][nextj].i=i;

						pre[nexti][nextj].j=j;

						pre[nexti][nextj].id=k;

						pre[nexti][nextj].is=l;

					}

				}

			}

		}

		num+=cnt[k][0]+cnt[k][1];

	}

	for(i=n/2,j=n-i; ;i--,j++)

	{

		if(dp[i][j])	

		{

			break;

		}

	}



	///    

	int ind[2]={0,0};

	cnt[0][0]=i;	cnt[0][1]=j;

	while(i || j)

	{

		int id=pre[i][j].id;

		int is=pre[i][j].is;

		for(int l=0;l<2;l++,is=!is)

		{

			for(int k=dataPtr[id][is];k!=-1;k=next[k])

			{

				cnt[++ind[l]][l]=data[k];

			}

		}

		int tmp=i;

		i=pre[i][j].i;	j=pre[tmp][j].j;

	}



	for(i=0;i<2;i++)

	{

		cout<<cnt[0][i];	

		for(j=1;j<=cnt[0][i];j++)

			cout<<" "<<cnt[j][i];

		cout<<endl;

	}

	

}







int main()

{

	freopen("input.txt","r",stdin);

	

	solve();



	return 0;

}