题解 P3701 【「伪模板」主席树】

2018-09-06 19:58:18


这题感觉完全没有黑题的难度啊,毕竟连我都会做

思路:很明显的最大流

如果不会最大流

为什么会想到最大流呢?

其实题目里到处都在暗示要用最大流

比如说:

两个人之间只能比一场。--->连一条容量为1的边

每次比完赛他们就会-1s。当他们生命为0s时他们就不能再比赛了。-->每条增广路流1,容量减1,边的容量满了就不能流了

最多能够赢得多少场比赛--->最大流是多少

看吧,到处都在暗示用最大流

接下来我们讲建图:

定义点:

byx和手气君每个人都对应一个点

还要一个s(源点),一个t(汇点),一个tt(假装是汇点,后面要加tt指向t的边来限制场数)

加边:

1.s流向byx每个人的边,容量为人的寿命(如果是J就加上YYY的数量)

2.手气君每个人流向tt的边,容量为人的寿命(J要加YYY的数量)

3.按克制关系加边,byx的人流向手气君的人(注意:每个被克的人都要加,例:byx的每个J要对应手气君每个HK和每个W),容量为1

4.tt流向t的边,容量为m(最多比m场)

更直观的理解:

样例建好图后是这样的:

然后跑最大流就完了,由于图很稠密,推荐Dinic

如果不会Dinci

代码略丑:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int inf=1<<30;
int a[101][2];//分别装byx和手气君的人,1表示J,2表示HK,3表示W,4表示YYY,5表示E
int b[101][2];//装寿命 
inline void REad(int i,int f){
    char c=getchar();
    string st="";
    while(c>'Z'||c<'A')c=getchar();
    while(c>='A'&&c<='Z')st=st+c,c=getchar();
    if(st=="J")a[i][f]=1;
    else if(st=="HK")a[i][f]=2;
    else if(st=="W")a[i][f]=3;
    else if(st=="YYY")a[i][f]=4;
    else if(st=="E")a[i][f]=5;
}//f==0表示byx,f==1表示手气君 
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int head[10101],cur[10101],top=1;
int n,m,s,t,tt;
struct Node{
    int v;
    int val;
    int next;
}node[101010];
inline void addedge(int u,int v,int val){
    node[++top].v=v;
    node[top].val=val;
    node[top].next=head[u];
    head[u]=top;
}
inline void add(int u,int v,int val){
    addedge(u,v,val);
    addedge(v,u,0);
}
int dep[10101],inque[10101];
bool spfa(){
    for(register int i=1;i<=t;i++){
        dep[i]=inf;
        inque[i]=0;
        cur[i]=head[i];
    }
    queue<int>q;
    q.push(s);
    dep[s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(int i=head[u];i;i=node[i].next){
            int d=node[i].v;
            if(node[i].val&&dep[d]>dep[u]+1){
                dep[d]=dep[u]+1;
                if(inque[d]==0){
                    q.push(d);
                    inque[d]=1;
                }
            }
        }
    }
    return dep[t]!=inf;
}
int maxflow,vis;
int dfs(int u,int flow){
    if(u==t){
        vis=1;
        maxflow+=flow;
        return flow;
    }
    int used=0;
    for(int i=cur[u];i;i=node[i].next){
        cur[u]=i;
        int d=node[i].v;
        if(dep[d]==dep[u]+1&&node[i].val){
        int low=dfs(d,min(node[i].val,flow-used));
        if(low!=0)used+=low,node[i].val-=low,node[i^1].val+=low;
        }
        if(used==flow)break;
    }
    return used;
}
int Dinic(){
    maxflow=0;
    while(spfa()){
        vis=1;
        while(vis)vis=0,dfs(s,inf);
    }
    return maxflow;
}
vector<int>J,HK,W,YYY,E;
void k(int i,vector<int> a){
    int sz=a.size();
    for(int j=0;j<sz;j++)add(i,n+a[j],1);//两个人之间只能比一场 
}
void ad(int i){
    if(a[i][0]==4||a[i][0]==5)k(i,J);
    if(a[i][0]==1||a[i][0]==4)k(i,HK);
    if(a[i][0]==1||a[i][0]==2)k(i,W);
    if(a[i][0]==3||a[i][0]==5)k(i,YYY);
    if(a[i][0]==2||a[i][0]==3)k(i,E);
}//按照克制关系给i点加边 
int main(){
    n=Read(),m=Read();
    register int i;
    int cnt1,cnt2;//两人YYY的数量 
    cnt1=cnt2=0;
    s=2*n+1,tt=2*n+2,t=2*n+3;
    add(tt,t,m);//最多比m场 
    for(i=1;i<=n;i++){
    REad(i,0);
    if(a[i][0]==4)cnt1++;   
    }
    for(i=1;i<=n;i++){
    REad(i,1);
    if(a[i][1]==4)cnt2++;
    if(a[i][1]==1)J.push_back(i);
    else if(a[i][1]==2)HK.push_back(i);
    else if(a[i][1]==3)W.push_back(i);
    else if(a[i][1]==4)YYY.push_back(i);
    else if(a[i][1]==5)E.push_back(i);
    }
    for(i=1;i<=n;i++)b[i][0]=Read();
    for(i=1;i<=n;i++)b[i][1]=Read();
    int now;
    for(i=1;i<=n;i++){
    now=i;
    if(a[i][0]==1)add(s,now,b[i][0]+cnt1);//YYY只能给J加命 
    else add(s,now,b[i][0]);
    ad(i);
    }
    for(i=1;i<=n;i++){
    now=i+n;
    if(a[i][1]==1)add(now,tt,b[i][1]+cnt2);
    else add(now,tt,b[i][1]);
    }
    printf("%d",Dinic());
    return 0;
}