網絡流24題(九)
九、方格取數問題
題目描述
有一個 \(m\) 行 \(n\) 列的方格圖，每個方格中都有一個正整數。現要從方格中取數，使任意兩個數所在方格沒有公共邊，且取出的數的總和最大，請求出最大的和。
輸入格式
第一行是兩個用空格隔開的整數，分别代表方格圖的行數 \(m\) 和列數 \(n\)。
第 \(2\) 到第 \((m + 1)\) 行，每行 \(n\) 個整數，第 \((i + 1)\) 行的第 \(j\) 個整數代表方格圖第 \(i\) 行第 \(j\) 列的的方格中的數字 \(a_{i, j}\)。
輸出格式
輸出一行一個整數，代表和最大是多少。
PS:這個傻逼題目\(m\)行\(n\)列，我的代碼是\(n\)行\(m\)列的
題解
模型：
二分圖最大權獨立集，這個問題等價于求二分圖最小權覆寫集的補集，然後後者可以建圖用最小割求。
下面解釋一下，最小權覆寫集和最大權獨立集。
覆寫集：在一張圖上選若幹個點，這些點滿足他們的鄰邊覆寫整張圖，那麼這些點就是覆寫集，最小覆寫集就是點數最少的覆寫集合，最小權覆寫集就是如果我們給上點權，我們求出的權值和最小的覆寫集合。
獨立集：在一張圖上選若幹個點，這些點滿足兩兩之間沒有邊相連，互相獨立，我們稱這個點集合為獨立集，當這個集合點數最多的時候就是最大獨立集，如果給上點權，權值和最大的就是最大獨立集。
覆寫集與獨立集：如果\(V\)是一個覆寫集，那麼滿足所有邊都有一個點至少在\(V\)集合中，那麼顯然，剩下的所有點都是不相連的，是以\(V\)的補集\(V'\)就是獨立集，同樣的最小權覆寫集的補集就是最大全獨立集。
是以我們知道，如果我們要求最大權獨立集可以考慮先求最小權覆寫集。
那麼如何求最小權覆寫集呢？
\(Amber\)胡伯濤在論文《最小割模型在資訊學競賽中的應用》給了一個十厘清晰的思考過程：
回顧與此模型相關的模型。簡化權的條件後，可以借鑒的是二分圖比對的最大流解法。
它加入了額外的源 \(s\)和彙 \(t\) ，将比對以一條條\(s-u-v-t\)形式的流路徑“串聯”起來。比對的限制是在點上，恰當地利用了流的容量限制。而點覆寫集的限制在邊上，最小割是最大流的對偶問題，對偶往往是将問題的性質從點轉邊，從邊轉點。可以嘗試着轉化到最小割模型。
在這個思路的啟發下，我們開始考慮最小割和覆寫集關系。
建圖的時候參考二分圖比對時的建圖，建立一個源點\(s\)和一個彙點\(t\),不難發現二分圖中的每一條邊\((u,v)\)都對應一條\(s-u-v-t\)的路徑，在這樣的一條路徑當中勢必會有一條邊存在割中。
根據割的定義，割會做到這樣一件事情：取走割中的所有邊，所有路徑不連通。
所有路徑？再聯系之前說到一句每一條邊\((u,v)\)對應一條\(s-u-v-t\)的路徑，這樣的話我們也找到了所有的邊。這與覆寫集想要做的事情一模一樣。
現在要求的是覆寫集，我們的注意力應該要放在點上，假設選擇了\(u-v\)這樣的邊放在割中不能展現我們對點的選取，是以我們人為的讓\(u-v\)這樣的邊容量限制為\(inf\)，這樣我們邊的選取就是隻會在\(s-u\)和\(v-t\)之間進行。
這樣我們就發現,覆寫集與割是一一對應的，是以最小覆寫集就是最小割。
最後就是給上權值，稍加思考就發現其實和之前并沒有什麼不同，隻是建圖時邊的容量略加修改即可。
求最大獨立集即是求最小覆寫集的補集。
建圖與實作：
整理下思緒：
代碼
#include <iostream>
#include <queue>
#include <cstring>
#define ll long long
const ll N = 5e3+50,M = 5e4+50;
const ll inf = 0x3f3f3f3f;
using namespace std;
ll head[N] = {0}, cnt = 1;
struct Edge{
ll to,w,nxt;
}edge[M*2];
void add(ll u,ll v,ll w){
edge[++cnt] = {v,w,head[u]};
head[u] = cnt;
}
void add2(ll u,ll v,ll w){
//cout<<"u:"<<u<<"v:"<<v<<endl;
add(u,v,w);
add(v,u,0);
}
ll s,t,lv[N],cur[N];
bool bfs(){
memset(lv,-1,sizeof lv);
lv[s] = 0;
memcpy(cur,head,sizeof head);
queue<ll> q;q.push(s);
while(!q.empty()){
ll p = q.front();q.pop();
for(ll eg = head[p];eg;eg = edge[eg].nxt){
ll to = edge[eg].to,vol = edge[eg].w;
//cout<<"from: "<<p<<" to:"<<to<<" vol: "<<vol<<endl;
if(vol > 0 && lv[to] == -1){
lv[to] = lv[p]+1;
q.push(to);
}
}
}
return lv[t] != -1;
}
ll dfs(ll p = s,ll flow = inf){
if(p == t) return flow;
ll rmn = flow;
for(ll &eg = cur[p];eg;eg = edge[eg].nxt){
if(!rmn) break;
ll to = edge[eg].to,vol = edge[eg].w;
if(vol > 0 && lv[to] == lv[p]+1){
ll c = dfs(to,min(vol,rmn));
rmn -= c;
edge[eg].w -= c;
edge[eg^1].w += c;
}
}
return flow-rmn;
}
ll dinic(){
ll ans = 0;
while(bfs()) ans += dfs();
return ans;
}
ll n,m,chess[N][N];
int main() {
ll sum = 0;
cin>>n>>m;
s = 0,t = n*m+1;
ll x = 0;
for(ll i = 1;i <= n;i++) {
for (ll j = 1; j <= m; j++) {
x++;
cin >> chess[i][j];
sum += chess[i][j];
if((i&1) == (j&1))add2(s, x, chess[i][j]);
else add2(x,t,chess[i][j]);
}
}
x = 0;
for(ll i = 1;i <= n;i++){
for(ll j = 1;j <= m;j++) {
x++;
if((i&1) != (j&1)) continue;
if (i != 1)add2(x, x - m, inf);
if (i != n)add2(x, x + m, inf);
if (j != 1)add2(x, x - 1, inf);
if (j != m)add2(x, x + 1, inf);
}
}
cout<<sum-dinic()<<endl;
return 0;
}