有N个正整数，需要从中选出一些数，使这些数的和最大。
若两个数a,b同时满足以下条件，则a,b不能同时被选
1:存在正整数C，使a*a+b*b=c*c
2:gcd(a,b)=1

n<=3000。

网络流

  1 #include <cmath>  2 #include <cstdio>  3 #include <cstring>  4   5 typedef long long lnt;  6   7 const int siz = 1000005;  8 const int inf = 1000000007;  9  10 int n; 11 int a[siz]; 12 int b[siz]; 13  14 int tot; 15 int s, t; 16 int hd[siz]; 17 int to[siz]; 18 int fl[siz]; 19 int nt[siz]; 20  21 inline void add(int u, int v, int f) 22 { 23     nt[tot] = hd[u]; to[tot] = v; fl[tot] = f; hd[u] = tot++; 24     nt[tot] = hd[v]; to[tot] = u; fl[tot] = 0; hd[v] = tot++; 25 } 26  27 int dep[siz]; 28  29 inline bool bfs(void) 30 { 31     static int que[siz]; 32     static int head, tail; 33  34     memset(dep, 0, sizeof(dep)); 35     head = 0, tail = 0; 36     que[tail++] = s; 37     dep[s] = 1; 38  39     while (head != tail) 40     { 41         int u = que[head++], v; 42  43         for (int i = hd[u]; ~i; i = nt[i]) 44             if (!dep[v = to[i]] && fl[i]) 45                 dep[que[tail++] = v] = dep[u] + 1; 46     } 47  48     return dep[t]; 49 } 50  51 int cur[siz]; 52  53 int min(int a, int b) 54 { 55     return a < b ? a : b; 56 } 57  58 int dfs(int u, int f) 59 { 60     if (u == t || !f) 61         return f; 62          63     int used = 0, flow, v; 64  65     for (int i = cur[u]; ~i; i = nt[i]) 66         if (dep[v = to[i]] == dep[u] + 1 && fl[i]) 67         { 68             flow = dfs(v, min(f - used, fl[i])); 69              70             used += flow; 71             fl[i] -= flow; 72             fl[i^1] += flow; 73  74             if (used == f) 75                 return f; 76  77             if (fl[i]) 78                 cur[u] = i; 79         } 80  81     if (!used) 82         dep[u] = 0; 83  84     return used; 85 } 86  87 inline int maxFlow(void) 88 { 89     int maxFlow = 0, newFlow; 90  91     while (bfs()) 92     { 93         for (int i = s; i <= t; ++i) 94             cur[i] = hd[i]; 95  96         while (newFlow = dfs(s, inf)) 97             maxFlow += newFlow; 98     } 99 100     return maxFlow;101 }102 103 inline lnt sqr(lnt x)104 {105     return x * x;106 }107 108 int gcd(int x, int y)109 {110     return y ? gcd(y, x % y) : x;111 }112 113 inline bool check(int x, int y)114 {115     if (gcd(x, y) != 1)116         return false;117 118     lnt t = sqr(x) + sqr(y);119     if (sqr(sqrt(t)) != t)120         return false;121 122     return true;123 }124 125 signed main(void)126 {127     scanf("%d", &n);128 129     for (int i = 1; i <= n; ++i)130         scanf("%d", a + i);131 132     for (int i = 1; i <= n; ++i)133         b[i] = a[i];134     135     s = 0, t = n + 1;136 137     memset(hd, -1, sizeof(hd));138 139     for (int i = 1; i <= n; ++i)140         if (a[i] & 1)141             add(s, i, b[i]);142         else143             add(i, t, b[i]);144 145     for (int i = 1; i <= n; ++i)146         for (int j = 1; j <= n; ++j)147             if (a[i] & 1)if (!(a[j] & 1))148                 if (check(a[i], a[j]))149                     add(i, j, inf);150 151     int sum = 0;152 153     for (int i = 1; i <= n; ++i)154         sum += b[i];155 156     printf("%d\n", sum - maxFlow());157 }