### xuanquang1999's blog

By xuanquang1999, history, 2 years ago, ,

I'm trying to solve B — Safety Grade from SEERC 2011. My solution is to iterate over all the pair of vertices in the graph (let's call the pair (s, t)), calculate the maximum flow (using Edmond-Karp algorithm) from s to t, and the answer is the minimum value among these max flow value. Also, notice that the answer can't exceed the minimum of each vertex's degree (which won't exceed ), so each maximum flow calculation will be done in less than BFS. So, the overall complexity of the algorithm is O(n * m2).

I don't know why my solution got Runtime Error (that's the last verdict I would expect to get in this problem). I ran stress-testing for half an hour, but couldn't find any wrong test case. I need help finding what's wrong with my implementation. Thanks in advance.

• 0

 » 15 months ago, # |   0 Did you manage to solve the problem ? I am also trying to solve the same problem but got no idea how to do it. If you solved the problem, can you please help me by posting your source code or giving a brief explanation of your approach. Thanks.
 » 15 months ago, # |   +5 I had the same RE as you. The problem is while (scanf("%d%d", &n, &m) != EOF). To get AC, you should write while (scanf("%d%d", &n, &m) == 2). Why? Maybe because they have wrong input files.
•  » » 14 months ago, # ^ |   0 Can you please share your source code? I did not find any on the internet. Doing the modifications you suggested in the source code by the author of this blog still yields a WA on live archive oj.
•  » » » 14 months ago, # ^ |   0 click#include using namespace std; const int N = 105; const int INF = 0x3f3f3f3f; const int Source = 0; int Sink = N - 3; struct edge { int to, flow; }; int i, j, n, m, ptr[N], dist[N], q[N], x, y, rs; vector lda[N]; vector E; void clearNetwork() { E.clear(); rs = INF; for(int i = 0; i < N; ++i) lda[i].clear(); } void addEdge(int x, int y, int flow) { E.push_back({y, flow}); E.push_back({x, 0}); lda[x].push_back(E.size() - 2); lda[y].push_back(E.size() - 1); } bool bfs() { int st = 0, dr = 0; memset(dist, INF, sizeof(dist)); for(q[st] = Source, dist[Source] = 0; st <= dr; ++st) for(auto it : lda[q[st]]) if(E[it].flow && dist[E[it].to] > dist[q[st]] + 1) { dist[E[it].to] = dist[q[st]] + 1; q[++dr] = E[it].to; } return dist[Sink] != INF; } int dfs(int x, int flow) { if(!flow || x == Sink) return flow; for(; ptr[x] < lda[x].size(); ++ptr[x]) { int it = lda[x][ptr[x]]; if(E[it].flow <= 0 || dist[E[it].to] != dist[x] + 1) continue; int pushed = dfs(E[it].to, min(flow, E[it].flow)); if(pushed) { E[it].flow -= pushed; E[it ^ 1].flow += pushed; return pushed; } } return 0; } int dinic() { int flow = 0; while(bfs()) { memset(ptr, 0, sizeof(ptr)); while(int pushed = dfs(Source, INF)) flow += pushed; } return flow; } int main() { while(scanf("%d %d", &n, &m) == 2) { clearNetwork(); while(m--) { scanf(" (%d,%d)", &x, &y); addEdge(x, y, 1); addEdge(y, x, 1); } for(i = 1; i < n; ++i) { Sink = i; for(j = 0; j < E.size(); j += 2) E[j].flow = 1, E[j + 1].flow = 0; rs = min(rs, dinic()); } if(rs == INF) rs = 0; printf("%d\n", rs); } return 0; } 
•  » » » » 14 months ago, # ^ |   0 Thanks a lot. :) BTW, can this problem be solved by using edmonds-karp as well, or do we need dinic for it? Because the blog author's solution implements edmonds-karp. I tried using the same idea but got WAs or REs.
•  » » » » » 14 months ago, # ^ |   0 Sure, Edmons-Karp should be enough.