Codeforces 510E Fox and Dinner 题解

题意简述

给定$n(<=200)$个数$a_1,a_2...a_n$，$2<=a_i<=10000$，把这$n$个数分成几组，使得每组中能排出一个序列，并且相邻两个和都是质数。输出方案。

思路

注意：$2<=a_i<=10000$。所以，我们将$a$按奇偶分类，只有奇数能和偶数在一块，奇数和奇数不能一块，偶数和偶数不能一块。所以我们把它们按奇偶分类，又注意到$n<=200$，考虑网络流。

• 对于偶数的$a_i$：$(S->a_i,2)$
• 对于奇数的$a_i$：$(a_i->T,2)$
• 对于$a_i+a_j=prime$,且$a_i$是偶数,$a_j$是奇数：$(a_i->a_j,1)$

跑一遍最大流。如果最大流$=n$，$DFS$求出分组。否则就不可能。

预处理质数，$O(10000+n^2+C)$解决（其中$C$是网络流的复杂度，又被称为玄学常数）

10.24upd 关于建图的具体思路 建图是一个很考验思维能力的过程。

首先我们注意到，每个数最多有两个数相邻，所以这个数和源点/汇点的连边容量为$2$，就代表它最多能通过两条边。而$DFS$的时候，就是通过连接的两条边判断相邻，然后判断顺序的。

然后，考虑到相邻两个数的和必须是质数，所以，不是所有的边都能流过去，必须只有质数才能流过去。所以我们判断两个数的和是否为质数，如果是质数那么就连一条容量为$1$的流过去。

我个人认为，虽然网络流建图就是个毒瘤，但是这个题还比较容易能理解。

代码：

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 322
    #define M 24444
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=Nt.Start(u),__v=Nt.To(i);~i;i=Nt.Next(i),__v=Nt.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    class Graph
    {
        public:
            int EdgeCount;
            int head[M];
            struct Edge
            {
                int To,Label;
                int Next;
            }Ed[2666666];
            void clear()
            {
                MEM(head,-1);
                MEM(Ed,-1);
                EdgeCount=-1;
            }
            void AddEdge(int u,int v,int w)
            {
                ++EdgeCount;
                Ed[EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void AddFlow(int u,int v,int w)
            {
                AddEdge(u,v,w);
                AddEdge(v,u,0);
            }
            int Start(int i){return head[i];}
            int To(int i){return Ed[i].To;}
            int Label(int i){return Ed[i].Label;}
            int Next(int i){return Ed[i].Next;}
    
            int Source,Sink;
            int deep[N];
            queue<int>Q,EmptyQ;
            bool BFS()
            {
                Q=EmptyQ;
                FK(deep);
    
                Q.push(Source);
                deep[Source]=1;
                do
                {
                    int u=Q.front();Q.pop();
                    for(int i=head[u];~i;i=Ed[i].Next)
                    {
                        int v=Ed[i].To;
                        if (deep[v]==0 and Ed[i].Label>0)
                        {
                            deep[v]=deep[u]+1;
                            Q.push(v);
                        }
                    }
                }while(!Q.empty());
    
                if (deep[Sink]==0) return 0;
                return 1;
            }
            int DFS(int u,int MinFlow)
            {
                if (u==Sink) return MinFlow;
                for(int i=head[u];~i;i=Ed[i].Next)
                {
                    int v=Ed[i].To;
                    if (deep[v]==deep[u]+1 and Ed[i].Label!=0)
                    {
                        int d=DFS(v,min(MinFlow,Ed[i].Label));
                        if (d>0)
                        {
                            Ed[i].Label-=d;
                            Ed[i^1].Label+=d;
                            return d;
                        }
                    }
                }
                return 0;
            }
            int Dinic()
            {
                int ans=0;
                while(BFS())
                {
                    int d;
                    while(d=DFS(Source,0x3f3f3f3f))
                    {
                        ans+=d;
                    }
                }
                return ans;
            }
    }Nt;
    int n,a[N];
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Input()
    {
        R1(n);
        F(i,1,n) R1(a[i]);
    }

    int primes[M],notp[M];
    void Init()
    {
        int &cnt=primes[0];
        int n=20000;
        notp[1]=1;
        F(i,2,n)
        {
            if (!notp[i]) primes[++cnt]=i;
            for(int j=1;i*primes[j]<=n and j<=cnt;++j)
            {
                int u=primes[j];
                notp[i*u]=true;
                if (i%u==0) break;
            }
        }
    }
    #define S Nt.Source
    #define T Nt.Sink
    vector<int> mp[M];
    bool vis[M];
    void DFS(int u,int tot)
    {
        mp[tot].push_back(u);
        vis[u]=1;
        Tra(i,u)
        {
            int v=__v;
            if (vis[v]==1) continue;
            if (v!=S and v!=T)
            {
                if (i%2==0 and Nt.Label(i)  ==0) DFS(v,tot);
                if (i%2==1 and Nt.Label(i^1)==0) DFS(v,tot);
            }
        }
    }
    void Soviet()
    {
        Init();
        Nt.clear();
        S=n+1,T=n+2;
        F(i,1,n)
        {
            if (a[i]%2==0)
            {
                Nt.AddFlow(S,i,2);
            }
            else
            {
                Nt.AddFlow(i,T,2);
            }
        }
        F(i,1,n) F(j,1,n)
        {
            if (a[i]%2==0 and a[j]%2==1 and !notp[a[i]+a[j]])
            {
                Nt.AddFlow(i,j,1);
            }
        }
        int flow=Nt.Dinic();
        if (flow==n)
        {
            FK(vis);
            int tot=0;
            F(i,1,n)
            {
                if (vis[i]==0) 
                {
                    DFS(i,++tot);
                }
            }
            printf("%d\n",tot);
            F(i,1,tot)
            {
                printf("%d",mp[i].size());
                F(j,0,(int)mp[i].size()-1)
                {
                    printf(" %d",mp[i][j]);
                }
                putchar('\n');
            }
        }
        else
        {
            puts("Impossible");
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}