[P2474 SCOI2008]天平 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意:
已知A,B和每两个点点权,求点权i,j,使得A+B>i+j的方案数ans1,A+B==i+j的方案数ans2,A+B<i+j的方案数ans3。
分析:
A+B>i+j可以化为A-i>j-B||i-A<B-j;A+Bi+j可以化为A-ij-B||i-A==B-j;A+B<i+j可以化为A-i<j-B||i-A>B-j。当然,i也可以与B搭配,j也可以与A搭配。所以对于每个条件都有两个式子。接下来,欢迎差分约束上台表演!maxn(i,j)表示从点i到点j之间最大值,minn(i,j)表示从点i到点j最小值。
代码如下:
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; int n,A,B,maxn[55][55],minn[55][55],ans1,ans2,ans3; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); } while(ch<='9'&&ch>='0'){ s=s*10+ch-'0'; ch=getchar(); } return s*w; } int main(){ n=read();A=read();B=read(); string a; for(int i=1;i<=n;i++){ cin>>a; for(int j=0;j<a.size();j++){ if(i==j+1||a[j]=='=')maxn[i][j+1]=minn[i][j+1]=0; else if(a[j]=='-')maxn[i][j+1]=-1,minn[i][j+1]=-2;//二者差最大为2,最小为1,这里i<j,用负号 else if(a[j]=='+')maxn[i][j+1]=2,minn[i][j+1]=1;//二者差最大为2,最小为1,这里i>j,用正号 else maxn[i][j+1]=2,minn[i][j+1]=-2;//这里是最大差2 } } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ if(i==k)continue; for(int j=1;j<=n;j++){ if(i==j)continue; maxn[i][j]=min(maxn[i][k]+maxn[k][j],maxn[i][j]);//求最大值的最小值,为了满足更多约束条件 minn[i][j]=max(minn[i][k]+minn[k][j],minn[i][j]);//求最小值的最大值,为了满足更多约束条件 } } } for(int i=1;i<=n;i++){ if(i==A||i==B)continue; for(int j=1;j<i;j++){ if(j==A||j==B)continue; if(minn[A][i]>maxn[j][B]||minn[B][i]>maxn[j][A])++ans1;//A+B>i+j else if(minn[i][A]>maxn[B][j]||minn[i][B]>maxn[A][j])++ans3;//A+B<i+j //此处换为 else if(maxn[A][i]<minn[j][B]||maxn[B][i]<minn[j][A])++ans3; 也可以 else if((maxn[A][i]==minn[j][B]&&minn[A][i]==maxn[j][B]&&maxn[A][i]==minn[A][i])//A+B==i+j ||(maxn[B][i]==minn[j][A]&&minn[B][i]==maxn[j][A]&&maxn[B][i]==minn[B][i]))++ans2; //当只有唯一一个确定的值才能正式确定“=” } } cout<<ans1<<" "<<ans2<<" "<<ans3; return 0; }