【最大权闭合图】BZOJ1565-[NOI2009]植物大战僵尸

害怕地发现我以前写的Dinic几乎都是有错的……？？！！！

【题目大意】

（以下摘自popoqqq大爷）给定一个m*n的草坪，每块草坪上的植物有两个属性：1.啃掉这个植物，获得收益x(可正可负)2.保护(r,c)点的植物不被啃掉。任何一个点的植物存活时，它左侧的所有植物都无法被攻击，求最大收益。

【思路】

首先我们很容易发现，植物存活有一个依赖关系，显然是一个最大权闭合图，即从被保护者指向保护者（简单来说，就是只有保护者被吃掉的情况下，被保护者才有可能被吃掉）。

注意，如果构成了一个环，则不会被吃掉；此外，当前点指向直接或间接指向一个环，也不可能被吃掉。

那么怎么删除环和指向环的节点呢？这里有一个拓扑排序常用的小技巧：

把所有边反向，从入度为0的点开始拓扑排序，能抵达的点便是保留的点。

顺便放一个拓扑排序的模板：

 1 void Topology()
 2 {
 3     memset(usable,0,sizeof(usable));
 4     queue<int> que;
 5     for (int i=S;i<=T;i++)
 6         if (!into[i]) que.push(i);
 7     while (!que.empty())
 8     {
 9         int head=que.front();que.pop();
10         usable[head]=1;
11         if (score[head]>0) ans+=score[head];
12         for (int i=0;i<rE[head].size();i++)
13         {
14             int to=rE[head][i];
15             into[to]--;
16             if (!into[to]) que.push(to); 
17         }
18     }
19 }

【错误点】

一开始建图的时候正向边反向边傻傻没分清……

2016/7/29修改：突然我以前写的Dinic都是错的我要爆炸了！现在又优化了一下，更正详见注释里面。至于优化前后的效率差距：

呃……

  1 /*2016.7.29更正*/
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<vector>
  7 #include<queue>
  8 #define S 0
  9 #define T m*n+1
 10 using namespace std;
 11 const int MAXN=35;
 12 struct node
 13 {
 14     int to,pos,cap;
 15 };
 16 const int INF=0x7fffffff;
 17 vector<int> rE[MAXN*MAXN];
 18 vector<node> E[MAXN*MAXN]; 
 19 int score[MAXN*MAXN];
 20 int n,m,ans=0;
 21 int usable[MAXN*MAXN],into[MAXN*MAXN];
 22 int dis[MAXN*MAXN];
 23 
 24 void addedge(int u,int v,int w)
 25 {
 26     rE[v].push_back(u);
 27     into[u]++; 
 28     E[u].push_back((node){v,E[v].size(),w});
 29     E[v].push_back((node){u,E[u].size()-1,0}); 
 30 }
 31 
 32 void Topology()
 33 {
 34     memset(usable,0,sizeof(usable));
 35     queue<int> que;
 36     for (int i=S;i<=T;i++)
 37         if (!into[i]) que.push(i);
 38     while (!que.empty())
 39     {
 40         int head=que.front();que.pop();
 41         usable[head]=1;
 42         if (score[head]>0) ans+=score[head];
 43         for (int i=0;i<rE[head].size();i++)
 44         {
 45             int to=rE[head][i];
 46             into[to]--;
 47             if (!into[to]) que.push(to); 
 48         }
 49     }
 50 }
 51 
 52 bool bfs()
 53 {
 54     memset(dis,-1,sizeof(dis));
 55     queue<int> que;
 56     while (!que.empty()) que.pop(); 
 57     que.push(S);
 58     dis[S]=0;
 59     while (!que.empty())
 60     {
 61         int head=que.front();que.pop();
 62         if (head==T) return true;    //首次抵达T即可返回，不需要整张图全部分层 
 63         for (int i=0;i<E[head].size();i++)
 64         {
 65             node tmp=E[head][i];
 66             if (dis[tmp.to]==-1 && tmp.cap && usable[tmp.to])
 67             {
 68                 dis[tmp.to]=dis[head]+1;
 69                 que.push(tmp.to);
 70             }
 71         }
 72     }
 73     return false;
 74 }
 75  
 76 int dfs(int s,int e,int f)
 77 {
 78     if (s==e) return f;
 79     int ret=0;
 80     for (int i=0;i<E[s].size();i++)
 81     {
 82         node &tmp=E[s][i];
 83         if (dis[tmp.to]==dis[s]+1 && tmp.cap)
 84         {
 85             int delta=dfs(tmp.to,e,min(f,tmp.cap));
 86             if (delta>0)
 87             {
 88                 tmp.cap-=delta;
 89                 E[tmp.to][tmp.pos].cap+=delta;
 90                 f-=delta;
 91                 ret+=delta;
 92                 if (f==0) return ret;
 93             }
 94             else dis[tmp.to]=-1;//注意一下这里要清为-1，很重要★★★★★ 
 95         }
 96     } 
 97     return ret;
 98 }
 99  
100 void dinic()
101 {
102     while (bfs())
103     {
104         int f=dfs(S,T,INF);
105         if (f) ans-=f;else break;
106     }
107 }
108 
109 void init()
110 {
111     scanf("%d%d",&n,&m);
112     for (int i=1;i<=n;i++)
113         for (int j=1;j<=m;j++)
114         {
115             int w,fr=(i-1)*m+j;
116             scanf("%d%d",&score[fr],&w);
117             if (score[fr]>0) addedge(S,fr,score[fr]);
118                 else if (score[fr]<0) addedge(fr,T,-score[fr]);
119             for (int k=1;k<=w;k++)
120             {
121                 int r,c;
122                 scanf("%d%d",&r,&c);
123                 r++;c++;
124                 int to=(r-1)*m+c;
125                 addedge(to,fr,INF);
126             }
127             if (j!=m) addedge(fr,fr+1,INF);
128         }
129 }
130 
131 int main()
132 {
133     init();
134     Topology();
135     dinic();
136     printf("%d",ans);
137     return 0;
138 }