SRM477 Div1 Medium(500) PythTriplets

PythTriplets

aとbが互いに素であることから、aとbどちらも偶数になることは無い。また、aもbも奇数と仮定すると、a=2n-1, b=2m-1として、c²=a²+b²=2(2n²+2m²-2n-2m+1)。2(2n²+2m²-2n-2m+1)が平方数であるためには、(2n²+2m²-2n-2m+1)が素因数2を含まなければならいが、(2n²+2m²-2n-2m+1)は奇数。よって、素なピタゴラス数は奇数と偶数の組み合わせ。２部グラフの最大マッチング問題。

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <sstream>
#include <numeric>

using namespace std;

class PythTriplets
{
    bool pyth( int a, int b );
    int gcd( int a, int b );
    int maxmatch2( vector<vector<bool> > edge, int L );
    int maxflow( vector<vector<int> > edge, int s=0, int t=-1 );
public:
    int findMax( vector <string> stick );
};

int PythTriplets::findMax( vector <string> stick )
{
    stringstream ss( accumulate(stick.begin(), stick.end(),string()));

    vector<int> s;
    int temp;
    while ( ss >> temp )
        s.push_back( temp );

    int N = (int)s.size();

    vector<vector<bool> > E( N, vector<bool>( N, false ) );
    vector<int> V;

    for ( int i=0; i<N; i++ )
    if ( s[i] % 2 == 0 )
        V.push_back( i );

    int L = (int)V.size();

    for ( int i=0; i<N; i++ )
    if ( s[i] % 2 == 1 )
        V.push_back( i );

    for ( int i=0; i<L; i++ )
    for ( int j=L; j<N; j++ )
        E[i][j] = pyth( s[V[i]], s[V[j]] );

    return maxmatch2( E, L );
}

bool PythTriplets::pyth( int a, int b )
{
    int c = (int)( sqrt( (long double)( (long long)a*a+(long long)b*b ) ) + 0.01 );

    return (long long)a*a+(long long)b*b == (long long)c*c  &&
        gcd(a,b) == 1;
}

int PythTriplets::gcd( int a, int b )
{
    if ( a < b )  return gcd( b, a );
    if ( b == 0 )  return a;
    return gcd( b, a%b );
}

//  ２部グラフの最大マッチング
//  v[:L]が左側、v[L:]が右側
int PythTriplets::maxmatch2( vector<vector<bool> > edge, int L )
{
    int n = (int)edge.size();
    vector<vector<int> > E(n+2,vector<int>(n+2));

    for ( int i=0; i<L; i++ )
        E[0][i+1] = 1;
    for ( int i=0; i<L; i++ )
    for ( int j=L; j<n; j++ )
        if ( edge[i][j] )
            E[i+1][j+1] = 1;
    for ( int i=L; i<n; i++ )
        E[i+1][n+1] = 1;

    return maxflow(E);
}

//  最大流問題（Edmonds-Karp）
int PythTriplets::maxflow( vector<vector<int> > edge, int s, int t )
{
    int n = (int)edge.size();
    if ( t<0 )  t = n-1;
    int f = 0;
    vector<vector<int> > F(n,vector<int>(n));
    while(true)
    {
        vector<int> P(n,-1);  P[s]=-2;
        vector<int> Q(1,s);
        while ( !Q.empty() && P[t]==-1 )
        {
            int u = Q.back();  Q.pop_back();
            for ( int v=0; v<n && P[t]==-1; v++ )
            if ( P[v]==-1 && edge[u][v]-F[u][v]>0 )
                P[v] = u,
                Q.push_back(v);
        }
        if ( P[t]==-1 )  break;

        int m = edge[P[t]][t];
        for ( int v=P[t]; v!=s; v=P[v] )
            m = min(m,edge[P[v]][v]-F[P[v]][v]);

        f += m;
        for ( int v=t; v!=s; v=P[v] )
            F[P[v]][v] += m,
            F[v][P[v]] -= m;
    }

    return f;
}