容易想到二分答案。問題變為判斷是否所有條件都被滿足，可以發現這是很多變量間的相對關系，取個log之后就是經典的差分約束模型了。特殊的地方在于某些人的分數已被給定，從每個人開始跑一遍最短路判斷一下是否能滿足關系即可。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } #define N 1010 const double eps=1E-6; double l,r,ans,d[N],a[N]; int n,m,k,p[N],q[N],cnt[N],t; bool f[N],isget[N]; struct data{int to,nxt;double len; }edge[N<<2]; struct flag{int op,x,y,z; }Q[N]; void addedge(int x,int y,double z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;} int inc(int &x){x++;if (x>n+1) x-=n+1;return x;} bool spfa(int k) {memset(f,0,sizeof(f));for (int i=1;i<=n;i++) d[i]=10000000;d[k]=0;memset(cnt,0,sizeof(cnt));int head=0,tail=1;q[1]=k;do{int x=q[inc(head)];f[x]=0;for (int i=p[x];i;i=edge[i].nxt)if (d[x]+edge[i].len<d[edge[i].to]){d[edge[i].to]=d[x]+edge[i].len;if (!f[edge[i].to]){q[inc(tail)]=edge[i].to,f[edge[i].to]=1;cnt[edge[i].to]++;if (cnt[edge[i].to]==n) return 0;}}}while (head!=tail);if (isget[k])for (int i=1;i<=n;i++)if (isget[i]&&d[i]<a[i]-a[k]) return 0;return 1; } bool check(double T) {t=0;memset(p,0,sizeof(p));for (int i=1;i<=m;i++)if (Q[i].op==1){if (Q[i].z>T) addedge(Q[i].x,Q[i].y,-log(Q[i].z-T));}else addedge(Q[i].x,Q[i].y,log(Q[i].z+T));for (int i=1;i<=n;i++)if (!spfa(i)) return 1;return 0; } int main() { #ifndef ONLINE_JUDGEfreopen("c.in","r",stdin);freopen("c.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifn=read(),m=read(),k=read();for (int i=1;i<=m;i++)Q[i].op=read(),Q[i].x=read(),Q[i].y=read(),Q[i].z=read();l=eps,r=10-eps;ans=-1;for (int i=1;i<=k;i++){int x=read(),y=read();a[x]=log(y);isget[x]=1;}while (l<=r){double mid=(l+r)/2;if (check(mid)) ans=mid,l=mid+eps;else r=mid-eps;}if (ans<0) cout<<-1;else printf("%.8lf",ans);return 0; }

?

轉載于:https://www.cnblogs.com/Gloid/p/9762749.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Luogu4926 倍杀测量者（二分答案+差分约束）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。