該題是一道經典的求最大點權獨立集問題的題目 。 關於定義我就不多說了 。 說一下幾個重要的關系 ：
1.最大流 = 最小割 = 最小點權覆蓋集 = sum - 最大點權獨立集 。
因此，該題其實還可以用最小割來做，思想是相同的 。
因為我們不能取相鄰的數字，所以很容易聯想到最小割 。
那麼我們可以先給每個格子編號1或2，形成二分圖。 然後由1到2連邊 。容量INF，與源點和匯點相連的容量為對應點的值。
這樣，求得的最大流也是最小割。 最大點權獨立集 = sum - 最小割 。
需要注意的是：上述的一切都是基於這樣一個事實：圖是二分圖 。因此我們必須要構建一個單向連通的圖，不能產生自環，這個在建圖的時候要重視，不然會莫名WA 。
細節參見代碼：
#includeusing namespace std; const int maxn = 20*20*2; typedef long long ll; const int INF = 1000000000; int T,n,m,id1[55][55],id2[55][55]; struct Edge { int from, to, cap, flow; }; bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to); } struct Dinic { int n, m, s, t; vector old; vector edges; // 邊數的兩倍 vector G[maxn]; // 鄰接表，G[i][j]表示結點i的第j條邊在e數組中的序號 bool vis[maxn]; // BFS使用 int d[maxn]; // 從起點到i的距離 int cur[maxn]; // 當前弧指針 void init(int 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 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; } }g; int a[55][55]; int dx[] = {0,1,0,-1}; int dy[] = {1,0,-1,0}; int main() { while(~scanf(%d,&n)) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf(%d,&a[i][j]); int s[21][21] = {0}, sum = 0; s[1][1] = 1; g.init(n*n+5); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(s[i][j] == 1) { //編號，建立二分圖 for(int k=0;k<4;k++) { int x = dx[k]+i, y = dy[k]+j; if(x < 1 || x > n || y < 1 || y > n || s[x][y] != 0) continue; s[x][y] = 2; } } else { for(int k=0;k<4;k++) { int x = dx[k]+i, y = dy[k]+j; if(x < 1 || x > n || y < 1 || y > n || s[x][y] != 0) continue; s[x][y] = 1; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { sum += a[i][j]; if(s[i][j] == 1) { //由1集合的點向2集合的點連邊 int id = (i-1)*n + j ; g.AddEdge(0,id,a[i][j]);//這樣，最小割的意義就是割去1集合的點或割去2中的某點 for(int k=0;k<4;k++) { int x = dx[k]+i, y = dy[k]+j; if(x < 1 || x > n || y < 1 || y > n ) continue; g.AddEdge(id,(x-1)*n+y,INF); } } else { //不可反向連邊，會形成環。 int id = (i-1)*n + j; g.AddEdge(id,n*n+1,a[i][j]); } } printf(%d ,sum - g.Maxflow(0,n*n+1)); } return 0; }
