Codeforces Round#290(Div.2)E.Fox And Dinner-最大ストリームパリティ構築図
10755 ワード
http://codeforces.com/contest/510/problem/E
n匹のキツネは食事をして、テーブルごとに少なくとも3匹のキツネを要求して、隣接する2匹のキツネの年齢と素数です
年齢が少なくとも2であるため、和は素数が必ず奇数であり、奇数=奇数+偶数は1つの2部図スーパーソース点0がすべての奇数に対して1つの辺をつなぎ、cap=2、すべての偶数とスーパーポイントが1つの辺をつなぎ、cap=2を得る.ある奇数とある偶数とある素数であれば、1つの辺をつなぎ、cap=1.満流には解がある
n匹のキツネは食事をして、テーブルごとに少なくとも3匹のキツネを要求して、隣接する2匹のキツネの年齢と素数です
年齢が少なくとも2であるため、和は素数が必ず奇数であり、奇数=奇数+偶数は1つの2部図スーパーソース点0がすべての奇数に対して1つの辺をつなぎ、cap=2、すべての偶数とスーパーポイントが1つの辺をつなぎ、cap=2を得る.ある奇数とある偶数とある素数であれば、1つの辺をつなぎ、cap=1.満流には解がある
#include<bits/stdc++.h>
const int maxn=210;
const int maxm=45000;
const int INF=1<<30;
using namespace std;
int num[maxn],d[maxn],p[maxn],cur[maxm];
int s,t;
int n,a[maxn];
int vis[maxn],ans[maxn],cnt;
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
vector<Edge> edges;
vector<int> G[maxn];
vector<int> mp[maxn];
inline void addedge(int u,int v,int c)
{
edges.push_back(Edge(u,v,c,0));
edges.push_back(Edge(v,u,0,0));
int m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
int Augment(){
int x=t,a=INF;
while(x!=s){
Edge& e=edges[p[x]];
a=min(a,e.cap-e.flow);
x=e.from;
}
x=t;
while(x!=s){
edges[p[x]].flow+=a;
edges[p[x]^1].flow-=a;
x=edges[p[x]].from;
}
return a;
}
int ISAP()
{
int flow=0;
memset(num,0,sizeof(num));
for(int i=0;i<n+2;++i) num[d[i]]++;
int x=s;
memset(cur,0,sizeof(cur));
while(d[s]<n+2){
if(x==t){
flow+=Augment();
x=s;
}
int ok=0;
for(int i=cur[x];i<G[x].size();++i){
Edge& e=edges[G[x][i]];
if(e.cap>e.flow&&d[e.to]+1==d[x]){
p[e.to]=G[x][i];
cur[x]=i;
x=e.to;
ok=1;
break;
}
}
if(!ok){
int m=INF;
for(int i=0;i<G[x].size();++i){
Edge& e=edges[G[x][i]];
if(e.cap>e.flow) m=min(m,d[e.to]);
}
if(--num[d[x]]==0) break;
num[d[x]=m+1]++;
cur[x]=0;
if(x!=s) x=edges[p[x]].from;
}
}
return flow;
}
bool isprime(int x)
{
for(int i=2;i<=sqrt(x);++i){
if(x%i==0) return false;
}
return true;
}
void dfs(int u){
ans[++cnt]=u;
for(int i=0;i<mp[u].size();++i){
int v=mp[u][i];
if(!vis[v]){
vis[v]=1;
dfs(v);
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.cpp","r",stdin);
#endif // ONLINE_JUDGE
cin>>n;
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) continue;
for(int j=1;j<=n;++j){
if(a[j]&1) continue;
if(isprime(a[i]+a[j])) addedge(i,j,1);
}
}
s=0,t=n+1;
int res=ISAP();
if(res!=n) printf("Impossible
");
else{
for(int i=1;i<=n;++i){
if(~a[i]&1) continue;
for(int j=0;j<G[i].size();++j){
Edge& e=edges[G[i][j]];
int v=e.to;
if(v>0&&v<n+1&&(e.cap==e.flow)){
mp[i].push_back(v);
mp[v].push_back(i);
}
}
}
int count=0;
for(int i=1;i<=n;++i){
if(!vis[i]){
++count;
vis[i]=1;
dfs(i);
}
}
printf("%d
",count);
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;++i){
if(!vis[i]){
cnt=0;
vis[i]=1;
dfs(i);
printf("%d",cnt);
for(int j=1;j<=cnt;++j){
printf(" %d",ans[j]);
}puts("");
}
}
}
return 0;
}
/* 12 2 3 4 5 6 7 8 9 10 11 12 13 u=2 v=1 u=2 v=3 u=4 v=1 u=4 v=5 u=6 v=5 u=6 v=11 u=8 v=7 u=8 v=9 u=10 v=7 u=10 v=11 u=12 v=3 u=12 v=9 ------------------- 1 12 1 2 3 12 9 8 7 10 11 6 5 4 Process returned 0 (0x0) execution time : 0.148 s Press any key to continue. */