1182. Team Them Up! 夜

http://acm.timus.ru/problem.aspx?space=1&num=1182

比较麻烦的一道题

先将不是相互知道的两个人重新建边 A知道B 但B不知道A 也需要建边（双向边）

新的图是m个连同块  对于每个连同块 用bfs将他们分成两组 组1 和组2 如果分的过程中出现矛盾 则无解

否则就会有m对  然后根据这m对 用DP的思想求最优解 既可

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<queue>
#include<stack>
#include <iomanip>
using namespace std;
#define LL long long
const int INF=0x3f3f3f3f;
//priority_queue<int,vector<int>,greater<int> >qt;
const int N=205;
bool know[N][N];
vector<int>graph1[N];
vector<int>graph2[N];
int choose[N][N];
int head[N],I;
struct node
{
    int j,next;
}side[N*N];
int in[N];
void add(int i,int j)
{
    side[I].j=j;
    side[I].next=head[i];
    head[i]=I++;
}
bool bfs(int s,int m)
{
    in[s]=1;
    graph1[m].push_back(s);
    queue<int>qt;
    qt.push(s);
    while(!qt.empty())
    {
        int x=qt.front();
        qt.pop();
        for(int t=head[x];t!=-1;t=side[t].next)
        {
            int j=side[t].j;
            if(in[j]==0)
            {
                if(in[x]==1)
                {in[j]=2;graph2[m].push_back(j);}
                if(in[x]==2)
                {in[j]=1;graph1[m].push_back(j);}
                qt.push(j);
            }else if(in[j]==in[x])
            {
                return false;
            }
        }
    }
    return true;
}
int main()
{
    //freopen("data.in","r",stdin);
    int n;
    while(cin>>n)
    {
        memset(know,false,sizeof(know));
        for(int i=1;i<=n;++i)
        {
            int j;
            while(cin>>j)
            {
                if(!j) break;
                know[i][j]=true;
            }
        }
        memset(head,-1,sizeof(head));
        I=0;
        for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        if(!know[i][j]||!know[j][i])
        {add(i,j);add(j,i);}
        memset(in,0,sizeof(in));
        for(int i=0;i<=n;++i)
        {graph1[i].clear();graph2[i].clear();}
        int flag=true;
        int m=0;
        for(int i=1;i<=n;++i)
        if(in[i]==0&&!bfs(i,m++))
        {flag=false;break;}
        if(flag==false)
        {cout<<"No solution"<<endl;continue;}
        memset(choose,0,sizeof(choose));
        stack<int>stx[2];
        stack<int>sty[2];
        stx[0].push(0);
        sty[0].push(0);
        int X,Y,x,y;
        for(int i=0;i<m;++i)
        {
            int l=i%2;
            int k=(i+1)%2;
            while(!stx[l].empty())
            {
                x=stx[l].top();stx[l].pop();
                y=sty[l].top();sty[l].pop();
                X=x+graph1[i].size();
                Y=y+graph2[i].size();
                if(choose[X][Y]==0)
                {choose[X][Y]=1;stx[k].push(X);sty[k].push(Y);}
                X=x+graph2[i].size();
                Y=y+graph1[i].size();
                if(choose[X][Y]==0)
                {choose[X][Y]=2;stx[k].push(X);sty[k].push(Y);}
            }
        }
        int MAX=INF;
        while(!stx[m%2].empty())
        {
            x=stx[m%2].top();stx[m%2].pop();
            y=sty[m%2].top();sty[m%2].pop();
            if(abs(x-y)<MAX)
            {
                MAX=abs(x-y);
                X=x;
                Y=y;
            }
        }
        vector<int>ans1;
        vector<int>ans2;
        while(X||Y)
        {
            --m;
            if(choose[X][Y]==1)
            {
                ans1.insert(ans1.end(),graph1[m].begin(),graph1[m].end());
                ans2.insert(ans2.end(),graph2[m].begin(),graph2[m].end());
                X=X-graph1[m].size();
                Y=Y-graph2[m].size();
            }else
            {
                ans2.insert(ans2.end(),graph1[m].begin(),graph1[m].end());
                ans1.insert(ans1.end(),graph2[m].begin(),graph2[m].end());
                X=X-graph2[m].size();
                Y=Y-graph1[m].size();
            }
        }
        cout<<ans1.size();
        for(unsigned int i=0;i<ans1.size();++i)
        cout<<" "<<ans1[i];
        cout<<endl;
        cout<<ans2.size();
        for(unsigned int i=0;i<ans2.size();++i)
        cout<<" "<<ans2[i];
        cout<<endl;
    }
    return 0;
}