题解 CF510E 【Fox And Dinner】

可以用网络流解决这个题。

注意到\(a_i \geqslant 2\)，所以当相邻数字要和为质数时，这两个数要一个为奇数，一个为偶数。

所以就先将所有数按奇偶分为两列，其就构成了一个二分图，二分图中和为质数的两个数间连容量为\(1\)的边，表示只能匹配一次。

因为是圆桌，所以一个数要恰好匹配两个数，所以每个点在和源汇点连边时，容量要为\(2\)，同时这也保证了每个圆桌中至少有\(3\)个狐狸。

无解的情况就是二分图两个部分大小不是都为\(\frac{n}{2}\)或最大流的结果不为\(n\)。

在跑完最大流后的残量网络中找环即可确定满足要求的分配方案。

\(code:\)

#include<bits/stdc++.h>

#define maxn 400010

#define all 20000

#define inf 1000000000

using namespace std;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,tot,s,t,cnt1,cnt2,ans;

int a[maxn],p1[maxn],p2[maxn],p[maxn],cur[maxn],d[maxn];

bool tag[maxn],vis[maxn];

vector<int> ve[maxn];

struct edge

{

    int to,nxt,v;

}e[maxn];

int head[maxn],edge_cnt=1;

void add(int from,int to,int val)

{

    e[++edge_cnt]=(edge){to,head[from],val},head[from]=edge_cnt;

    e[++edge_cnt]=(edge){from,head[to],0},head[to]=edge_cnt;

}

bool bfs()

{

	queue<int> q;

	for(int i=s;i<=t;++i) cur[i]=head[i],d[i]=0;

	q.push(s),d[s]=1;

	while(!q.empty())

	{

		int x=q.front();

		q.pop();

		for(int i=head[x];i;i=e[i].nxt)

		{

			int y=e[i].to,v=e[i].v;

			if(d[y]||!v) continue;

			d[y]=d[x]+1,q.push(y);

		}

	}

	return d[t];

}

int dfs(int x,int lim)

{

	if(x==t) return lim;

	int res=lim,flow;

	for(int &i=cur[x];i;i=e[i].nxt)

	{

		int y=e[i].to,v=e[i].v;

		if(d[y]!=d[x]+1||!v) continue;

		if(flow=dfs(y,min(res,v)))

		{

			res-=flow;

			e[i].v-=flow;

			e[i^1].v+=flow;

			if(!res) break;

		}

	}

	return lim-res;

}

int dinic()

{

    int flow,v=0;

    while(bfs())

        while(flow=dfs(s,inf))

            v+=flow;

    return v;

}

void init()

{

    for(int i=2;i<=all;++i)

    {

        if(!tag[i]) p[++tot]=i;

        for(int j=1;j<=tot;++j)

        {

            int k=i*p[j];

            if(k>all) break;

            tag[k]=true;

            if(i%p[j]==0) break;

        }

    }

}

void dfs_ans(int x,int type)

{

    vis[x]=true,ve[ans].push_back(x);

    for(int i=head[x];i;i=e[i].nxt)

    {

        int y=e[i].to;

        if(e[i^type].v||vis[y]) continue;

        dfs_ans(y,type^1);

    }

}

int main()

{

    init(),read(n),t=n+1;

    for(int i=1;i<=n;++i)

    {

        read(a[i]);

        if(a[i]&1) p1[++cnt1]=i;

        else p2[++cnt2]=i;

    }

    if(cnt1!=cnt2)

    {

        puts("Impossible");

        return 0;

    }

    for(int i=1;i<=n/2;++i)

        for(int j=1;j<=n/2;++j)

            if(!tag[a[p1[i]]+a[p2[j]]])

                add(p1[i],p2[j],1);

    for(int i=1;i<=n/2;++i) add(s,p1[i],2);

    for(int i=1;i<=n/2;++i) add(p2[i],t,2);

    if(dinic()!=n)

    {

        puts("Impossible");

        return 0;

    }

    vis[s]=vis[t]=true;

    for(int i=1;i<=n/2;++i)

    {

        if(vis[p1[i]]) continue;

        ans++,dfs_ans(p1[i],0);

    }

    printf("%d\n",ans);

    for(int i=1;i<=ans;++i)

    {

        printf("%d ",ve[i].size());

        for(int j=0;j<ve[i].size();++j)

            printf("%d ",ve[i][j]);

        puts("");

    }

    return 0;

}

巴特西

题解 CF510E 【Fox And Dinner】

最新文章

热门文章