「Luogu P3701」「伪模板」主席树

发表于 |
字数统计: 1.1k | 阅读时长 ≈ 5

A和B有五种不同的人物，共$n$个，两人之间要比$m$场。A的的$i$个人物的寿命为$hpA_i$，B的为$hpB_i$。
每一次A和B选出不同的人物进行PK，每一次PK使得两边人物的寿命$-1s$，当寿命为$0$时就不能比赛了，两个人之间只能比一场。
同时，当J的寿命为$0$时，同一棵树上的YYY可以为他$+1s$。每个YYY只能给每个J续一次，最大化A能赢的场次的数目。

题解

一个比较巧妙的网络流建模题。
首先打出人物之间输赢的表，然后考虑从源点像A的第$i$个人物连边，容量为$hpA_i$，从B的第$i$个人物像汇点连边，容量为$hpB_i$。
以上连边，如果第$i$个人是J，则将容量增加本方YYY的数量。
对于A的第$i$个人能赢B的第$j$个人，就从A的第$i$个人向B的第$j$个人A的人连边，容量为$1$。跑一边最大流即可。
下面分析为什么这样连边是对的。
先不考虑续命，这个人物不能出战即找不到经过这个人物的增广路，而通过这个人物的增广路只能是从源点直接到这个人物再到后面或是前面找到的增广路到这个人物再到汇点。
以上这句话很重要，请仔细理解。所以，当源点到这个人物或这个人物到汇点的边为零流边就找不到增广路了，即这个人没命了。所以从源点发出或到汇点连边是正确的。
由于两个人之间只能比一场，而题目要求只求胜利场次数，所以中间的连边也是正确的。
现在考虑续命。对于一个J，无论YYY是死是活，总能在它死的时候续命，对于每一个J都是一样。所以将从源点连到J的边或是J连到汇点的边的容量增加本方YYY的个数。
至此，连边的正确性就已经说明清楚了。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=1e5+51,inf=0x7fffffff;
struct Edge{
    ll to,prev,flow;
};
Edge ed[MAXN<<1];
map<string,ll>mp;
ll nc,ec,source,sink,tot=1,from,to,flow,maxFlow;
ll cnt,ccnt,life,xx,yy;
ll last[MAXN],depth[MAXN],inQueue[MAXN];
ll win[5][5]={
    0,0,0,1,1,
    1,0,1,0,0,
    1,0,0,1,0,
    0,1,0,0,1,
    0,1,1,0,0
};
string x[151],y[151];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void addEdge(ll from,ll to,ll flow)
{
    ed[++tot].prev=last[from];
    ed[tot].to=to;
    ed[tot].flow=flow;
    last[from]=tot; 
}
inline ll Min(ll x,ll y)
{
    return x<y?x:y;
}
inline bool bfs()
{
    queue<ll>q;
    ll top,to;
    memset(depth,0x3f,sizeof(depth));
    depth[source]=0,q.push(source);
    while(!q.empty())
    {
        top=q.front();
        q.pop(),inQueue[top]=0;
        for(register int i=last[top];i;i=ed[i].prev)
        {
            to=ed[i].to;
            if(depth[to]>depth[top]+1&&ed[i].flow)
            {
                depth[to]=depth[top]+1;
                if(!inQueue[to])
                {
                    q.push(to),inQueue[to]=1;
                }
            }
        }
    }
    if(depth[sink]!=0x3f3f3f3f)
    {
        return 1;	
    } 
    return 0;
}
inline ll dfs(ll cur,ll flow)
{
    ll low;
    if(cur==sink)
    {
        return flow;
    }
    for(register int i=last[cur];i;i=ed[i].prev)
    {
        if(ed[i].flow&&depth[ed[i].to]==depth[cur]+1)
        {
            if(low=dfs(ed[i].to,Min(flow,ed[i].flow)))
            {
                ed[i].flow-=low,ed[i^1].flow+=low;
                return low;
            }
        }
    }
    return 0;
}
inline ll Dinic()
{
    ll flow;
    while(bfs())
    {
        while(flow=dfs(source,inf))
        {
            maxFlow+=flow;
        }
    }
    return maxFlow;
}
int main()
{
    cnt=read(),ccnt=read();
    nc=sink=(cnt+1)<<1,source=1;
    mp["J"]=0,mp["E"]=1,mp["YYY"]=2,mp["HK"]=3,mp["W"]=4;
    for(register int i=1;i<=cnt;i++)
    {
        cin>>x[i];
        xx+=(x[i]=="YYY");
    }
    for(register int i=1;i<=cnt;i++)
    {
    	cin>>y[i];
    	yy+=(y[i]=="YYY");
    }
    for(register int i=2;i<=cnt+1;i++)
    {
        life=read();
        addEdge(source,i,life+(x[i-1]=="J"?xx:0)),addEdge(i,source,0);
    }
    for(register int i=2;i<=cnt+1;i++)
    {
        life=read();
        addEdge(i+cnt,sink,life+(y[i-1]=="J"?yy:0)),addEdge(sink,i+cnt,0);
    }
    for(register int i=1;i<=cnt;i++)
    {
        xx=mp[x[i]];
        for(register int j=1;j<=cnt;j++)
        {
            yy=mp[y[j]];
            if(win[xx][yy])
            {
                addEdge(i+1,j+1+cnt,1),addEdge(j+1+cnt,i+1,0);
            }
        }
    }
    printf("%d",min(ccnt,Dinic()));
}