算法思想概述
本題是一道最大權閉合子圖模型，應用的算法為最大流(BFS增廣即可)，定理為最大流最小割定理，輔助算法為拓撲排序。
問題初始模組化
首先我們我建立圖論模型，把每個植物當做一個頂點，植物攜帶的資源數目為頂點的權值。如果一個植物b在另一個植物a的攻擊範圍内，連接配接一條有向邊<a,b>，表示a可以保護b。由于僵屍從右向左進攻，可以認為每個植物都被它右邊相鄰的植物保護，對于每個植物a（除最左邊一列），向其左邊的相鄰植物b，連接配接一條有向邊<a,b>。
由本題樣例就可以發現，有一些植物是互相依賴的，于是我們可以進行算法實作的第一步：
1.使用拓撲排序去除圖中的環，進而使圖得到簡化。
最大權閉合子圖
進行算法的第二步。
### 2.對第一步中得到的圖進行轉置操作(把所有邊反向)，進而得到最大子權閉合圖。
樣例的圖經過拓撲排序和轉置操作後如下：
其中最大權閉合子圖為(1,2,4)
下面進行算法實作的第3、4步：
3.最大權閉合子圖的網絡流模組化：
(1). 建立附加源S和附加彙T。
(2). 圖中原有的轉置後的邊容量設為∞。
(3). 從S向每個權值為正的點連接配接一條容量為該點權值的有向邊。
(4). 從每個權值不為正的點向T連接配接一條容量為該點權值絕對值的有向邊。
模組化後圖如下：
4.求解：求S到T的最大流Maxflow，最大權閉合子圖的權值就是(所有正權點權值之和 – Maxflow)，也就是需要輸出的答案。
我們可以這樣想，當我們從s到t的一條路上 得到了Ws 花費了min(Ws,Wt）,如果Wt>Ws 得到收益為 Ws - Ws = 0（相當于不走）;如果Wt<Ws,收益為Ws - Wt(賺錢了！！！);
而所有正權點權值之和就是
$\begin{matrix}\underbrace{Ws1+Ws2+\cdots+Wsn}\n\end{matrix}=\sum\limits_{i=1}^nW_i$
而S到T的最大流Maxflow就是
$\begin{matrix}\underbrace{min(Wt1,Ws1)+min(Wt2,Ws2)+\cdots+min(Wtn,Wsn)}\n\end{matrix}=\sum\limits_{i=1}^nmin(Wti,Wsi)$
$ $
$ ans = \sum\limits_{i=1}^nW_i-\sum\limits_{i=1}^nmin(Wti,Wsi) $
代碼
#include<bits/stdc++.h>
#define POINT(X, Y) ((X) * 31 + (Y))
using namespace std;
const int MAXN = POINT(30,30)+10;
const int INF = 1<<28;
int read(){
int flag=1,sum=0;char c;
for(;c>'9'||c<'0';c=getchar())if(c=='-')flag=-1;
for(;c<='9'&&c>='0';c=getchar())sum=(sum<<3)+(sum<<1)+c-'0';
return flag*sum;
}
struct node{
int to, val;
int next=-1;
}edge[MAXN*MAXN*2];int top=1, head[MAXN];
vector<int> out[MAXN];int vis[MAXN],in[MAXN],score[MAXN];
int dep[MAXN],s=MAXN-1,t=MAXN-2;int n,m;
void add(int u, int v, int val) {
top++;edge[top].to = v;edge[top].val = val;edge[top].next = head[u];head[u] = top;
top++;edge[top].to = u;edge[top].val = 0;edge[top].next = head[v];head[v] = top;
} dinic部分
int bfs()
{
memset(dep,0,sizeof(dep));
queue<int> q;
while(!q.empty())
q.pop();
q.push(s);
dep[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dep[v]==0&&edge[i].val>0)
{
dep[v]=dep[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int dfs(int u,int flow)
{
if(u==t)
return flow;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dep[v]==dep[u]+1&&edge[i].val>0)
{
int k=dfs(v,min(edge[i].val,flow));
if(k==0)
{
dep[v]=0;
}
else
{
edge[i].val-=k;
edge[i^1].val+=k;
return k;
}
}
}
return 0;
}
int dinic(){
int flow,maxflow=0;
while(bfs())
{
while(flow=dfs(s,INF))
{
maxflow+=flow;
}
}
return maxflow;
} 構造圖部分
void topsort(){
queue<int> q;
//memset(vis,0,sizeof(0));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(in[POINT(i,j)]==0){
q.push(POINT(i,j));
vis[POINT(i,j)]=1;
}
}
while(!q.empty()){
int u=q.front();q.pop();
int len=out[u].size();
for(int i=0;i<len;i++){
int v=out[u][i];
in[v]--;
if(vis[v]==0&&in[v]==0){
q.push(v);
vis[v]=1;
}
}
}
}
int main(){
// freopen("B.in","r",stdin);
// freopen("B.out","w",stdout);
n=read();m=read();
for(int i=1;i<=n;i++){
int flag,x,y;
for(int j=1;j<=m;j++){
score[POINT(i,j)]=read();
flag=read();
while(flag--){
x=read();y=read();x++,y++;
out[POINT(i,j)].push_back(POINT(x,y));
in[POINT(x,y)]++;
}
if(j < m) {
out[POINT(i, j + 1)].push_back(POINT(i, j));
in[POINT(i, j)] ++;
}
}
}
topsort();
int sum=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(in[POINT(i,j)]==0){
int u = POINT(i, j);
if(!vis[u])
continue;
if(score[u] >= 0) {
add(s,u,score[u]);
sum += score[u];//cout<<sum<<" ";
} else {
add(u,t,-score[u]);
}
for(int k = 0; k < out[u].size(); k ++) {
int v = out[u][k];
if(vis[v]) {
add(v, u, INF);
}
}
}
}
}
cout<<sum-dinic();
return 0;
} 轉載于:https://www.cnblogs.com/starconstant/p/11154014.html