2015年2月16日 星期一

2015/02/16 Codeforces 510E. Fox And Dinner

/*
    二分圖匹配
    匈牙利演算法
*/
// http://codeforces.com/problemset/problem/510/E
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

bool is_prime[100000];

void set_prime()
{
    fill(is_prime, is_prime+100000, true);
    is_prime[0] = is_prime[1] = false;

    for(int i = 2; i*i < 100000; i++)
    {
        if( !is_prime[i] ) continue;

        for(int j = i*i; j < 100000; j += i)
            is_prime[j] = false;
    }
}

vector<int> even, odd;
vector<int> v[300], e[300];
int pr[300];
bool visit[300];
bool hv[300];

int N;
int A[300];

vector<int> p, q;

bool find(int x)
{
    visit[x] = true;

    for(int vi = 0; vi < v[x].size(); vi++)
    {
        int p = pr[v[x][vi] ];

        if( !p || !visit[p] && find(p) )
        {
            pr[x] = v[x][vi];
            pr[v[x][vi] ] = x;
            return true;
        }
    }

    return false;
}

int main()
{
    set_prime();

    scanf("%d", &N);

    for(int Ni = 1; Ni <= N; Ni++)
    {
        scanf("%d", &A[Ni]);

        if( A[Ni]%2 == 0 ) even.push_back(Ni);
        else odd.push_back(Ni);
    }

    if( even.size() != odd.size() )
    {
        puts("Impossible");
        return 0;
    }

    fill(pr, pr+300, 0);

    for(int i = 0; i < odd.size(); i++)
    {
        for(int j = 0; j < even.size(); j++)
        {
            int a = A[odd[i] ];
            int b = A[even[j] ];

            if( is_prime[a+b] )
                v[i+1].push_back(j+odd.size()+1 );
        }
    }

    for(int i = 1; i <= odd.size(); i++)
    {
        fill(visit, visit+300, false);

        if( !find(i) )
        {
            puts("Impossible");
            return 0;
        }
    }

    for(int i = 1; i <= odd.size(); i++)
    {
        int a = i-1;
        int b = pr[i]-odd.size()-1;

        e[odd[a] ].push_back(even[b] );
        v[i].erase(find(v[i].begin(), v[i].end(), pr[i]) );
    }

    fill(pr, pr+300, 0);

    for(int i = 1; i <= odd.size(); i++)
    {
        fill(visit, visit+300, false);

        if( !find(i) )
        {
            puts("Impossible");
            return 0;
        }
    }

    for(int i = 1; i <= odd.size(); i++)
    {
        int a = i-1;
        int b = pr[i]-odd.size()-1;

        e[even[b] ].push_back(odd[a] );
    }

    vector<vector<int> > Ans;

    for(int Ni = 1; Ni <= N; Ni++)
    {
        if( hv[Ni] ) continue;

        vector<int> t;

        int p = Ni;

        while(1)
        {
            t.push_back(p);
            hv[p] = true;

            if( e[p][0] == t[0] ) break;
            p = e[p][0];
        }

        Ans.push_back(t);
    }

    printf("%d\n", Ans.size());

    for(int Ai = 0; Ai < Ans.size(); Ai++)
    {
        vector<int> &t = Ans[Ai];

        printf("%d", t.size());

        for(int ti = 0; ti < t.size(); ti++)
            printf(" %d", t[ti]);

        puts("");
    }

}

沒有留言:

張貼留言