从化区住房和建设局网站,网站建设软硬件要求,网站建设推广招代理加盟,济宁人才网招聘信息网ARC142E Pairing Wizards
题目大意
有nnn个法师#xff0c;编号为111到nnn。法师iii有强度aia_iai#xff0c;他计划打败强壮度为bib_ibi的怪物。
你可以执行以下操作任意次#xff1a;
选中一个法师#xff0c;将它的强壮度增加1
一对法师(i,j)(i,j)(i,j)称为好的…ARC142E Pairing Wizards
题目大意
有nnn个法师编号为111到nnn。法师iii有强度aia_iai他计划打败强壮度为bib_ibi的怪物。
你可以执行以下操作任意次
选中一个法师将它的强壮度增加1
一对法师(i,j)(i,j)(i,j)称为好的当至少满足以下条件之一
法师iii至少有bib_ibi的强壮度法师jjj至少有bjb_jbj的强壮度法师iii至少有bjb_jbj的强壮度法师jjj至少有bib_ibi的强壮度
你的目标是对于i1,…,mi1,\dots,mi1,…,m使得(xi,yi)(x_i,y_i)(xi,yi)称为一对好的法师。求最小的操作数量。 题解
首先令mnxmax(x,y)∈E(min(bx,by))mn_x\max\limits_{(x,y)\in E}(\min(b_x,b_y))mnx(x,y)∈Emax(min(bx,by))。如果axmnxa_xmn_xaxmnx则不断增加axa_xax使得axmnxa_xmn_xaxmnx。
如果bxaxb_xa_xbxax则xxx属于XXX集合如果bx≤axb_x\leq a_xbx≤ax则xxx属于YYY集合。我们把每一对法师看作一条边因为上面对axa_xax的改变所以每条边中至少有一个点在YYY集合中。
每个XXX集合的点xxx对应一个点xxx每个YYY集合中的点yyy和一个在1到100之间的值aaa对应一个点(y,a)(y,a)(y,a)。我们可以按如下方法建图那么答案为最小割即最大流用网络流即可解决。
对于i∈Xi\in Xi∈X连边(s,i,bi−ai)(s,i,b_i-a_i)(s,i,bi−ai)对于i∈Yi\in Yi∈Y连边((i,j),t,1)((i,j),t,1)((i,j),t,1)对于i∈Yi\in Yi∈Y连边((i,j),(i,j−1),∞)((i,j),(i,j-1),\infty)((i,j),(i,j−1),∞)对于(i,j)∈E,i∈X,j∈Y,biaj(i,j)\in E,i\in X,j\in Y,b_ia_j(i,j)∈E,i∈X,j∈Y,biaj连边(i,(j,bi−aj),∞)(i,(j,b_i-a_j),\infty)(i,(j,bi−aj),∞)
如果要使ax≥bxa_x\geq b_xax≥bx则割第一类边如果要使ax≥by,ay≥bxa_x\geq b_y,a_y\geq b_xax≥by,ay≥bx则割第二类边。因为无限的影响第三类边只能将jjj值小的放在sss的一边jjj值大的放在ttt的一边第四类边不会被割。这样就可以求最小的操作数了。
code
#includebits/stdc.h
using namespace std;
int n,m,x,y,ans0,vt0,s,t,v10,v20,inf1e9,a[105],b[105],mn[105],on[105],re[105];
int tot1,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(it) return augco;int augcaugco,dl0,mdn-1;for(int ur[i];u;ul[u]){int jcs[u];if(w[u]0){if(d[i]d[j]1){dlmin(augc,w[u]);dlaug(j,dl);w[u]-dl;w[u^1]dl;augc-dl;if(d[s]n) return augco-augc;if(!augc) break;}if(mdd[j]) mdd[j];}}if(augcoaugc){--vd[d[i]];if(!vd[d[i]]) d[s]n;d[i]md1;vd[d[i]];}return augco-augc;
}
void sap(){vd[0]n;while(d[s]n) ansaug(s,inf);
}
int main()
{scanf(%d,n);svt;tvt;for(int i1;in;i){scanf(%d%d,a[i],b[i]);mn[i]a[i];}scanf(%d,m);for(int i1;im;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 i1;in;i){ansmn[i]-a[i];a[i]mn[i];if(a[i]b[i]){add(s,i2,b[i]-a[i]);add(i2,s,0);}else{re[i]v2;on[i]1;for(int j1;j100;j){add(2n(i-1)*100j,t,1);add(t,2n(i-1)*100j,0);if(j1){add(2n(i-1)*100j,2n(i-1)*100j-1,inf);add(2n(i-1)*100j-1,2n(i-1)*100j,0);}}}}for(int i1;im;i){xvw[i].x;yvw[i].y;if(on[x]0on[y]1){if(b[x]a[y]){add(x2,2n(y-1)*100b[x]-a[y],inf);add(2n(y-1)*100b[x]-a[y],x2,0);}}else if(on[x]1on[y]0){swap(x,y);if(b[x]a[y]){add(x2,2n(y-1)*100b[x]-a[y],inf);add(2n(y-1)*100b[x]-a[y],x2,0);}}}n2nn*100;sap();printf(%d,ans);return 0;
}
