734. [網絡流24題] 方格取數問題 二分圖點權最大獨立集/最小割/最大流

?問題描述：
在一個有m*n 個方格的棋盤中，每個方格中有一個正整數。現要從方格中取數，使任
意2 個數所在方格沒有公共邊，且取出的數的總和最大。試設計一個滿足要求的取數算法。
?編程任務：
對于給定的方格棋盤，按照取數要求編程找出總和最大的數。
?數據輸入：
由文件grid.in提供輸入數據。文件第1 行有2 個正整數m和n，分別表示棋盤的行數
和列數。接下來的m行，每行有n個正整數，表示棋盤方格中的數。

【問題分析】

二分圖點權最大獨立集，轉化為最小割模型，從而用最大流解決。

【建模方法】

首先把棋盤黑白染色，使相鄰格子顏色不同，所有黑色格子看做二分圖X集合中頂點，白色格子看做Y集合頂點，建立附加源S匯T。

1、從S向X集合中每個頂點連接一條容量為格子中數值的有向邊。
2、從Y集合中每個頂點向T連接一條容量為格子中數值的有向邊。
3、相鄰黑白格子Xi,Yj之間從Xi向Yj連接一條容量為無窮大的有向邊。

求出網絡最大流，要求的結果就是所有格子中數值之和減去最大流量。

【建模分析】

這是一個二分圖最大點權獨立集問題，就是找出圖中一些點，使得這些點之間沒有邊相連，這些點的權值之和最大。獨立集與覆蓋集是互補的，求最大點權獨立集可以轉化為求最小點權覆蓋集（最小點權支配集）。最小點權覆蓋集問題可以轉化為最小割問題解決。結論:最大點權獨立集 = 所有點權 - 最小點權覆蓋集 = 所有點權 - 最小割集 = 所有點權 - 網絡最大流。

對于一個網絡，除去冗余點（不存在一條ST路徑經過的點），每個頂點都在一個從S到T的路徑上。割的性質就是不存在從S到T的路徑，簡單割可以認為割邊關聯的非ST節點為割點，而在二分圖網絡流模型中每個點必關聯到一個割點（否則一定還有增廣路，當前割不成立），所以一個割集對應了一個覆蓋集（支配集）。最小點權覆蓋集就是最小簡單割，求最小簡單割的建模方法就是把XY集合之間的變容量設為無窮大，此時的最小割就是最小簡單割了。

/* * Problem: 線性規劃與網絡流24題 #9 方格取數問題* Author: Guo Jiabao* Time: 2009.6.27 19:06* State: Solved* Memo: 網絡最大流 二分圖點權最大獨立集
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXL=50,MAXN=50*50,MAXM=MAXN*8,INF=~0U>>1;
const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
struct edge
{edge *next,*op;int t,c;
}*V[MAXN],*P[MAXN],ES[MAXM],*Stae[MAXN];
int N,M,S,T,C,EC,Ans,Maxflow,Total;
int Lv[MAXN],Stap[MAXN],Map[MAXL][MAXL];
inline void addedge(int a,int b,int c)
{ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c;ES[++EC].next = V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0;V[a]->op = V[b]; V[b]->op = V[a];
}
void init()
{int i,j,k,c;freopen("grid.in","r",stdin);freopen("grid.out","w",stdout);scanf("%d%d",&M,&N);S=0; T=N*M+1;for (i=1;i<=M;i++){for (j=1;j<=N;j++){scanf("%d",&c);Total += c;Map[i][j] = ++C;if ((i+j)%2==0)addedge(S,C,c);elseaddedge(C,T,c);}}for (i=1;i<=M;i++){for (j=1;j<=N;j++){if ((i+j)%2==0){for (k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if (x>=1 && x<=M && y>=1 && y<=N)addedge(Map[i][j],Map[x][y],INF);}}}}
}
bool Dinic_Label()
{int head,tail,i,j;Stap[head=tail=0]=S;memset(Lv,-1,sizeof(Lv));Lv[S]=0;while (head<=tail){i=Stap[head++];for (edge *e=V[i];e;e=e->next){j=e->t;if (e->c && Lv[j]==-1){Lv[j] = Lv[i]+1;if (j==T)return true;Stap[++tail] = j;}}}return false;
}
void Dinic_Augment()
{int i,j,delta,Stop;for (i=S;i<=T;i++)P[i] = V[i];Stap[Stop=1]=S;while (Stop){i=Stap[Stop];if (i!=T){for (;P[i];P[i]=P[i]->next)if (P[i]->c && Lv[i] + 1 == Lv[j=P[i]->t])break;if (P[i]){Stap[++Stop] = j;Stae[Stop] = P[i];}elseStop--,Lv[i]=-1;}else{delta = INF;for (i=Stop;i>=2;i--)if (Stae[i]->c < delta)delta = Stae[i]->c;Maxflow += delta;for (i=Stop;i>=2;i--){Stae[i]->c -= delta;Stae[i]->op->c += delta;if (Stae[i]->c==0)Stop = i-1;}}}
}
void Dinic()
{while (Dinic_Label())Dinic_Augment();
}
int main()
{init();Dinic();Ans = Total - Maxflow;printf("%d\n",Ans);return 0;
}

?