Acwing 2326：王者之剑（网格图之网络流最大权独立集）

太过爱你忘了你带给我的痛 2022-11-03 11:26 100阅读 0赞

### 原题链接 ###

传送门：[Acwing 2326：王者之剑][Acwing 2326]

### 题目大意 ###

给一个网格图，每个点是宝石的数量，现在从0秒开始可以从任意一个点作为起点开始走，每秒顺序执行下面三件事：1、拿走该点的宝石。2、如果当前是偶数秒，清空上下左右四个相邻的点的宝石。3、向上下左右四个相邻的点走一步或原地不动。问取得宝石数量最多是多少？

### 思路 ###

看到网格图，可能有人就会敏感的想到网络流了。我们要先分析一下取宝石的过程，会总结出**两个性质**：①我们只能在偶数秒取宝石。②不可能同时拿走相邻格子上的宝石。这两个性质不难证明，因为偶数秒会清空相邻的宝石，所以奇数秒时走到邻点是没有宝石的，同理，没法取走相邻点的宝石。这样看到性质二，我们就会想到[最大权独立集][Link 1]。我们给每个相邻的点之间建一条边，一条边上连的两个点不能同时取，这就是独立集，而每个点的宝石数量就是点权，我们要使点权和最大，这就是**最大权独立集**。所以不难证明取宝石的每一种合法方案就是一种独立集同时一种独立集就对应了一种取法，所以这就可以转换到最大权独立集来做。  
而我们将网格图中所有不相邻的点看成一个集合，剩下的点看成另一个集合，就会将网格图中的所有点分成两个集合，如下图。这样相邻点之间建的边一定是一个集合到另一个集合的边，这就是一个二分图了。于是我们就将原问题转化成了二分图的最大权独立集了。  
![二分][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]

### 代码详解 ###

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int N =  10010,M = 100010,INF = 0x3f3f3f3f;
    
    int n,m,s,t,cur[N],dis[N],tot;		//tot用来记总权值
    int e[M],ne[M],w[M],h[N],idx;
    int dx[4] = { -1,0,1,0},dy[4] = { 0,1,0,-1};
    
    int get(int i,int j)	//计算（i，j）点的序号，以行序为主序对点编号
    { 
    	return (i-1)*m+j;
    }
    
    void add(int a,int b,int c) 	//建图模板
    { 
    	e[idx] = b;
    	w[idx] = c;
    	ne[idx] = h[a];
    	h[a] = idx++;
    	e[idx] = a;
    	w[idx] = 0;
    	ne[idx] = h[b];
    	h[b] = idx++;
    }
    
    bool bfs() 		//dinic模板
    { 
    	queue<int> q;
    	memset(dis,-1,sizeof dis);
    	q.push(s);
    	dis[s] = 0;
    	cur[s] = h[s];
    	while(q.size())
    	{ 
    		int u = q.front();
    		q.pop();
    		for(int i = h[u];~i;i = ne[i])
    		{ 
    			int v = e[i];
    			if(dis[v] == -1 && w[i])
    			{ 
    				dis[v] = dis[u] + 1;
    				cur[v] = h[v];
    				if(v == t)
    					return 1;
    				q.push(v);
    			}
    		}
    	}
    	return 0;
    }
    
    int dfs(int u,int limit)
    { 
    	if(u == t)
    		return limit;
    	int flow = 0;
    	for(int i = cur[u];~i;i = ne[i])
    	{ 
    		int v = e[i];
    		cur[u] = i;
    		if(dis[v] == dis[u]+1 && w[i])
    		{ 
    			int minf = dfs(v,min(w[i],limit-flow));
    			w[i] -= minf;
    			w[i^1] += minf;
    			flow += minf;
    			if(flow == limit) 
    				return flow;
    		}
    	}
    	return flow;
    }
    
    int dinic()
    { 
    	int ans = 0;
    	while(bfs())
    		ans += dfs(s,INF);
    	return ans;
    }
    
    int main()
    { 
    	cin >> n >> m;
    	s = 0,t = n*m+1;	//设置源汇点
    	memset(h,-1,sizeof h);
    	for(int i = 1;i <= n;i++)
    	{ 
    		for(int j = 1;j <= m;j++)
    		{ 
    			int c;
    			cin >> c;
    			if(i+j & 1)	//将所有点分成两个集合
    			{ 
    				add(s,get(i,j),c);	//s到左边集合的点建一条容量为c的边
    				for(int k = 0;k < 4;k++)
    				{ 
    					int x = i+dx[k],y = j+dy[k];
    					if(x >= 1 && x <= n && y >= 1 && y <= m)	//看该点的上下左右邻点是否存在
    					add(get(i,j),get(x,y),INF);	//若存在，从该点向邻点建一条容量为正无穷的边
    				}
    			}
    			else	//另一个集合的点
    				add(get(i,j),t,c);	//从该点向t建一条容量为c的边
    			tot += c;	//tot计算总权值和
    		}
    	}
    	 
    	cout << tot-dinic() << endl;	//最大权独立集 = 总权值 - 最小权点覆盖集
     
    	return 0;
    }

[Acwing 2326]: https://www.acwing.com/problem/content/2328/
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/114164797
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]: /images/20221024/6af285d39f674f3a9a5551ff40c066e8.png