有N个正整数，需要从中选出一些数，使这些数的和最大。
若两个数a,b同时满足以下条件，则a,b不能同时被选
1:存在正整数C，使a*a+b*b=c*c
2:gcd(a,b)=1
有N个正整数，需要从中选出一些数，使这些数的和最大。
若两个数a,b同时满足以下条件，则a,b不能同时被选
1:存在正整数C，使a*a+b*b=c*c
2:gcd(a,b)=1
n<=3000。
所以这道题a的数据范围是什么......用long long可以过，不知道int行不行。
嗯，把所有有关系的数字连一条边，这道题就变成了选出一些点使这些点两两没有边相连，求最大点权。这样就变成了最大点权独立集问题。
然后好像这个图一定是二分图，就可以用网络流做了。如果不是二分图就是NP问题了233。
有奇怪的定理：最大点权独立集 = 总权值 - 最小点权覆盖集 = 总权值 - 最小割 = 总权值 - 最大流。
好像不只一个定理，怪我咯。
把每个数字拆成两个点，从源点连向一个点，另一个点连向汇点，边权均为数字大小。然后把有关系的点之间连一条边，边权无限大。
跑一遍最大流，答案就是总权值 - 最大流 / 2。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll INF = 2147483647; 5 struct edge 6 { 7 int v, nxt; 8 ll w; 9 }e[300005]; 10 queue<int> Q; 11 ll d[3005]; 12 int fst[6005], etot = 1, sss, ttt, level[6005]; 13 14 void addedge(int u, int v, ll w) 15 { 16 e[++etot] = (edge){v, fst[u], w}, fst[u] = etot; 17 } 18 19 bool istri(ll a, ll b) 20 { 21 ll c = (ll)sqrt(a * a + b * b + 0.1); 22 return c * c == a * a + b * b; 23 } 24 25 ll gcd(ll a, ll b) 26 { 27 return b ? gcd(b, a % b) : a; 28 } 29 30 int BFS() 31 { 32 memset(level, 0, sizeof(level)); 33 Q.push(sss), level[sss] = 1; 34 while(!Q.empty()) 35 { 36 int u = Q.front(); 37 Q.pop(); 38 for(int i = fst[u]; i; i = e[i].nxt) 39 if(!level[e[i].v] && e[i].w) 40 Q.push(e[i].v), level[e[i].v] = level[u] + 1; 41 } 42 return level[ttt]; 43 } 44 45 ll Dinic(int u, ll lim) 46 { 47 ll tmp = lim; 48 if(u == ttt) return lim; 49 for(int i = fst[u]; i; i = e[i].nxt) 50 if(level[e[i].v] == level[u] + 1 && e[i].w) 51 { 52 ll flow = Dinic(e[i].v, min(tmp, e[i].w)); 53 e[i].w -= flow, e[i ^ 1].w += flow; 54 if(!(tmp -= flow)) break; 55 } 56 if(tmp == lim) level[u] = 0; 57 return lim - tmp; 58 } 59 60 int main() 61 { 62 int n; 63 ll ans = 0; 64 cin >> n; 65 sss = (n << 1) + 1, ttt = (n << 1) + 2; 66 for(int i = 1; i <= n; i++) 67 cin >> d[i]; 68 for(int i = 1; i <= n; i++) 69 { 70 addedge(sss, i, d[i]), addedge(i, sss, 0); 71 addedge(i + n, ttt, d[i]), addedge(ttt, i + n, 0); 72 } 73 for(int i = 1; i <= n; i++) 74 for(int j = 1; j <= n; j++) 75 if(istri(d[i], d[j]) && gcd(d[i], d[j]) == 1) 76 addedge(i, j + n, INF), addedge(j + n, i, 0); 77 while(BFS()) 78 ans += Dinic(sss, INF); 79 ans = -(ans >> 1); 80 for(int i = 1; i <= n; i++) 81 ans += d[i]; 82 cout << ans << endl; 83 return 0; 84 }
原文：http://www.cnblogs.com/CtrlCV/p/5372858.html
