最大流最小割定理的应用
添加源点（src）与汇点（sink）
由于P是偶数，那么对于点i与j，若gcd(x[i] ^ y[i] ^ x[j] ^ y[j],p) > 1,则可共存，可将点集分为两个集合a，b（二分图），a中点的x与y坐标同奇同偶，y中点的坐标一奇一偶，src与a中点连x[i] & y[i]的边，b中点与sink连x[i]&y[i]的边。若两点不能共存（该两点一定一个在a一个在b），连INF=max的边。求出最小割，ans=sum-maxflow().
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<cstdlib>
#include<cmath>
using
namespace std;
const int MAXM = 2000011;
const int MAXN = 511;
long
long INF = 0;
struct edge
{
int v,nxt;
long long
f;
};
edge e[MAXM];
int g[MAXN];
int nume,n,p;
int
x[MAXN],y[MAXN],dist[MAXN];
bool vis[MAXN];
int src,sink;
int
a[MAXN],b[MAXN];
int tot1,tot2;
void init()
{
memset(g,0,sizeof(g));
nume = 1;
for (int i = 1; i <= n; i++)
scanf("%d%d",&x[i],&y[i]);
}
void addedge(int u,int v,long long
c)
{
e[++nume].v = v;
e[nume].f = c;
e[nume].nxt =
g[u];
g[u] = nume;
e[++nume].v = u;
e[nume].f = 0;
e[nume].nxt = g[v];
g[v] = nume;
}
int gcd(int a,int b)
{
if (b == 0) return a;
return
gcd(b,a%b);
}
queue<int>que;
void bfs()
{
memset(dist,0,sizeof(dist));
while (!que.empty()) que.pop();
vis[src] = 1;
que.push(src);
while (!que.empty())
{
int u = que.front();
que.pop();
for (int i = g[u];i;i =
e[i].nxt)
if (e[i].f && !vis[e[i].v])
{
que.push(e[i].v);
dist[e[i].v] = dist[u] + 1;
vis[e[i].v] = 1;
}
}
}
/*inline long long mint(int
x,long long y)
{
if (x < y) return x;
return
y;
}*/
long long dfs(int u,long long delta)
{
if (u == sink)
{
return delta;
}
else
{
long long
ret = 0;
for (int i = g[u]; delta && i; i = e[i].nxt)
if (e[i].f && dist[e[i].v] == dist[u] +1)
{
long long dd = dfs(e[i].v,min(e[i].f,delta));
e[i].f -=
dd;
e[i ^ 1].f += dd;
delta -= dd;
ret += dd;
}
return ret;
}
}
long long
maxflow()
{
long long ret = 0;
while (1)
{
memset(vis,0,sizeof(vis));
bfs();
if (!vis[sink]) return
ret;
ret += dfs(src,INF);
}
}
int main()
{
while (scanf("%d%d",&n,&p) != EOF)
{
init();
src = 0; sink = n + 1;
tot1 = tot2 = 0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for (int i =
1; i <= n; i++)
{
int s1 = x[i] % 2,s2 = y[i] %
2;
int s = s1 + s2;
if (s % 2 == 0) a[++tot1] = i;
else b[++tot2] = i;
}
long long ans = 0ll;
for
(int i = 1;i <= n; i++) ans += (x[i] & y[i]);
INF = ans;
for (int i = 1; i <= tot1; i++) addedge(0,a[i],x[a[i]] &
y[a[i]]);
for (int i = 1; i <= tot2; i++) addedge(b[i],n +
1,x[b[i]] & y[b[i]]);
for (int i = 1; i <= tot1; i++)
for (int j = 1; j <= tot2; j++)
if (gcd(x[a[i]] ^
y[a[i]] ^ x[b[j]] ^ y[b[j]],p) == 1) addedge(a[i],b[j],INF);
ans =
ans - maxflow();
cout<<ans<<endl;
}
return
0;
}
ZOJ3760 Treasure Hunting,布布扣,bubuko.com
原文：http://www.cnblogs.com/yuhao1994/p/3577800.html