ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1182. Team Them Up!

Idea
Posted by Marko Tintor (marko@pkj.co.yu) 4 Jul 2002 17:58
My idea, but it got Time Limit.

1) construct a opposite of input graph
2) convert all one-way to two-way edges
3) color vertices with two black and white such that every edge
      have one side in black and other in white
4) for every isolated component in graph find difference
      beetwen black and white vertices and save it in array d
5) put sings '+' and '-' beetwen values of array d
      such that absolute sum iz minimized (eg. |+2+3-5|=0)
6) for every component sign means to which team black vertices belong

----------------------------------------------

#include <fstream.h>
class item
{
public:
    short v;
    item *next;
    item(short V, item *N): v(V), next(N) {}
    ~item() {if(next) delete next;}
};

ifstream fin("teams.dat");
static char e[100][100];
static short team[100], color[100];
static short delta[100], d, total[3], t;
short bit[100], bbit[100], b=32000;
static item *list[100];
int n,fr=0,bi=1,z[2];

void dfs(int x)
{
    z[color[x]&1]++;
    for(item *p=list[x]; p; p=p->next)
        if(!color[p->v])
        {
            color[p->v]=color[x]^1;
            dfs(p->v);
        }
        else
            if(color[p->v]==color[x]) {bi=0;return;}
}

void comb(int x)
{
    if(x==d)
    {
        if(t<0) t=-t;
        if(t<b)
        {
            b=t;
            for(int i=0; i<d; i++) bbit[i]=bit[i];
        }
        return;
    }

    bit[x]=1;
    t+=delta[x];
    comb(x+1);
    t-=delta[x];

    bit[x]=0;
    t-=delta[x];
    comb(x+1);
    t+=delta[x];
}

void solve()
{
    int i,j;
    for(i=0; i<n; i++) for(j=0; j<n; j++) if(j!=i)
        if(!e[i][j] || !e[j][i])
            list[i] = new item(j,list[i]);

    short c=0;
    for(i=0; bi && i<n; i++) if(!color[i])
        if(list[i])
        {
            c+=2; color[i]=c;
            z[0]=z[1]=0;
            dfs(i);
            delta[d++]=z[0]-z[1];
        }
        else
            color[i]=1;

    for(i=0; i<n; i++) if(list[i]) delete list[i];

    if(bi)
    {
        if(d)
        {
            comb(0);
            for(i=0; i<d; i++)
                for(j=0; j<n; j++)
                    if(color[j]==(i+i+2))
                        team[j]=(bbit[i]?1:2);
                    else if(color[j]==(i+i+3))
                        team[j]=(bbit[i]?2:1);
            for(i=0; i<n; i++)
                if(team[i]==1) total[1]++;
                else if(team[i]==2) total[2]++;
        }
        for(i=0; i<n; i++) if(color[i]==1)
            if(total[1]<total[2])
                total[team[i]=1]++;
            else
                total[team[i]=2]++;
    }
}

void main()
{
    int i,a;
    fin >> n;
    for(i=0; i<n; i++) while(1)
    {
        fin >> a; if(!a) break;
        e[i][a-1]=1;
    }
    solve();
    if(bi)
    {
        cout << total[1] << " ";
        for(i=0; i<n; i++) if(team[i]==1) cout << i+1 << " ";
        cout << endl << total[2] << " ";
        for(i=0; i<n; i++) if(team[i]==2) cout << i+1 << " ";
        cout << endl;
    }
    else
        cout << "No solution" << endl;
}