洛谷P4926 [1007]倍杀测量者,个人看法和理解
最近校赛出了这道题的改编题,那时候我信心满满的认为是水题,一发贪心GG,心态爆炸。
错误的思路:
将式子变形:
对于每一个A,B都知道成绩的组,求出他们的T,然后将最大的T输出即可
下面是错误的代码:
#include<bits/stdc++.h>
using namespace std;
int score[1004];
struct node{
int to,k,o;
};
vector<node> flags[1004];
int main(){
int n,s,t; cin>>n>>s>>t;
memset(score,0,sizeof(score));
while(s--){
int o,a,b,k;
scanf("%d %d %d %d",&o,&a,&b,&k);
node q;
q.k=k; q.to=b; q.o=o;
flags[a].push_back(q);
}
while(t--){
int num,sco; scanf("%d %d",&num,&sco);
score[num]=sco;
}
double T=0;
for(int i=1;i<=n;i++){
if(!flags[i].size()) continue;
for(int j=0;j<flags[i].size();j++){
node q=flags[i][j];
if(!score[q.to]||!score[i]) continue;
if(q.o==1){
double gg=((double)score[i])/score[q.to];
T=max(T,q.k-gg);
}
else{
double gg=((double)score[q.to])/score[i];
T=max(T,gg-q.k);
}
}
}
if(T==0) cout<<-1<<endl;
else{
printf("%.2lf",T); //校赛精度是0.01
}
return 0;
}
为什么会错呢
即使不知道b的成绩,依然可以求T,假如按上面的思路那么就歇菜了(心疼我自己一秒)
这道题其实用的是类似差分约束的思想,我看网上很多人通过log将乘法变成加法,然鹅也可以不需要log。
首先根据题目要求找出T的范围,根据二分搜索将每一个T都试着验证一下其正确性。
如何验证呢,首先根据已知的关系构建路,然后根据已知的成绩构建两条路(0~目标的正反路)
void add_edge(int a,int b,double c){
nex[++cnt]=head[a] ;head[a]=cnt; to[cnt]=b; val[cnt]=c;
}
for(int i=1;i<=q;i++){
add_edge(0,aim[i],mark[i]);
add_edge(aim[i],0,1.0/mark[i]);
}
(注:aim 就是学生,mark就是成绩,然后那个add里面数组的话看不懂可以放着。。)
然后跑spfa,有一个关系:
if(val[i]*dis[now]>dis[v]){
dis[v]=val[i]*dis[now];
然后跑这个关系,由于是递增的关系,那么有可能会形成环。
如图,假如所用的T能够发生状态转移,那么就会变成环
假如有环,那么T就是可以的!
AC代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
const double jingdu=1e-8;
int fro[maxn],to[maxn<<1],nex[maxn<<1],head[maxn]; //增加一倍是因为要和0取得联♂系
double val[maxn<<1],dis[maxn];
int a[maxn],o[maxn],b[maxn],c[maxn],mark[maxn],aim[maxn];
int vis[maxn],Count[maxn];
int stu,fla,q,cnt;
void add_edge(int a,int b,double c){
nex[++cnt]=head[a] ;head[a]=cnt; to[cnt]=b; val[cnt]=c;
}
bool spfa(int sor){
queue<int> Q;
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(Count,0,sizeof(Count));
Q.push(sor);
vis[sor]=1;
dis[sor]=1;
Count[sor]++;
while(!Q.empty()){
int now=Q.front();
Q.pop();
for(int i=head[now];i;i=nex[i]){ //i = cnt
int v=to[i];
if(val[i]*dis[now]>dis[v]){
dis[v]=val[i]*dis[now];
if(!vis[v]){
Q.push(v);
vis[v]=1;
Count[v]++;
if(Count[v]>stu+1) return 1;//成环就退出
}
}
}
vis[now]=0;
}
return 0;
}
bool are_u_ok(double T){
cnt=1;
memset(head,0,sizeof(head));
for(int i=1;i<=fla;i++) {
if(o[i]==1) add_edge(b[i],a[i],c[i]-T);
else add_edge(b[i],a[i],1.0/(c[i]+T));
}
for(int i=1;i<=q;i++){
add_edge(0,aim[i],mark[i]);
add_edge(aim[i],0,1.0/mark[i]);
}
return spfa(0);
}
int main(){
cin>>stu>>fla>>q;
double ll=0,rr=0;
for(int i=1;i<=fla;i++){
scanf("%d %d %d %d",&o[i],&a[i],&b[i],&c[i]);
rr=max(rr,(double)c[i]);// 至少一个k-t>0
}
for(int i=1;i<=q;i++){
scanf("%d %d",&aim[i],&mark[i]);
}
double mid=0;
while(rr-ll>jingdu){
mid=(ll+rr)/2;
if(are_u_ok(mid)) ll=mid;
else rr=mid;
}
if(ll>jingdu) printf("%lf",ll);
else cout<<-1;
return 0;
}