Since the original problem is in another language, I will just translate it into English(may not be as “descriptive”).
Problem Description: The Wolf King wants to catch Rabbits, a given graph is listed below.
The Rabbits live in (1,1), the northwest corner, and they want to go to the southeast corner. The Wolf King needs to arrange wolves standing at the roads(undirected edges) in order to catch them. Specifically, K wolves are needed in order catch K Rabbits. Please output the minimum number of wolves that the Wolf King needs to arrange in order to catch ALL Rabbits.
Input Format:
N,M represents the height and width of the grids.
The following N lines with M – 1 numbers per line represent the number of Rabbits in the horizontal roads.
The following N – 1 lines with M numbers per line represent the number of Rabbits in the vertical roads.
The following N – 1 lines with M – 1 numbers per line represent the number of Rabbits in the tilted roads.
Output Format:
One line with the minimum number of wolves needed.
Sample Input:
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
Sample Output:
14
Solution: This is one problem that requires to calculate the minimum-cut of the graph. One useful formula for this one is that Maximum Flow = Minimum-Cut, so we can use Dinic Algorithm to get the answer. However, in the original website, the memory limit is 162MB, which will leads to MLE. With further studying, we found that the minimum-cut problem can be transformed into a shortest-path problem in its dual, I will update that solution later. I don’t know why it works for now.
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stdio.h>
#include <queue>
using namespace std;
const int maxn = 1e6 + 10;
#define inf 0x7ffffff
struct edge{
int from,to,cap,flow;
edge(int a = 0,int b = 0,int c = 0,int d = 0):from(a),to(b),cap(c),flow(d){};
};
vector<edge> es;
vector<int> G[maxn];
int dis[maxn],cur[maxn];
bool vis[maxn];
int N,M,S,T;
void addedge(int from,int to,int cap){
es.push_back(edge(from,to,cap,0));
es.push_back(edge(to,from,cap,0));
int m = es.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool bfs(){
queue<int> q;
memset(vis,0,sizeof(vis));
dis[S] = 0;
vis[S] = 1;
q.push(S);
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = 0; i < G[u].size(); i++){
edge e = es[G[u][i]];
if(e.cap > e.flow && !vis[e.to]){
vis[e.to] = 1;
dis[e.to] = dis[u] +1;
q.push(e.to);
}
}
}
return vis[T];
}
int dfs(int x,int a){
if(x == T || !a) return a;
int f,flow = 0;
for(int &i = cur[x]; i < G[x].size(); i++){
edge &e = es[G[x][i]];
edge &er = es[G[x][i] ^ 1];
if(dis[e.to] == dis[x] + 1 && (f = dfs(e.to,min(a,e.cap - e.flow))) > 0){
e.flow += f;
er.flow -= f;
flow += f;
a -= f;
if(!a) break;
}
}
return flow;
}
int mxflow(){
int ans = 0;
while(bfs()){
memset(cur,0,sizeof(cur));
ans += dfs(S,inf);
}
return ans;
}
inline int id(int i,int j){
return (i - 1) * M + j;
}
int main(){
scanf("%d%d",&N,&M);
S = id(1,1), T = id(N,M);
for(int i = 1; i <= N; i++){
for(int j = 1; j < M; j++){
int cap;
scanf("%d",&cap);
addedge(id(i,j),id(i,j + 1),cap);
}
}
for(int i = 1; i < N; i++){
for(int j = 1; j <= M; j++){
int cap;
scanf("%d",&cap);
addedge(id(i,j),id(i + 1,j),cap);
}
}
for(int i = 1; i < N; i++){
for(int j = 1; j < M; j++){
int cap;
scanf("%d",&cap);
addedge(id(i,j),id(i + 1,j + 1),cap);
}
}
printf("%d\n",mxflow());
return 0;
}
SPFA Solution: TO BE CONTINUED….