SRM549 Div1 Easy(250), Div2 Medium(500) PointyWizardHats

PointyWizardHats

2部グラフの最大マッチングに帰着できる。1個目の条件は、上の円錐のほうが頂角が小さいということ。

#include <vector>
using namespace std;

//  最大流
int maxflow( vector<vector<int> > edge, int s=0, int t=-1 )
{
    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;
}

//  二部グラフの最大マッチング
int bipartite( vector<vector<bool> > edge )
{
    int n = (int)edge.size();
    int m = (int)edge[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 ( edge[i][j] )
            E[i+1][j+n+1] = 1;
    for ( int i=0; i<m; i++ )
        E[i+n+1][n+m+1] = 1;

    return maxflow(E);
}

class PointyWizardHats{public:
int getNumHats( vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius )
{
    int n = (int)topHeight.size();
    int m = (int)bottomHeight.size();

    vector<vector<bool> > E(n,vector<bool>(m));
    for ( int i=0;i <n; i++)
    for ( int j=0; j<m; j++ )
        E[i][j] = topHeight[i]*bottomRadius[j]>bottomHeight[j]*topRadius[i] &&
                  topRadius[i]<bottomRadius[j];

    return bipartite(E);
}};