ARC142E Pairing Wizards

ARC142E Pairing Wizards

题目大意

有$n$个法师，编号为$1$到$n$。法师$i$有强度$a_i$，他计划打败强壮度为$b_i$的怪物。

你可以执行以下操作任意次：

• 选中一个法师，将它的强壮度增加1

一对法师$(i,j)$称为好的，当至少满足以下条件之一：

• 法师$i$至少有$b_i$的强壮度，法师$j$至少有$b_j$的强壮度
• 法师$i$至少有$b_j$的强壮度，法师$j$至少有$b_i$的强壮度

你的目标是对于$i=1,\dots ,m$，使得$(x_i,y_i)$称为一对好的法师。求最小的操作数量。

题解

首先，令$m{n}_x=\underset{(x,y)\in E}{\max }(\min (b_x,b_y))$。如果$a_x<m{n}_x$，则不断增加$a_x$使得$a_x=m{n}_x$。

如果$b_x>a_x$，则$x$属于$X$集合；如果$b_x\le a_x$，则$x$属于$Y$集合。我们把每一对法师看作一条边，因为上面对$a_x$的改变，所以每条边中至少有一个点在$Y$集合中。

每个$X$集合的点$x$对应一个点$x$，每个$Y$集合中的点$y$和一个在1到100之间的值$a$对应一个点$(y,a)$。我们可以按如下方法建图，那么答案为最小割，即最大流，用网络流即可解决。

• 对于$i\in X$，连边$(s,i,b_i-a_i)$
• 对于$i\in Y$，连边$((i,j),t,1)$
• 对于$i\in Y$，连边$((i,j),(i,j-1),\infty )$
• 对于$(i,j)\in E,i\in X,j\in Y,b_i>a_j$，连边$(i,(j,b_i-a_j),\infty )$

如果要使$a_x\ge b_x$，则割第一类边；如果要使$a_x\ge b_y,a_y\ge b_x$，则割第二类边。因为无限的影响，第三类边只能将$j$值小的放在$s$的一边，$j$值大的放在$t$的一边，第四类边不会被割。这样就可以求最小的操作数了。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,ans=0,vt=0,s,t,v1=0,v2=0,inf=1e9,a[105],b[105],mn[105],on[105],re[105];
int tot=1,cs[100005],l[100005],r[100005],w[100005],d[100005],vd[100005];
struct node{int x,y;
}vw[10005];
void add(int xx,int yy,int zz){l[++tot]=r[xx];cs[tot]=yy;r[xx]=tot;w[tot]=zz;
}
int aug(int i,int augco){if(i==t) return augco;int augc=augco,dl=0,md=n-1;for(int u=r[i];u;u=l[u]){int j=cs[u];if(w[u]>0){if(d[i]==d[j]+1){dl=min(augc,w[u]);dl=aug(j,dl);w[u]-=dl;w[u^1]+=dl;augc-=dl;if(d[s]>=n) return augco-augc;if(!augc) break;}if(md>d[j]) md=d[j];}}if(augco==augc){--vd[d[i]];if(!vd[d[i]]) d[s]=n;d[i]=md+1;++vd[d[i]];}return augco-augc;
}
void sap(){vd[0]=n;while(d[s]<n) ans+=aug(s,inf);
}
int main()
{scanf("%d",&n);s=++vt;t=++vt;for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);mn[i]=a[i];}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);vw[i]=(node){x,y};mn[x]=max(mn[x],min(b[x],b[y]));mn[y]=max(mn[y],min(b[x],b[y]));}for(int i=1;i<=n;i++){ans+=mn[i]-a[i];a[i]=mn[i];if(a[i]<b[i]){add(s,i+2,b[i]-a[i]);add(i+2,s,0);}else{re[i]=++v2;on[i]=1;for(int j=1;j<=100;j++){add(2+n+(i-1)*100+j,t,1);add(t,2+n+(i-1)*100+j,0);if(j>1){add(2+n+(i-1)*100+j,2+n+(i-1)*100+j-1,inf);add(2+n+(i-1)*100+j-1,2+n+(i-1)*100+j,0);}}}}for(int i=1;i<=m;i++){x=vw[i].x;y=vw[i].y;if(on[x]==0&&on[y]==1){if(b[x]>a[y]){add(x+2,2+n+(y-1)*100+b[x]-a[y],inf);add(2+n+(y-1)*100+b[x]-a[y],x+2,0);}}else if(on[x]==1&&on[y]==0){swap(x,y);if(b[x]>a[y]){add(x+2,2+n+(y-1)*100+b[x]-a[y],inf);add(2+n+(y-1)*100+b[x]-a[y],x+2,0);}}}n=2+n+n*100;sap();printf("%d",ans);return 0;
}