随笔-68  评论-10  文章-0  trackbacks-0
图论+DP.
题目要求:
1、把所有的人分成2组,每组至少有1人;
2、每组里的人两两认识。
3、两个组的成员应尽量接近。
       我们先构图,如果存在两个人A和B,A不认识B,或B不认识A,那么A和B一定不能分在同一组。因此,我们以人为结点重新构造一个图G。假如A和B不能分在同一组,那么就在G中增加一条无向边(A,B)。 然后求极大连通分量。可以看到在这个图中的不同的连通分量中的两个人都是互相认识的!接下来很关键,那些互不认识的人就在一个连通分量里面。 
      在遍历求连通分量的时候,同时对连通分量中的点染色(01),如果一个点颜色为0,那么所有和它相邻的点与它的颜色应该不同(标记为1)。这是因为图中相邻的两个人都是不认识的。这样遍历结束后,就可以根据颜色把连通分量中的点分成两个组s0s1,在不同两个组的人是不可能分到一个team内的。到这里要做一个特判,对于s0s1组里的任意两个人p,q如果图中存在一条边(p,q),说明无解,输出"No solution"
      求出了所有的连通分量,对于第i个连通分量都把其节点分为两个组si1si2。这时要做的就是把所有的si1si2分配到team1team2中去,使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]!=0continue;    

        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]==0continue;
                
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 阅读(178) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理