Hi,
I get a WA in MUDDY, used Edmonds Karp algorithm. I got an AC in QUEST4 using the same.
But in MUDDY only the mud has to be covered and not the grass, so I know this one is different from QUEST4.
But how do I do that?
Here is my code:
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define INF 1000000007
int c[110][110];
int f[110][110];
vector<int> graph [110];
int P[110];
int M[110];
int s(0), t, n, flow, v;
int a, b;
char S[55][55];
int BFS() {
memset(P, -1, sizeof(P));
memset(M, 0, sizeof(M));
P[s] = -2;
M[s] = INF;
queue<int> Q;
Q.push(s);
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(int i=0; i<graph[u].size(); i++) {
int to = graph[u][i];
if(P[to] == -1) {
if(c[u][to] - f[u][to] > 0) {
P[to] = u;
M[to] = min(M[u], c[u][to]-f[u][to]);
if(to == t) {
return M[t];
}
Q.push(to);
}
}
}
}
return 0;
}
int edmondsKarp() {
int maxFlow = 0;
while(true) {
flow = BFS();
if(flow == 0) break;
maxFlow += flow;
v = t;
while( v!=s ) {
int u = P[v];
f[u][v] += flow;
f[v][u] -= flow;
v = u;
}
}
return maxFlow;
}
int main() {
int test;
int m;
s = 0;
scanf("%d", &test);
while(test--) {
memset(c, 0, sizeof(c));
scanf("%d%d", &a, &b);
t = a+b+1;
for(int i=0; i<=t; i++) graph[i].clear();
for(int i=0; i<a; i++)
scanf("%s", S[i]);
for(int i=1; i<=a; i++) {
graph[0].push_back(i);
graph[i].push_back(0);
c[0][i] = 1;
}
for(int i=a+1; i<t; i++) {
graph[i].push_back(t);
graph[t].push_back(i);
c[i][t] = 1;
}
for(int i=0; i<a; i++)
for(int j=0; j<b; j++)
if(S[i][j] == '*') {
graph[i+1].push_back(a+j+1);
graph[a+j+1].push_back(i+1);
c[i+1][a+j+1] = 1;
}
memset(f, 0, sizeof(f));
printf("%d\n", edmondsKarp());
}
return 0;
}
Thank you.