Reverse the Graphs - CRANREVG - Cranium 2015

/*  Sanchit Abrol  */
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define all(X) (X).begin(),(X).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define s(a) scanf("%d", &a)
#define INF (1LL<<60)

const int MAXN = 210;
int N,i,j,T,in[MAXN],out[MAXN],S;
bool vis[MAXN];
long long G[MAXN][MAXN],flow[MAXN],prevn[MAXN];
long long maxflow(int source, int sink);
void dfs(int v);
vector<vector<int> > edges;

int main()
{
    s(N);
    int ind = 0, outd = 0;
    for(i = 0; i < N; i++)
    {
        s(out[i]); outd += out[i];
        s(in[i]);  ind += in[i];
    }
    if(outd != ind)
    {
        printf("Not possible\n");
        return 0;
    }
    for(i = 0; i < N; i++)
    {
        if(out[i])
        {
            for(j = 0; j < N; j++)
                if(in[j] && i != j)
                    G[i + 1][j + N + 1] = 1;
        }
    }
    S = 2*N + 1;
    T = 2*N + 2;
    for(i = 0; i < N; i++)
    {
        G[S][i + 1] = out[i];
        G[i + N + 1][T] = in[i];
    }
    long long x = maxflow(S, T);
    if(x != ind)
    {
        printf("Not possible\n");
        return 0;
    }
    edges.resize(N + 2);
    for(i = 1; i <= N; i++)
    for(j = N+1; j <= 2*N; j++)
        if(G[j][i] > 0)
            edges[i].pb(j-N);
    for(i = 1; i <= N; i++)
    {
        printf("%d ", (int)edges[i].size());
        for(auto x : edges[i])
            printf("%d ", x);
        printf("\n");
    }

    return 0;
}

void dfs(int v)
{
    vis[v] = true;
    for(int i=1;i<=2*N+2;i++)
        if(G[v][i] > 0 && !vis[i])
            dfs(i);
}

long long maxflow(int source, int sink)
{
    if(source == sink)
        return INF;

    long long total_flow = 0, mx_flow = 0;
    int mx_idx = -1;
    while(1)
    {
        memset(flow,0,sizeof flow);
        memset(prevn,0,sizeof prevn);
        memset(vis,0,sizeof vis);
        flow[source] = INF;

        while(1)
        {
            mx_flow = 0;
            mx_idx = -1;
            for(int i=1; i<=2*N+2; i++)
            if(flow[i] > mx_flow && !vis[i])
            {
                mx_flow = flow[i];
                mx_idx = i;
            }
            if(mx_idx == -1 || mx_idx == sink)
                break;

            vis[mx_idx] = 1;
            for(int i=1; i<=2*N+2; i++)
            if(flow[i] < min(mx_flow,G[mx_idx][i]))
            {
                prevn[i] = mx_idx;
                flow[i] = min(mx_flow,G[mx_idx][i]);
            }
        }
        if(mx_idx == -1) break;

        total_flow += flow[sink];

        int cur = sink;
        while(cur != source)
        {
            int next = prevn[cur];
            G[next][cur] -= flow[sink];
            G[cur][next] += flow[sink];
            cur = next;
        }
    }
    return total_flow;
}