题目描述
凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是，给出一个闭区间[a,b]中的全部整数，如果其中某两个数x,y（设x>y）的平方差x2-y2是一个完全平方数z2，并且y与z互质，那么就可以将x和y连起来并且将它们一起消除，同时得到x+y点分数。那么过关的要求就是，消除的数对尽可能多的前提下，得到足够的分数。快动手动笔算一算吧。
输入
只有一行，两个整数，分别表示a,b。
输出
两个数，可以消去的对数，及在此基础上能得到的最大分数。
样例输入
1 15
样例输出
2 34
题解
拆点+最大费用最大流
分析题目要求，发现x和y一定是互质的。
对于i和j，如果i和j符合题目要求，那么加i->j'和j->i'，容量为1，费用为i+j的两条边。
对于所有的i，加S->i和i'->T，容量为1，费用为0的边。
然后跑最大费用最大流，答案为maxflow/2和mincost/2。
这样建图看起来是理所当然的。好像有什么问题？
会不会出现a1->a2'，a2->a3'，a3->a1'的情况？以及会不会TLE？
自己写一个程序试了一下，测试结果：不存在a1->a2'，a2->a3'，a3->a1'的情况，满足条件的点对最多只有316*2对。
然后跑一下最大费用最大流就AC了。
方法：先将cost取相反数，然后跑最小费用最大流，再对费用取相反数。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
queue<int> q;
int head[2010] , to[100010] , val[100010] , cost[100010] , next[100010] , cnt = 1 , dis[2010] , from[2010] , pre[2010] , s , t;
int gcd(int x , int y)
{
return y ? gcd(y , x % y) : x;
}
void add(int x , int y , int z , int c)
{
to[++cnt] = y , val[cnt] = z , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt;
to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;
}
bool spfa()
{
int i , x;
memset(from , -1 , sizeof(from));
memset(dis , 0x7f , sizeof(dis));
dis[s] = 0;
q.push(s);
while(!q.empty())
{
x = q.front() , q.pop();
for(i = head[x] ; i ; i = next[i])
if(val[i] && dis[to[i]] > dis[x] + cost[i])
dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]);
}
return ~from[t];
}
int main()
{
int n , a , b , i , j , tmp , maxflow = 0 , mincost = 0 , k;
scanf("%d%d" , &a , &b);
n = b - a + 1 , s = 0 , t = 2 * n + 1;
for(i = a ; i <= b ; i ++ )
{
for(j = a ; j < i ; j ++ )
{
tmp = (int)round(sqrt(i * i - j * j));
if(tmp * tmp == i * i - j * j && gcd(j , tmp) == 1)
add(i - a + 1 , j - a + 1 + n , 1 , - i - j) , add(j - a + 1 , i - a + 1 + n , 1 , - i - j);
}
}
for(i = 1 ; i <= n ; i ++ ) add(s , i , 1 , 0) , add(i + n , t , 1 , 0);
while(spfa())
{
k = 0x7f7f7f7f;
for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]);
maxflow += k , mincost += k * dis[t];
for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k;
}
printf("%d %d\n" , maxflow / 2 , -mincost / 2);
return 0;
}