把每个数拆成两个点建图
具体原因我想了想。。。因为一个点一定是不能做的。。。但是两个点不能保证一定是对称流法啊。。。（坑）
如果两个数a, b满足要求，则a -> b', b -> a'，边流量为1，费用为- a - b
最后再建源汇S, T，分别连边，流量为1，费用为0
跑一边费用流即可，但是要记下流量
1 /************************************************************** 2 Problem: 2661 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:128 ms 7 Memory:3984 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 14 using namespace std; 15 const int N = 2005; 16 const int M = N * 100; 17 const int inf = (int) 1e9; 18 19 struct edges { 20 int next, to, f, cost; 21 edges() {} 22 edges(int _n, int _t, int _f, int _c) : next(_n), to(_t), f(_f), cost(_c) {} 23 } e[M]; 24 25 int n, S, T; 26 int first[N], tot = 1; 27 int d[N], g[N], q[N]; 28 bool v[N]; 29 30 31 inline void Add_Edges(int x, int y, int f, int c) { 32 e[++tot] = edges(first[x], y, f, c), first[x] = tot; 33 e[++tot] = edges(first[y], x, 0, -c), first[y] = tot; 34 } 35 36 inline int calc() { 37 int flow = inf, x; 38 for (x = g[T]; x; x = g[e[x ^ 1].to]) 39 flow = min(flow, e[x].f); 40 for (x = g[T]; x; x = g[e[x ^ 1].to]) 41 e[x].f -= flow, e[x ^ 1].f += flow; 42 return flow; 43 } 44 45 bool spfa() { 46 int x, y, l, r; 47 for (x = 1; x <= T; ++x) 48 d[x] = inf; 49 d[S] = 0, v[S] = 1, q[0] = S; 50 for(l = r = 0; l != (r + 1) % N; ++l %= N) { 51 for (x = first[q[l]]; x; x = e[x].next) 52 if (d[q[l]] + e[x].cost < d[y = e[x].to] && e[x].f) { 53 d[y] = d[q[l]] + e[x].cost, g[y] = x; 54 if (!v[y]) 55 q[++r %= N] = y, v[y] = 1; 56 } 57 v[q[l]] = 0; 58 } 59 return d[T] != inf; 60 } 61 62 inline void work() { 63 int ans1 = 0, ans2 = 0, del; 64 while (spfa()) { 65 del = calc(); 66 ans1 += del, ans2 += del * d[T]; 67 } 68 printf("%d %d ", ans1 >> 1, -ans2 >> 1); 69 } 70 71 inline int sqr(int x) { 72 return x * x; 73 } 74 75 inline int gcd(int a, int b) { 76 return b ? gcd(b, a % b) : a; 77 } 78 79 inline bool check(int a, int b) { 80 int t = sqr(b) - sqr(a); 81 if (sqr((int) sqrt(t)) != t) return 0; 82 return gcd(a, (int) sqrt(t)) == 1; 83 } 84 85 int main() { 86 int a, b, i, j; 87 scanf("%d%d", &a, &b); 88 S = (b - a + 1) << 1 | 1, T = S + 1; 89 for (i = a; i <= b; ++i) 90 for (j = a; j < i; ++j) if (check(j, i)) 91 Add_Edges(i - a + 1, j + b - a * 2 + 2, 1, - i - j), 92 Add_Edges(j - a + 1, i + b - a * 2 + 2, 1, - i - j); 93 for (i = a; i <= b; ++i) 94 Add_Edges(S, i - a + 1, 1, 0), Add_Edges(i + b - a * 2 + 2, T, 1, 0); 95 work(); 96 return 0; 97 }