1128. Partition into Groups-白红宇

1128. Partition into Groups

阅读量：5140 次

发布时间：2019-06-13

本文共 1246 字，大约阅读时间需要 4 分钟。

思维才是最重要的有些题目用不到很复杂的算法甚至不用算法但就是让人很难想到

个人认为这才是一个人能力的关键还需要多加练习呀

此题：

首先此题肯定有解也就是说“NO SOLUTION”是骗人的

1.我们先把所以人放在一个组里

2.遍历一遍对于某个人如果同组中有两个或两个以上的敌人则将此人放到另一组

3.如果 2 中没有更新则结束否则重复步骤 2

时间复杂度接近 o(n^2)

可以接受

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 using namespace std;#define LL long longconst int INF=0x3f3f3f3f;const int N=10005;int head[N],I;struct node{ int j,next;}side[N*50];vector
                 
                  group1;vector
                  
                   group2;int in[N];queue
                   
                    qt;struct node1{ int out; int I;}mem[N];void add(int i,int j){ side[I].j=j; side[I].next=head[i]; head[i]=I++;}bool cmp(node1 x,node1 y){ return x.out
                    
                     =2) {in[i]=-in[i];log=true;} } } return log;}int main(){ //freopen("data.in","r",stdin); int n; while(cin>>n) { memset(head,-1,sizeof(head)); I=0; for(int i=1;i<=n;++i) { int m; cin>>m; while(m--) { int k; cin>>k; add(i,k); } } for(int i=1;i<=n;++i) in[i]=1; int k=1; while(F(k,n)) k=-k; group1.clear(); group2.clear(); for(int i=1;i<=n;++i) { if(in[i]==1) group1.push_back(i); else group2.push_back(i); } cout<
                     
                      <