codeforces-510E Fox And Dinner(带限制的二分图多重匹配+奇偶建图+打印路径)
题意:
有n个fox,分别有一个年龄为a[i]。 现在要将n个fox分配入座,但要求两两相邻的fox的年龄和为质数。一桌(环形桌)至少要有三个fox。求要分几桌才能满足上述要求,并打印每桌有几个fox以及每个fox的具体id。(n <= 200, 2 <= a[i] <= 1e4)
思路:
由于年龄最小是2,所以两两相加为质数只可能是一奇一偶相加所得,所以安排座位就是一个奇数两旁是偶数,一个偶数两旁是奇数,一个桌子上的fox个数是偶数个。所以我们可以把奇数和偶数分到二分图的两部,同样得到特判:当且仅当两部的元素个数相等有解。我们将源点S向奇数部建有向边容量为2,将偶数部向汇点T建有向边容量为2,然后就是奇偶建边,如果两个数之和是质数就建一条从奇数到偶数的有向边容量为1。然后如果求得最大流等于n则有解,否则没有。为什么能用最大流做呢,最大流==n就代表A部的每个点恰好匹配B部的两个点,B部的每个点也恰好匹配A部的两个点。然后根据网络流流量的性质就可以得出所有的路径,打印出来即可。
代码:
#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 205;
const int maxm = maxn*maxn;
struct node{int w; int v, next;} edge[maxm];
int pre[maxn], rec[maxn], head[maxn], gap[maxn], now[maxn];
int dis[maxn];
int n, no, up;
int S, T;
queue<int> q;
inline void add(int u, int v, int w)
{
edge[no].v = v; edge[no].w = w;
edge[no].next = head[u]; head[u] = no++;
edge[no].v = u; edge[no].w = 0;
edge[no].next = head[v]; head[v] = no++;
}
inline void pre_init()
{
no = 0;
memset(head, -1, sizeof head);
}
void init(int S, int T)
{
memset(gap, 0, sizeof gap);
memset(dis, 0x3f, sizeof dis);
for(int i = 0; i <= up; ++i)
now[i] = head[i];
while(!q.empty()) q.pop();
dis[T] = 0; q.push(T);
while(!q.empty())
{
int tp = q.front(); q.pop();
++gap[dis[tp]];
int k = head[tp];
while(k != -1)
{
if(dis[edge[k].v] == inf && edge[k^1].w)
{
dis[edge[k].v] = dis[tp]+1;
q.push(edge[k].v);
}
k = edge[k].next;
}
}
}
int SAP(int S, int T)
{
int ans = 0, flow = inf;
int top = S;
pre[S] = S; init(S, T);
while(dis[S] < up)
{
if(top == T)
{
ans += flow;
while(top != S)
{
edge[rec[top]].w -= flow;
edge[rec[top]^1].w += flow;
top = pre[top];
}
flow = inf;
}
int k = now[top];
while(k != -1)
{
int v = edge[k].v;
if(edge[k].w && dis[top] == dis[v]+1)
{
flow = min(flow, edge[k].w);
pre[v] = top; rec[v] = k;
now[top] = k; top = v;
break;
}
k = edge[k].next;
}
if(k == -1)
{
int mind = up;
if(--gap[dis[top]] == 0) break;
int k = now[top] = head[top];
while(k != -1)
{
if(edge[k].w && mind>dis[edge[k].v]) mind = dis[edge[k].v];
k = edge[k].next;
}
++gap[dis[top] = mind+1];
top = pre[top];
}
}
return ans;
}
int a[maxn];
bool isprime[20005], vis[maxn];
vector<int> g[maxn], vt[maxn];
void prime_init()
{
memset(isprime, 0, sizeof isprime);
isprime[1] = true;
for(int i = 2; i*i <= 20000; ++i)
if(!isprime[i])
for(int j = i*i; j <= 20000; j+=i)
isprime[j] = true;
}
bool mapping()
{
int ttx = 0;
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
if(a[i]&1) add(S, i, 2), ++ttx;
else add(i, T, 2);
for(int j = 1; j < i; ++j)
if(!isprime[a[i]+a[j]])
{
if(a[i]&1) add(i, j, 1);
else add(j, i, 1);
}
}
return ttx*2 == n;
}
void dfs(int id, int u)
{
vis[u] = true;
vt[id].push_back(u);
for(int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if(vis[v]) continue;
dfs(id, v);
}
}
void work()
{
memset(vis, 0, sizeof vis);
for(int i = 1; i <= n; ++i) g[i].clear();
for(int i = 1; i <= n; ++i)
{
if(!(a[i]&1)) continue;
for(int k = head[i]; k+1; k = edge[k].next)
{
int v = edge[k].v;
if(v == S) continue;
if(!edge[k].w && !(k&1))
{
g[i].push_back(v);
g[v].push_back(i);
}
}
}
int cnt = 0;
for(int i = 1; i <= n; ++i)
{
if(vis[i]) continue;
++cnt; vt[cnt].clear();
dfs(cnt, i);
}
printf("%d\n", cnt);
for(int i = 1; i <= cnt; ++i)
{
printf("%d", vt[i].size());
for(int j = 0; j < vt[i].size(); ++j)
printf(" %d", vt[i][j]);
printf("\n");
}
}
int main()
{
while(~scanf("%d", &n))
{
up = n+2, S = 0, T = n+1;
pre_init();
prime_init();
if(!mapping()) puts("Impossible");
else if(SAP(S, T) != n) puts("Impossible");
else work();
}
return 0;
}
继续加油~