l悟空号将会在t秒以后沉入海底，那时船上所有的人将会死亡(包括t秒时也不能生存)。但是，，在某些房间中会有一些救生设备（不一定只有一个），人可以花费1分钟的时间走到相邻的另外四个房间。如果船上的人获得这些救生设备那么他们将会存活下来,请找出最大能存活的人数.

思路：建立源点跟汇点，将存在需要救援的房间与源点相连，容量为该房间的人数。将存在救生设备的房间与汇点相连，容量为救生设备的数目。中间点则考虑在t分钟内是否能够到达进行连边即可。

AC代码：#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<iostream> using namespace std; const int maxn = 10000 + 50; const int INF = 1e9; struct Edge { int from, to, cap, flow; }; struct Dinic { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init(int n) { this->n = n; for(int i=0; i<=n; ++i) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back((Edge) { from, to, cap, 0 }); edges.push_back((Edge) { to, from, 0, 0 }); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof vis ); queue<int> Q; Q.push(s); vis[s] = 1; d[s] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i=0; i<G[x].size(); ++i) { Edge& e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if(x==t || a==0) return a; int flow = 0, f; for(int& i=cur[x]; i<G[x].size(); ++i) { Edge& e = edges[G[x][i]]; if(d[x]+1==d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow)))>0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a==0) break; } } return flow; } int MaxFlow(int s, int t) { this->s = s; this->t = t; int flow = 0; while(BFS()) { memset(cur, 0, sizeof cur ); flow += DFS(s, INF); } return flow; } }; Dinic solve; int mtx[50][50]; int dist(int x1, int y1, int x2, int y2) { return abs(x1-x2) + abs(y1-y2); } int main() { #ifdef LOCAL_DEFINE freopen("in.cpp", "r", stdin); freopen("out.cpp", "w", stdout); #endif // LOCAL_DEFINE int n, tt, x; int s, t; while(~scanf("%d%d", &n, &tt)) { int lmt = n*n; s = lmt*2 + 1; t = lmt*2 + 2; solve.init(t+2); for(int i=0; i<n; ++i) { for(int j=0; j<n; ++j) { scanf("%d", &mtx[i][j]); if(mtx[i][j]>0) { solve.AddEdge( s, n*i+j, mtx[i][j]); } } } for(int i=0; i<n; i++) for(int j=0; j<n; j++) { scanf("%d",&x); if(x>0) { int u = n*i+j + lmt; solve.AddEdge(u, t, x); for(int i1=0; i1<n; ++i1) for(int j1=0; j1<n; ++j1) if(mtx[i1][j1]>0 && dist(i1, j1, i, j)<=tt){ int v = n*i1 + j1; solve.AddEdge(v, u, INF); } } } int ans = solve.MaxFlow(s, t); printf("%d\n", ans); } return 0; }