#include #include #include #include #include #include #include #include #include using namespace std; typedef struct{ int to; int cap; int rev; }edge; // node v : distance from s => level[v] void bfs(vector > &G, vector &level, int s){ fill(level.begin(), level.end(), -1); queue q; q.push(s); level[s] = 0; while(!q.empty()){ int e=q.front(); q.pop(); for(int i=0; i 0 && level[G[e][i].to] < 0){ level[G[e][i].to] = level[e] + 1; q.push(G[e][i].to); } } } } int dfs(vector > &G, vector &level, vector &used, vector &iter, int s, int f, int t){ if(s==t) return f; else{ //iter[e] : done searching from v[0] to v[ iter[e]-1 ] for(int &i=iter[s]; i 0 && level[s] < level[ G[s][i].to ]){ int d = dfs(G, level, used, iter, G[s][i].to, min(f, G[s][i].cap), t); if(d>0){ G[s][i].cap -= d; G[ G[s][i].to ][ G[s][i].rev ].cap += d; return d; } } } return 0; } } int dinic_maxflow(vector > &G, int s, int t){ const int INF = 100000000; int flow=0; while(true){ vector level(G.size(), -1); vector iter(G.size(), 0); vector used(G.size(), false); bfs(G, level, s); if(level[t] < 0) return flow; //unable to achieve to t while(true){ int f = dfs(G, level, used, iter, s, INF, t); if(f==0) break; else flow += f; } } } void add_edge(vector > &G, int from, int to, int cap){ G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].push_back((edge){from, 0, (int)G[from].size() - 1}); } int main(){ int n,m; cin >> n >> m; vector v(n); for(int i=0; i> v[i]; } // s -> w -> b -> t vector< vector > G(n*m + 2); int s = n*m; int t = n*m+1; int cnt_w = 0; int cnt_b = 0; for(int i=0; i