BZOJ_2661_[BeiJing wc2012]连连看_费用流
Description
凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是，给出一个闭区间[a,b]中的全部整数，如果其中某两个数x,y（设x>y）的平方差x2-y2是一个完全平方数z2，并且y与z互质，那么就可以将x和y连起来并且将它们一起消除，同时得到x+y点分数。那么过关的要求就是，消除的数对尽可能多的前提下，得到足够的分数。快动手动笔算一算吧。
Input
只有一行，两个整数，分别表示a,b。
Output
两个数，可以消去的对数，及在此基础上能得到的最大分数。
Sample Input
1 15
Sample Output
2 34
HINT
对于30%的数据，1<=a,b<=100
对于100%的数据，1<=a,b<=1000
首先考虑拆点，对于符合条件的(i,j),连i->j(1,i+j)和j->i(1,i+j)两条边。
如果只连一条边不能限制住每个数只用一次，如果正反两条都连说明如果一个选了另一个必须也选。
而且不会出现流出去流不回来的情况。
那么求最大费用最大流，答案除个2即可。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define N 1000050
#define S (2*n+1)
#define T (2*n+2)
#define inf 100000000
typedef double f2;
#define eps 1e-6
f2 Abs(f2 x) {return x>0?x:-x;}
int head[N],to[N<<1],nxt[N<<1],flow[N<<1],cnt=1,n,dis[N],Q[N],l,r,val[N<<1],inq[N];
int path[N],A,B;
bool check(int y,int x) {
int z=x*x-y*y;
int p=(int)(sqrt(z));
if(p*p!=z) return 0;
// puts("FUCK");
return __gcd(p,y)==1;
}
void add(int u,int v,int f,int w) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f; val[cnt]=w;
to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0; val[cnt]=-w;
}
bool spfa() {
memset(dis,0xef,sizeof(dis));
memset(path,0,sizeof(path));
l=r=0; Q[r++]=S; dis[S]=0; inq[S]=1;
while(l!=r) {
int x=Q[l++],i;inq[x]=0; if(l==T) l=0;
for(i=head[x];i;i=nxt[i]) {
if(dis[to[i]]<dis[x]+val[i]&&flow[i]) {
dis[to[i]]=dis[x]+val[i];
path[to[i]]=i^1;
if(!inq[to[i]]) {
inq[to[i]]=1; Q[r++]=to[i];
if(r==T) r=0;
}
}
}
}
return path[T];
}
void mfmc() {
int mc=0,mf=0;
while(spfa()) {
int nf=1<<30;
int i;
for(i=T;i!=S;i=to[path[i]]) {
nf=min(nf,flow[path[i]^1]);
}
for(i=T;i!=S;i=to[path[i]]) {
flow[path[i]]+=nf;
flow[path[i]^1]-=nf;
mc+=nf*val[path[i]^1];
}
mf+=nf;
}
printf("%d %d\n",mf>>1,mc>>1);
}
int main() {
scanf("%d%d",&A,&B);
n=B-A+1;
int i,j;
for(i=1;i<=n;i++) {
add(S,i,1,0); add(i+n,T,1,0);
for(j=i+1;j<=n;j++) {
if(check(i+A-1,j+A-1)) {
add(i,j+n,1,i+A-1+j+A-1);
add(j,i+n,1,i+A-1+j+A-1);
}
}
}
mfmc();
}