Artifact b357fd2040b9449a5148cbba3e66c95a567f84ea
#include <vector>
#include <string>
#include <iostream>
#include <cstring>
using namespace std;
static const int NV = 512;
typedef int flow;
typedef int vert;
typedef vert edge;
typedef vector<edge> edges;
typedef vector<edges> graph;
typedef flow flow_graph[NV][NV];
flow dinic_dfs( graph& G, flow_graph F, vert v, vert D,
int LV[], flow flow_in, int blocked[] )
{
flow flow_out = 0;
for(int i=0; i!=G[v].size(); ++i)
{
int u = G[v][i];
if( LV[v]+1==LV[u] && F[v][u] )
{
flow f = min(flow_in-flow_out, F[v][u]);
if( u==D || !blocked[u] && (f=dinic_dfs(G,F,u,D,LV,f,blocked)) )
{
F[v][u] -= f;
F[u][v] += f;
flow_out += f;
if( flow_in == flow_out ) return flow_out;
}
}
}
blocked[v] = (flow_out==0);
return flow_out;
}
flow dinic( graph& G, flow_graph F, vert S, vert D )
{
for( flow total=0 ;; ) {
int LV[NV] = {0};
vector<int> Q(1, S);
for(int lv=1; !Q.empty(); ++lv)
{
vector<int> Q2;
for(int i=0; i!=Q.size(); ++i)
{
edges& ne = G[Q[i]];
for(int j=0; j!=ne.size(); ++j)
if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
LV[ne[j]]=lv, Q2.push_back(ne[j]);
}
Q.swap(Q2);
}
if( !LV[D] )
return total;
int blocked[NV] = {};
total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked );
}
}
struct DancingParty
{
int maxDances(vector<string> likes, int k)
{
int n = likes.size();
#define SRC 0
#define DST 1
#define L(i) 2+n*0+i
#define R(i) 2+n*1+i
#define YL(i) 2+n*2+i
#define NL(i) 2+n*3+i
#define YR(i) 2+n*4+i
#define NR(i) 2+n*5+i
graph G(2+n*6);
// Graph
for(int i=0; i<n; ++i) {
G[SRC ].push_back(L(i)); G[L(i) ].push_back(SRC);
G[L(i)].push_back(YL(i)); G[YL(i)].push_back(L(i));
G[L(i)].push_back(NL(i)); G[NL(i)].push_back(L(i));
G[DST ].push_back(R(i)); G[R(i) ].push_back(DST);
G[R(i)].push_back(YR(i)); G[YR(i)].push_back(R(i));
G[R(i)].push_back(NR(i)); G[NR(i)].push_back(R(i));
for(int j=0; j<n; ++j)
if( likes[i][j] == 'Y' )
G[YL(i)].push_back(YR(j)), G[YR(j)].push_back(YL(i));
else
G[NL(i)].push_back(NR(j)), G[NR(j)].push_back(NL(i));
}
for(int M=1; M<=n; ++M) {
// Flow
flow_graph F = {};
for(int i=0; i<n; ++i) {
F[SRC][L(i)] = M;
F[L(i)][YL(i)] = M;
F[L(i)][NL(i)] = k;
F[R(i)][DST] = M;
F[YR(i)][R(i)] = M;
F[NR(i)][R(i)] = k;
for(int j=0; j<n; ++j)
if( likes[i][j] == 'Y' )
F[YL(i)][YR(j)] = 1;
else
F[NL(i)][NR(j)] = 1;
}
// Maxflow
if( dinic(G, F, SRC, DST) < M*n )
return M-1;
}
return n;
}
};