搬运大佬题解系列：http://blog.csdn.net/qwb492859377/article/details/49021453
传送门：点击打开链接
题意：
n只狐狸，每个狐狸对应了一个数字，现在要把n只狐狸分成很多个圈坐着，每个圈中至少要有3只，且相邻两只狐狸对应的数字只和必须是质数
思路：
由于相加必须是质数。，且有对应的那个数字>=2，说明这个质数必须是奇数，进一步说明两只挨在一起的狐狸必须一奇一偶。看到奇偶，我们就应该要想到网络流
我们让超级源点s连接所有的偶数，边容量为2.让所有的奇数连接超级汇点t，边容量为2，再两两枚举点，看其相加是否为质数，如果是质数，就连接一条从偶数到奇数的边，容量为1。然后跑一遍网络流，验证最后的流量是否等于n就做完了。
还有一个问题就是如何打印。edge[i].cap里面是边的容量。如果之前有容量，但是后来减小了，说明有流量从这里经过。利用这个性质我们就能构造出路径，然后再DFS打印路径，这题就算完成了~
#include<bits/stdc++.h>
using namespace std;
#define N 250
#define MAXM 40050
//---------------------
//以下为ISAP部分
const int INF = 1 << 30;
int head[N], eid;
int dep[N], cur[N], pre[N], gap[N];
int source, sink, nv;//源点、汇点、点的个数inline void init()
{eid = 0;memset(head, -1, sizeof(head));
}
struct Edge
{int u, v, cap, nxt;Edge(){}Edge(int t, int c, int nx):v(t), cap(c), nxt(nx){}
}edge[MAXM];
void AddEdge(int u, int v, int c)
{edge[eid].u = u;edge[eid].v = v;edge[eid].cap = c;edge[eid].nxt = head[u];head[u] = eid++;edge[eid].u = v;edge[eid].v = u;edge[eid].cap = 0;edge[eid].nxt = head[v];head[v] = eid++;
}
void rev_bfs()
{memset(gap, 0, sizeof(gap));memset(dep, -1, sizeof(dep));dep[sink] = 0;queue<int> q;q.push(sink);while(!q.empty()){int u = q.front();q.pop();for(int i = head[u]; i != -1; i = edge[i].nxt){int v = edge[i].v;if(dep[v] != -1)continue;dep[v] = dep[u] + 1;q.push(v);gap[dep[v]]++;}}
}
int ISAP()
{memcpy(cur, head, sizeof(cur));//复制，当前弧优化rev_bfs();int flow = 0, u = pre[source] = source;while(dep[sink] < nv){if(u == sink)//如果已经找到了一条增广路，则沿着增广路修改流量{int f = INF, neck;for(int i = source; i != sink; i = edge[cur[i]].v)if(f > edge[cur[i]].cap){f = edge[cur[i]].cap;//不断更新需要减少的流量neck = i;//记录回退点，目的是为了不用再回到起点重新找}for(int i = source; i != sink; i = edge[cur[i]].v)//修改流量{edge[cur[i]].cap -= f;edge[cur[i]^1].cap += f;}flow += f;//更新u = neck;//回退}int i;for(i = cur[u]; i != -1; i = edge[i].nxt)if(dep[edge[i].v] + 1 == dep[u] && edge[i].cap)break;if(i != -1){cur[u] = i;//如果存在可行增广路，更新pre[edge[i].v] = u;//修改当前弧u = edge[i].v;}else//否则回退，重新找增广路{if((--gap[dep[u]]) == 0)//GAP间隙优化，如果出现断层，可以知道一定不会再有增广路了break;int mind = nv;for(i = head[u]; i != -1; i = edge[i].nxt){if(edge[i].cap && mind > dep[edge[i].v])//寻找可以增广的最小标号{cur[u] = i;//修改当前弧mind = dep[edge[i].v];}}dep[u] = mind + 1;gap[dep[u]]++;u = pre[u];}}return flow;
}
//---------------------int a[N], out[N], cnt;
bool vis[N];
vector<int> mp[N];
bool Isprime(int x)
{bool flag=true;for(int i=2; i*i<=x; i++){if((x%i)==0){flag=false;break;}}return flag;
}
void dfs(int u)
{out[cnt++]=u;for(int i=0; i<mp[u].size(); i++){int v=mp[u][i];if(vis[v]) continue;vis[v]=true;dfs(v);}
}
int main()
{int n;while(scanf("%d", &n)!=EOF){init();for(int i=1; i<=n; i++) mp[i].clear();for(int i=1; i<=n; i++) scanf("%d", &a[i]);for(int i=1; i<=n; i++){if(a[i]&1) AddEdge(0, i, 2);else AddEdge(i, n+1, 2);}for(int i=1; i<=n; i++){if((a[i]&1)==0) continue;for(int j=1; j<=n; j++){if(a[j]&1) continue;if(Isprime(a[i]+a[j]))AddEdge(i, j, 1);}}source=0, sink = n+1, nv=n+2;int ans=ISAP();if(ans!=n){printf("Impossible\n");continue;}for(int i=0; i<eid; i++){if(edge[i].u>0&&edge[i].u<n+1&&edge[i].v>0&&edge[i].v<n+1){int u=edge[i].u, v=edge[i].v;if((a[u]&1)&&edge[i].cap==0){mp[u].push_back(v);mp[v].push_back(u);}}}int Count=0;cnt=0;memset(vis, false, sizeof(vis));for(int i=1; i<=n; i++){if(!vis[i]){++Count;vis[i]=true;dfs(i);}}printf("%d\n", Count);memset(vis, false, sizeof(vis));for(int i=1; i<=n; i++){if(!vis[i]){cnt=0;vis[i]=true;dfs(i);printf("%d", cnt);for(int j=0; j<cnt; j++) printf(" %d", out[j]);printf("\n");}}}return 0;
}