[BZOJ3275] Number (网络流)

Description

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

Input

　　第一行一个正整数n，表示数的个数。

　　第二行n个正整数a1,a2,?an。

Output

　　最大的和。

Sample Input

5
3 4 5 6 7

Sample Output

HINT

　　n<=3000。

Source

　　网络流

Solution

　　所以这道题a的数据范围是什么......用long long可以过，不知道int行不行。

　　嗯，把所有有关系的数字连一条边，这道题就变成了选出一些点使这些点两两没有边相连，求最大点权。这样就变成了最大点权独立集问题。

　　然后好像这个图一定是二分图，就可以用网络流做了。如果不是二分图就是NP问题了233。

　　有一个奇怪的定理：最大点权独立集 = 总权值 - 最小点权覆盖集 = 总权值 - 最小割 = 总权值 - 最大流。

　　好像不只一个定理，怪我咯。

　　把每个数字拆成两个点，从源点连向一个点，另一个点连向汇点，边权均为数字大小。然后把有关系的点之间连一条边，边权无限大。

　　跑一遍最大流，答案就是总权值 - 最大流 / 2。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll INF = ;

 struct edge

 {

     int v, nxt;

     ll w;

 }e[];

 queue<int> Q;

 ll d[];

 int fst[], etot = , sss, ttt, level[];

 void addedge(int u, int v, ll w)

 {

     e[++etot] = (edge){v, fst[u], w}, fst[u] = etot;

 }

 bool istri(ll a, ll b)

 {

     ll c = (ll)sqrt(a * a + b * b + 0.1);

     return c * c == a * a + b * b;

 }

 ll gcd(ll a, ll b)

 {

     return b ? gcd(b, a % b) : a;

 }

 int BFS()

 {

     memset(level, , sizeof(level));

     Q.push(sss), level[sss] = ;

     while(!Q.empty())

     {

         int u = Q.front();

         Q.pop();

         for(int i = fst[u]; i; i = e[i].nxt)

             if(!level[e[i].v] && e[i].w)

                 Q.push(e[i].v), level[e[i].v] = level[u] + ;

     }

     return level[ttt];

 }

 ll Dinic(int u, ll lim)

 {

     ll tmp = lim;

     if(u == ttt) return lim;

     for(int i = fst[u]; i; i = e[i].nxt)

         if(level[e[i].v] == level[u] +  && e[i].w)

         {

             ll flow = Dinic(e[i].v, min(tmp, e[i].w));

             e[i].w -= flow, e[i ^ ].w += flow;

             if(!(tmp -= flow)) break;

         }

     if(tmp == lim) level[u] = ;

     return lim - tmp;

 }

 int main()

 {

     int n;

     ll ans = ;

     cin >> n;

     sss = (n << ) + , ttt = (n << ) + ;

     for(int i = ; i <= n; i++)

         cin >> d[i];

     for(int i = ; i <= n; i++)

     {

         addedge(sss, i, d[i]), addedge(i, sss, );

         addedge(i + n, ttt, d[i]), addedge(ttt, i + n, );

     }

     for(int i = ; i <= n; i++)

         for(int j = ; j <= n; j++)

             if(istri(d[i], d[j]) && gcd(d[i], d[j]) == )

                 addedge(i, j + n, INF), addedge(j + n, i, );

     while(BFS())

         ans += Dinic(sss, INF);

     ans = -(ans >> );

     for(int i = ; i <= n; i++)

         ans += d[i];

     cout << ans << endl;

     return ;

 }

秒客网