最大权闭合子图

最大权闭合子图其实就是通过一系列的证明，可以求证出来，用边权为正的累加和减去图的最大流就是这个图的最大权闭合子图。证明过程两天前写过一遍，但是丢掉了，实在不想去写了。

并且最大权闭合子图的题目拥有难度的并不多，也就下面这道题有一些难度，证明过程直接粘贴讲稿的QAQ

证明过程

  • 了解了最大权闭合图的概念，接下来我们就需要知道如何求最大权闭合图。首先我们将其转化为一个网络(现在不要问为什么,接下来会证明用网络可以求解)。构造一个源点S，汇点T。我们将S与所有权值为正的点连一条容量为其权值的边，将所有权值为负的点与T连一条容量为其权值的绝对值的边，原来的边将其容量定为正无穷。

  • 首先引入结论，最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图，接下来我们来说明一些结论。
    ?证明:最小割为简单割。

  • 引入一下简单割的概念：割集的每条边都与S或T关联。(请下面阅读时一定分清最小割与简单割，容易混淆)那么为什么最小割是简单割呢？因为除S和T之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证。

  • 证明网络中的简单割与原图中闭合图存在一一对应的关系。(即所有闭合图都是简单割，简单割也必定是一个闭合图)。

  • 证明闭合图是简单割：如果闭合图不是简单割(反证法)。那么说明有一条边是容量为正无穷的边，则说明闭合图中有一条出边的终点不在闭合图中，矛盾。

  • 证明简单割是闭合图：因为简单割不含正无穷的边，所以不含有连向另一个集合(除T)的点，所以其出边的终点都在简单割中，满足闭合图定义。得正。

  • 证明最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图。 首先我们记一个简单割的容量为C,且S所在集合为N，T所在集合为M。则C=M中所有权值为正的点的权值(即S与M中点相连的边的容量)+N中所有权值为负的点权值的绝对值(即N中点与T中点相连边的容量)。记(C=x1+y1);(很好理解，不理解画一个图或想象一下就明白了)。

  • 我们记N这个闭合图的权值和为W。则W=N中权值为正的点的权值-N中权值为负的点的权值的绝对值。记(W=x2-y2）则W+C=x1+y1+x2-y2。因为明显y1=y2，所以W+C=x1+x2;x1为M中所有权值为正的点的权值，x2为N中权值为正的点的权值。

  • 所以x1+x2=所有权值为正的点的权值之和(记为TOT).所以我们得到W+C=TOT.整理一下W=TOT-C.到这里我们就得到了闭合图的权值与简单割的容量的关系。

  • 因为TOT为定值，所以我们欲使W最大，即C最小，即此时这个简单割为最小割，此时闭合图为其源点S所在集合(除去S)。得正。

  • 至此，我们就将最大权闭合图问题转化为了求最小割的问题。求最小割用最小割容量=最大流，即可将问题转化为求最大流的问题。

NOI2009植物大战僵尸

题目描述：

  1. Plants vs. Zombies（PVZ）是最近十分风靡的一款小游戏。Plants（植物）和Zombies（僵尸）是游戏的主角，其中Plants防守，而Zombies进攻。该款游戏包含多种不同的挑战系列，比如Protect Your Brain、Bowling等等。其中最为经典的，莫过于玩家通过控制Plants来防守Zombies的进攻，或者相反地由玩家通过控制Zombies对Plants发起进攻。
  2. 现在，我们将要考虑的问题是游戏中Zombies对Plants的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色，Plants和Zombies，每个Plant有一个攻击位置集合，它可以对这些位置进行保护；而Zombie进攻植物的方式是走到植物所在的位置上并将其吃掉。
  3. 游戏的地图可以抽象为一个N行M列的矩阵，行从上到下用0到N–1编号，列从左到右用0到M–1编号；在地图的每个位置上都放有一个Plant，为简单起见，我们把位于第r行第c列的植物记为Pr, c。
  4. Plants分很多种，有攻击类、防守类和经济类等等。为了简单的描述每个Plant，定义Score和Attack如下：
  5. Zombies必须从地图的右侧进入，且只能沿着水平方向进行移动。Zombies攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此Zombies的进攻总是从地图的右侧开始。也就是说，对于第r行的进攻，Zombies必须首先攻击Pr, M-1；若需要对Pr, c（0≤c<M-1）攻击，必须将Pr,M-1, Pr, M-2 … Pr, c+1先击溃，并移动到位置(r, c)才可进行攻击。
  6. 在本题的设定中，Plants的攻击力是无穷大的，一旦Zombie进入某个Plant的攻击位置，该Zombie会被瞬间消灭，而该Zombie没有时间进行任何攻击操作。因此，即便Zombie进入了一个Plant所在的位置，但该位置属于其他植物的攻击位置集合，则Zombie会被瞬间消灭而所在位置的植物则安然无恙（在我们的设定中，Plant的攻击位置不包含自身所在位置，否则你就不可能击溃它了）。
  7. Zombies的目标是对Plants的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套Zombies的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。

输入：

输入文件pvz.in的第一行包含两个整数N, M，分别表示地图的行数和列数。
接下来N×M行描述每个位置上植物的信息。第r×M + c + 1行按照如下格式给出植物Pr, c的信息：第一个整数为Score[Pr, c], 第二个整数为集合Attack[Pr, c]中的位置个数w，接下来w个位置信息（r’, c’），表示Pr, c可以攻击位置第r’ 行第c’ 列。

输出：

输出文件pvz.out仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。

题解：

  • 这道题目同样是非常的麻烦，首先题目里面有很多的限制条件，也就是保护的关系，和你必须从地图的右方开始进攻，也就是说，我们需要建立一个完整的限制网络图。

  • 首先进行读入数据，然后建立一个临时的图，将所有的有保护关系的通过一个dis[i]数组记录下来有几个植物在保护自己，然后将所有没有植物保护的放在队列里面，然后更新掉队列里面的植物所保护的其他植物，一旦这个植物所有的保护都被更新掉了（拓扑排序），那么我们就将他加入到队列里面。

  • 进行一轮跟新之后，剩下的就是形成了一个保护环了，也就是里面的所有植物都是互相保护着的，然后我们除掉他们，也就是我们不可能干掉里面的任何一个植物了，所以就可以去掉了。一个DFS遍历将所有的环里面的植物的Del值标志位true,然后我们就可以重新建图。所有有先后关系的，先者向后者连着一条边，然后权值为正的连着汇点，权值为负的连着源点，对应边的权值全部为原来的绝对值。

  • 然后剩下的就是一个最大权闭合图的模型了，直接套最大流的模板就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cctype>
using namespace std;
#define P(x,y) (x-1)*m+y//这里* 表示坐标
struct Edge
{
    int Point;
    int Next;
    int Value;
    int Back;
}a[200000],b[200000];
int n,m,Queue[200000],Level[200000],len;
int Link_First[200000],Maxx,dis[200000];
int cnt,Link_Second[200000],Energy[200000];
int Delete[200000],top,all,ans,tot;
inline int Read()
{
    int This=0,F=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') F=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getchar();
    }
    return This*F;
}
bool GetLevel()
{
    memset(Queue,0,sizeof(Queue));
    memset(Level,-1,sizeof(Level));
    int head=0,tail=1;
    Queue[1]=1; Level[1]=0;
    while(++head<=tail)
    for(int i=Link_First[Queue[head]];i;i=a[i].Next)
    if(Level[a[i].Point]<0&&a[i].Value)
    {
        Queue[++tail]=a[i].Point;
        Level[Queue[tail]]=Level[Queue[head]]+1;
    }
    return Level[Maxx]>=0;
}
int GetMaxFlow(int x,int Flow)
{
    if(x==Maxx) return Flow;
    int MaxFlow=0,d=0;
    for(int i=Link_First[x];i&&MaxFlow<Flow;i=a[i].Next)
    if(a[i].Value&&Level[a[i].Point]==Level[x]+1)
    if(d=GetMaxFlow(a[i].Point,min(Flow-MaxFlow,a[i].Value)))
    {
        MaxFlow+=d;
        a[i].Value-=d;
        a[a[i].Back].Value+=d;
    }
    if(!MaxFlow) Level[x]=-1;
    return MaxFlow;
}
void Dinic()
{
    while(GetLevel())
    while(ans=GetMaxFlow(1,2123456789))
    all+=ans; return;
}
void AddEdge(int x,int y,int v)
{
    a[++len].Point=y;
    a[len].Value=v;
    a[len].Next=Link_First[x];
    a[len].Back=len+1;
    Link_First[x]=len;
    a[++len].Point=x;
    a[len].Value=0;
    a[len].Next=Link_First[y];
    a[len].Back=len-1;
    Link_First[y]=len;
}
void InsertEdge(int x,int y)
{
    dis[y]++;
    b[++cnt].Point=y;
    b[cnt].Next=Link_Second[x];
    Link_Second[x]=cnt;
}
void DFS(int x)
{
    Delete[x]=true;
    for(int i=Link_Second[x];i;i=b[i].Next)
    if(!Delete[b[i].Point]) DFS(b[i].Point);
}
void TopSort()
{
    for(int i=1;i<=n*m;i++)
    if(!dis[i]) Queue[++top]=i;
    else Delete[i]=true;
    while(top)
    {
        int That=Queue[top--];
        Delete[That]=false;
        for(int i=Link_Second[That];i;i=b[i].Next)
        {
            dis[b[i].Point]--;
            if(!dis[b[i].Point])
            Queue[++top]=b[i].Point;
        }
    }
    for(int i=1;i<=n*m;i++)
    if(Delete[i]) DFS(i);
}
void Rebuild()
{
    for(int i=1;i<=n*m;i++)
    if(!Delete[i])
    {
        if(Energy[i]>0)
        {
            tot+=Energy[i];
            AddEdge(i+1,Maxx,Energy[i]);
        }
        else AddEdge(1,i+1,-Energy[i]);
        for(int j=Link_Second[i];j;j=b[j].Next)
        if(!Delete[b[j].Point])
        AddEdge(i+1,b[j].Point+1,2123456789);
    }
}
int main()
{
    n=Read(); m=Read();
    Maxx=n*m+2;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        Energy[P(i,j)]=Read();
        int Protect=Read();
        while(Protect--)
        {
            int x=Read()+1;
            int y=Read()+1;
            InsertEdge(P(i,j),P(x,y));
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=m;j>1;j--)
    InsertEdge(P(i,j),P(i,j-1));
    TopSort(); Rebuild(); Dinic();
    cout<<tot-all<<endl;
    return 0;
}