链接
https://www.luogu.com.cn/problem/P4926
题意
有两种约束条件
s
a
≥
s
b
(
k
−
T
)
s_a\ge s_b(k-T)
sa≥sb(k−T)
s
b
<
s
a
(
k
+
T
)
s_b< s_a(k+T)
sb<sa(k+T)
现在有
s
s
s 个条件，
t
t
t 个已知点，使
T
T
T 尽可能大来满足所有条件
思路
o
=
1
o=1
o=1，
s
a
≥
s
b
(
k
−
T
)
→
log
(
s
a
)
≥
log
(
s
b
)
+
log
(
k
−
T
)
s_a\ge s_b(k-T) \rightarrow \log(s_a)\ge \log(s_b)+\log(k-T)
sa≥sb(k−T)→log(sa)≥log(sb)+log(k−T)
o
=
2
o=2
o=2，
s
b
<
s
a
(
k
+
T
)
→
s
a
≥
s
b
k
+
T
→
log
(
s
a
)
≥
log
(
s
b
)
−
log
(
k
+
T
)
s_b< s_a(k+T)\rightarrow s_a\ge \frac{s_b}{k+T}\rightarrow \log(s_a)\ge \log(s_b)-\log(k+T)
sb<sa(k+T)→sa≥k+Tsb→log(sa)≥log(sb)−log(k+T)（误差不超过
1
0
−
4
10^{-4}
10−4，大于可近似成大于等于）
按照上述关系建立有向边
对于已知点
c
c
c：
s
c
−
0
≥
x
s_c-0\ge x
sc−0≥x
0
−
s
c
≥
−
x
0-s_c\ge -x
0−sc≥−x
建立一个超级起点与已知点之间建立一条权值为
log
(
x
)
\log(x)
log(x) 的有向边，再在已知点与超级起点建立一条权值为
−
log
(
x
)
-\log(x)
−log(x) 的有向边
最后在超级起点与所有点之间建立一条权值为
0
0
0 的有向边，使图连通
二分
T
T
T，跑最长路，有正环则无解
代码
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std
;
typedef double DB
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;
typedef vector
<int> VI
;
typedef vector
<PII
> VPII
;
const int N
=1e3+5;
int n
,s
,t
;
int vis
[N
],cnt
[N
];
DB dist
[N
];
bool st
[N
];
struct E
{
int v
,o
;
DB w
;
E() {}
E(int v
,DB w
,int o
):v(v
),w(w
),o(o
) {}
};
vector
<E
> G
[N
];
bool spfa(DB mid
) {
for(int i
=1;i
<=n
;i
++) {
cnt
[i
]=0;
st
[i
]=false;
dist
[i
]=-1e8;
}
queue
<int> q
;
q
.push(n
);
dist
[n
]=0;
cnt
[n
]=1;
st
[n
]=true;
while(q
.size()) {
int u
=q
.front();
q
.pop();
st
[u
]=false;
for(auto x
:G
[u
]) {
int v
=x
.v
;
DB w
=x
.w
;
if(x
.o
==1) w
=log(w
-mid
);
else if(x
.o
==2) w
=-log(w
+mid
);
if(dist
[v
]<dist
[u
]+w
) {
dist
[v
]=dist
[u
]+w
;
cnt
[v
]++;
if(cnt
[v
]>=n
) return true;
if(!st
[v
]) {
st
[v
]=true;
q
.push(v
);
}
}
}
}
return false;
}
int main() {
scanf("%d%d%d",&n
,&s
,&t
);
for(int i
=1;i
<=s
;i
++) {
int o
,a
,b
;
DB k
;
scanf("%d%d%d%lf",&o
,&a
,&b
,&k
);
if(o
==1) G
[b
].PB(E(a
,k
,1));
else G
[b
].PB(E(a
,k
,2));
}
for(int i
=1;i
<=t
;i
++) {
int c
;
DB x
;
scanf("%d%lf",&c
,&x
);
G
[n
+1].PB(E(c
,log(x
),3));
G
[c
].PB(E(n
+1,-log(x
),3));
}
for(int i
=1;i
<=n
;i
++) G
[n
+1].PB(E(i
,0,3));
n
++;
DB l
=0,r
=10;
DB res
=-1;
while(r
-l
>1e-6) {
DB mid
=(l
+r
)/2;
if(spfa(mid
)) res
=mid
,l
=mid
;
else r
=mid
;
}
if(res
==-1) puts("-1");
else printf("%.10f\n",l
);
return 0;
}
