P4926 [1007]倍杀测量者(差分约束取log判正环或负环)-白红宇的个人博客

P4926 [1007]倍杀测量者(差分约束取log判正环或负环)

发布日期：2021-06-30 10:30:31 浏览次数：3 分类：技术文章

本文共 3642 字，大约阅读时间需要 12 分钟。

赛后一定有选手去女装,说明原来的各种限制一定不同时成立

设原来的限制成立,我们可以建立如下不等式

选手 $A$ 立下 $k$ 倍杀选手 $B$ (条件一)

$w_A>=(k-T)w_B$ ，两边取 $l n$ 得到 $log(w_A)>=log(k-T)+log(w_B)$

选手 $A$ 立下选手 $B$ 不能 $k$ 倍杀自己 (条件二)

$k+T)w_A>=w_B$ ,两边取 $l n$ 得到 $log(k+T)+log(w_A)>=log(w_B)$

已知选手 $A$ 的分数为 $z$ (条件三)

$w_x>=z\&\&w_A<=z$ ,两边取 $l n$ 得到 $log(w_x)>=log(z)\&\&log(w_x)<=log(z)$

建立以上不等式,跑差分约束,若不出现负环,说明存在没有人女装的解

我们跑最长路判断是否存在正环即可

若出现正环,说明有条件不合法,说明一定有人需要女装

由于 $T$ 是满足单调性的, $T$ 越大越容易没有人女装,所以可以二分判断

注意一下 $l o g (k - T)$ 的话,当 $T > k$ 是没有意义的,所以上界应该取 $m i n$

#include 
   
    using namespace std;const int maxn = 3e5+10;const int inf = 1e9;const double eps = 1e-7;struct edge{
   	int to,nxt; double w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,double w){
    d[++cnt] = (edge){
   v,head[u],w},head[u] = cnt; }int n,s,t,type[maxn],A[maxn],B[maxn],K[maxn],num[maxn],vis[maxn],C[maxn];double dis[maxn];bool spfa(double T)//跑最短路吧 {
   	cnt = 1;	for(int i=0;i<=n;i++)	head[i] = vis[i] = num[i] = 0, dis[i] = -inf;	dis[0] = 0;	for(int i=1;i<=n;i++)	{
   		if( C[i]==0 )	continue;		add( 0,i,log( C[i] ) ); 	add( i,0,-log( C[i] ) );	}	for(int i=1;i<=s;i++)	{
   		int a = A[i], b = B[i] , k = K[i];//		if( C[a]&&C[b] )提前判断可以加速 //		{
   //			if( type[i]==1&&C[a]

q; q.push( 0 ); while( !q.empty() ) {

int u = q.front(); q.pop(); vis[u] = 0; for(int i=head[u];i;i=d[i].nxt ) {

int v = d[i].to; if( dis[v]

> n >> s >> t; double l = 0,r = 1e18, ans = -1; for(int i=1;i<=s;i++) {

cin >> type[i] >> A[i] >> B[i] >> K[i]; if( type[i]==1 ) r = min( r,(double)K[i]-eps ); } for(int i=1;i<=t;i++) {

int id,x; cin >> id >> x; C[id] = x; } while( r>=l+eps ) {

double mid = (l+r)/2.0; if( spfa(mid) ) l = mid+eps, ans = mid; else r = mid-eps; } if( ans==-1 ) printf("-1"); else printf("%.10lf",ans);}

最短路

#include 
   
    using namespace std;const int maxn = 3e5+10;const int inf = 1e9;const double eps = 1e-7;struct edge{
   	int to,nxt; double w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,double w){
    d[++cnt] = (edge){
   v,head[u],w},head[u] = cnt; }int n,s,t,type[maxn],A[maxn],B[maxn],K[maxn],num[maxn],vis[maxn],C[maxn];double dis[maxn];bool spfa(double T)//跑最短路吧 {
   	cnt = 1;	for(int i=0;i<=n;i++)	head[i] = vis[i] = num[i] = 0, dis[i] = inf;	dis[0] = 0;	for(int i=1;i<=n;i++)	{
   		if( C[i]==0 )	continue;		add( i,0,-log( C[i] ) ); 	add( 0,i,log( C[i] ) );	}	for(int i=1;i<=s;i++)	{
   		int a = A[i], b = B[i] , k = K[i];//		if( C[a]&&C[b] )//		{
   //			if( type[i]==1&&C[a]

q; q.push( 0 ); while( !q.empty() ) {

int u = q.front(); q.pop(); vis[u] = 0; for(int i=head[u];i;i=d[i].nxt ) {

int v = d[i].to; if( dis[v]>dis[u]+d[i].w ) {

dis[v] = dis[u]+d[i].w; if( !vis[v] ) {

vis[v] = 1, q.push( v ); if( ++num[v]==n+2 ) return true; } } } } return false;}int main(){

cin >> n >> s >> t; double l = 0,r = 1e18, ans = -1; for(int i=1;i<=s;i++) {

cin >> type[i] >> A[i] >> B[i] >> K[i]; if( type[i]==1 ) r = min( r,(double)K[i]-eps ); } for(int i=1;i<=t;i++) {

int id,x; cin >> id >> x; C[id] = x; } while( r>=l+eps ) {

double mid = (l+r)/2.0; if( spfa(mid) ) l = mid+eps, ans = mid; else r = mid-eps; } if( ans==-1 ) printf("-1"); else printf("%.10lf",ans);}

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114543743 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：P5840 [COCI2015]Divljak(ac自动机+排序树上差分)

下一篇：QT操作mysql数据库(创建,插入,更新,删除)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章