1. #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define RE(x) (x)^1#define INF 0x3fffffff#define MAXN 205using namespace std;int N, M, G[MAXN][MAXN], dis[MAXN*MAXN];int dir[2][2] = { 0, 1, 1, 0};int idx, head[MAXN*MAXN];const int sink = MAXN*MAXN-1, source = MAXN*MAXN-2;struct Edge{ int v, cap, next;}e[MAXN*MAXN*4];void init(){ idx = -1; memset(head, 0xff, sizeof (head));} int to(int x, int y){ return (x-1)*M+(y-1);} void insert(int a, int b, int c){ ++idx; e[idx].v = b, e[idx].cap = c; e[idx].next = head[a], head[a] = idx;} bool judge(int x, int y){ if (x < 1 || x > N || y < 1 || y > M) { return false; } return true;} void getint(int &t){ char c; while (c = getchar(), c < '0' || c > '9') ; t = c - '0'; while (c = getchar(), c >= '0' && c <= '9') { t = t * 10 + c - '0'; }} void check(int x, int y){ int xx, yy; if (G[x][y] == 1) { insert(to(x, y), sink, INF); insert(sink, to(x, y), 0); } else if (G[x][y] == 2) { insert(source, to(x, y), INF); insert(to(x, y), source, 0); } for (int i = 0; i < 2; ++i) { xx = x + dir[i][0], yy = y + dir[i][1]; if (judge(xx, yy)) { insert(to(x, y), to(xx, yy), 1); insert(to(xx, yy), to(x, y), 1); } }}bool bfs(){ int pos; queue
                  
                   q; memset(dis, 0xff, sizeof (dis)); dis[source] = 0; q.push(source); while (!q.empty()) { pos = q.front(); q.pop(); for (int i = head[pos]; i != -1; i = e[i].next) { if (dis[e[i].v] == -1 && e[i].cap > 0) { dis[e[i].v] = dis[pos]+1; q.push(e[i].v); } } } return dis[sink] != -1;}int dfs(int u, int flow){ if (u == sink) { return flow; } int tf = 0, sf; for (int i = head[u]; i != -1; i = e[i].next) { if (dis[u]+1 == dis[e[i].v] && e[i].cap > 0 && (sf = dfs(e[i].v, min(flow-tf, e[i].cap)))) { e[i].cap -= sf, e[RE(i)].cap += sf; tf += sf; if (tf == flow) { return flow; } } } if (!tf) { dis[u] = -1; } return tf;}int dinic(){ int ans = 0; while (bfs()) { ans += dfs(source, INF); } return ans;}int main(){ int ca = 0; while (scanf("%d %d", &N, &M) == 2) { init(); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { scanf("%d", &G[i][j]); // getint(G[i][j]); } } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { check(i, j); } } printf("%d\n",dinic()); } return 0;}
                  
                 
                
               
              
             
            

   题中要求出至少要多少个围墙才能把狼阻挡在羊群活动的范围外，解决该题的方法就是以狼为源点，羊会汇点，求最小割即为最少的围墙数。出源点和汇点外其余两个网格之间的权值都是1，表示有一头狼能够通过网格走到羊群中去。

   递归写的sap一直超时，最后还是递归的Dinic过了，无语了。不会非递归伤不起啊。