图论+DP.
题目要求：
1、把所有的人分成2组，每组至少有1人；
2、每组里的人两两认识。
3、两个组的成员应尽量接近。
我们先构图，如果存在两个人A和B，A不认识B，或B不认识A，那么A和B一定不能分在同一组。因此，我们以人为结点重新构造一个图G。假如A和B不能分在同一组，那么就在G中增加一条无向边(A,B)。
然后求极大连通分量。可以看到在这个图中的不同的连通分量中的两个人都是互相认识的！接下来很关键，那些互不认识的人就在一个连通分量里面。
在遍历求连通分量的时候，同时对连通分量中的点染色（0或1），如果一个点颜色为0，那么所有和它相邻的点与它的颜色应该不同（标记为1）。这是因为图中相邻的两个人都是不认识的。这样遍历结束后，就可以根据颜色把连通分量中的点分成两个组s0和s1，在不同两个组的人是不可能分到一个team内的。到这里要做一个特判，对于s0或s1组里的任意两个人p,q如果图中存在一条边(p,q)，说明无解，输出"No solution"。
求出了所有的连通分量，对于第i个连通分量都把其节点分为两个组si1和si2。这时要做的就是把所有的si1和si2分配到team1和team2中去，使team1的总和与team2的总和差值最小。就可以用DP了。
f[i][j]表示前i个连同分量,team1的人数恰为j时的状态(true or false)，true 表示该状态存在，false表示不存在。
状态转移方程：f[i][j]=f[i-1][j-si1] || f[i-1][j-si2].
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef struct
{
int fst,sec;
vector<int> v1,v2;
}Group;
Group s[105];
int map[105][105];
int vis[105];
int path[105][105];
bool f[105][105];
int n,pt;
void input()
{
int i,j,t;
scanf("%d",&n);
memset(map,0,sizeof(map));
for(i=1;i<=n;i++)
{
bool mark[105]={0};
while(scanf("%d",&t)!=EOF&&t)
mark[t]=true;
for(j=1;j<=n;j++)
if(i!=j&&!mark[j])
{
map[i][j]=1;
map[j][i]=1;
}
}
}
bool Init()
{
int i,j;
pt=0;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
{
if(vis[i]!=0) continue;
queue<int> q;
vis[i]=-1;
q.push(i);
s[++pt].fst=1;
s[pt].sec=0;
(s[pt].v1).push_back(i);
while(!q.empty())
{
int temp=q.front();
q.pop();
for(j=1;j<=n;j++)
if(j!=temp&&map[temp][j])
{
if(vis[j]+vis[temp]==0) continue;
else if(vis[temp]==vis[j]) return false;
else if(!vis[j])
{
vis[j]=-vis[temp];
if(vis[j]==-1)
{
s[pt].fst++;
(s[pt].v1).push_back(j);
}
else if(vis[j]==1)
{
s[pt].sec++;
(s[pt].v2).push_back(j);
}
q.push(j);
}
}
}
}
return true;
}
void dp()
{
int i,j;
memset(path,-1,sizeof(path));
memset(f,false,sizeof(f));
f[0][0]=true;
for(i=1;i<=pt;i++)
for(j=0;j<=n;j++)
{
if(j-s[i].fst>=0&&f[i-1][j-s[i].fst])
{
f[i][j]=true;
path[i][j]=0;
continue;
}
if(j-s[i].sec>=0&&f[i-1][j-s[i].sec])
{
f[i][j]=true;
path[i][j]=1;
}
}
}
void output()
{
int i,j;
int k=n/2,num;
for(i=0;i<=k;i++)
{
if(f[pt][k+i])
{
num=k+i;
break;
}
else if(f[pt][k-i])
{
num=k-i;
break;
}
}
int cur=num;
bool flag[105]={0};
printf("%d",num);
i=path[pt][num];
while(i!=-1)
{
int ss;
if(i==0)
{
cur-=s[pt].fst;
for(j=0;j<(s[pt].v1).size();j++)
{
ss=(s[pt].v1).at(j);
flag[ss]=true;
printf(" %d",ss);
}
}
else
{
cur-=s[pt].sec;
for(j=0;j<(s[pt].v2).size();j++)
{
ss=(s[pt].v2).at(j);
flag[ss]=true;
printf(" %d",ss);
}
}
pt--;
i=path[pt][cur];
}
printf("\n%d",n-num);
for(i=1;i<=n;i++)
if(!flag[i]) printf(" %d",i);
printf("\n");
}
int main()
{
input();
if(!Init())
printf("No solution\n");
else
{
dp();
output();
}
return 0;
}
posted on 2010-08-11 23:23
wuxu 阅读(162)
评论(0) 编辑 收藏 引用 所属分类:
动态规划