SRM527 Div1 Medium(450) P8XMatrixRecovery

P8XMatrixRecovery

頂点数が2Cの二部グラフを考える。rowsのi番目の列と、columnsのj番目の要素に、矛盾が無ければ、左側のi番目の点と右側のj番目の間に辺があるとする。この二部グラフに完全マッチが存在する時かつその時に限り、マトリックスが存在する。完全マッチは複数存在する場合があり、この問題では辞書順最小の答えを返す必要がある。そこで、左上の?から順に、マトリックスが存在するならば0を、そうでなければ1を割り当てていく。O(C⁵)。

#include <string>
#include <vector>
using namespace std;

int R, C;

//  最大流
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);
}

bool valid( vector <string> rows, vector <string> columns )
{
    vector<vector<bool> > E( C, vector<bool>(C) );

    for ( int i=0; i<C; i++ )
    for ( int j=0; j<C; j++ )
    {
        bool f = true;
        for ( int k=0; k<R&&f; k++ )
            if ( rows[k][i]!='?' && columns[j][k]!='?' &&
                 rows[k][i]!=columns[j][k] )
                f = false;
        E[i][j] = f;
    }

    return bipartite(E)==C;
}

class P8XMatrixRecovery{public:
vector <string> solve( vector <string> rows, vector <string> columns )
{
    R = (int)rows.size();
    C = (int)columns.size();
    
    for ( int y=0; y<R; y++ )
    for ( int x=0; x<C; x++ )
    if ( rows[y][x]=='?' )
    {
        rows[y][x]='0';
        if ( !valid(rows,columns) )
            rows[y][x]='1';
    }

    return rows;
}};