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

~~这题感觉完全没有黑题的难度啊，毕竟连我都会做~~ # 思路：~~很明显的~~最大流 [如果不会最大流](https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-di-zong-jie) 为什么会想到最大流呢？ ### 其实题目里到处都在暗示要用最大流 比如说： 两个人之间只能比一场。--->连一条容量为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](https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-jiang-xie-zhi-dinic) 代码略丑: ``` #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; } ```