PKU 1034 The dog task

The dog task

２部グラフの最大マッチング。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

double  dist( vector<int> a, vector<int> b );
/*int*/ vector<vector<bool> >   maxmatch2( vector<vector<bool> > G );
/*int*/ vector<vector<int> >    maxflow( vector<vector<int> > G, int s=0, int t=-1 );

int main()
{
    int N, M;  cin >> N >> M;
    vector<vector<int> > B( N, vector<int>( 2 ) );
    for ( int i=0; i<N; i++ )
        cin >> B[i][0] >> B[i][1];
    vector<vector<int> > R( M, vector<int>( 2 ) );
    for ( int i=0; i<M; i++ )
        cin >> R[i][0] >> R[i][1];

    //  G[i][j]：i→i+1の移動中に面白そうな場所jを経由できるか
    vector<vector<bool> > G( N-1, vector<bool>( M ) );
    for ( int i=0; i<N-1; i++ )
    for ( int j=0; j<M; j++ )
        G[i][j] = dist(B[i],R[j]) + dist(R[j],B[i+1]) <= 2*dist(B[i],B[i+1]);

    vector<vector<bool> > F = maxmatch2( G );

    vector<vector<int> > P;
    for ( int i=0; i<N-1; i++ )
    {
        P.push_back( B[i] );
        for ( int j=0; j<M; j++ )
            if ( F[i][j] )
                P.push_back( R[j] );
    }
    P.push_back( B[N-1] );

    cout << P.size() << endl;
    for ( int i=0; i<(int)P.size(); i++ )
        cout << (i>0?" ":"") << P[i][0] << " " << P[i][1];
    cout << endl;
}

//  ２点間距離
double dist( vector<int> a, vector<int> b )
{
    return sqrt( pow(a[0]-b[0],2.0) + pow(a[1]-b[1],2.0) );
}

//  ２部グラフの最大マッチング
//  G[i][j]が真ならばv(i)からv(n+j)にエッジがある
/*int*/ vector<vector<bool> > maxmatch2( vector<vector<bool> > G )
{
    int n = (int)G.size();
    int m = (int)G[0].size();
    vector<vector<int> > E(n+m+2,vector<int>(n+m+2));

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

    //return maxflow(E);

    vector<vector<int> > A = maxflow(E);
    vector<vector<bool> > F(n,vector<bool>(m));
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<m; j++ )
        F[i][j] = A[i+1][n+j+1] == 1;
    return F;
}

//  最大流問題（Edmonds-Karp）
/*int*/ vector<vector<int> > maxflow( vector<vector<int> > G, int s, int t )
{
    int n = (int)G.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 && G[u][v]-F[u][v]>0 )
                P[v] = u,
                Q.push_back(v);
        }
        if ( P[t]==-1 )  break;

        int m = G[P[t]][t];
        for ( int v=P[t]; v!=s; v=P[v] )
            m = min(m,G[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;
    return F;
}