自动搬运

查看原文

来自洛谷，原作者为

	lmq308270 I AM Liumengqi ：-）

搬运于2025-08-24 23:02:51，当前版本为作者最后更新于2025-03-19 10:11:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

01 分数规划+判负环

我们可以将每条线路的起点与终点看作点速度和看作边权，然后二分 01 分数规划。 发现判负环即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int e[N],ne[N],h[N],tot;
int x,n,m,t,w[N],st;
double l,r,mid,ans=-1,len[N],d[N];
bool flag,vis[N];
void add(int x,int y){
   e[++tot]=y,ne[tot]=h[x],h[x]=tot;
}//添加函数
int f(char ch){
   switch(ch){
   	case 'S': t=0;return 1000;
   	case 'G': t=1;return 500;
   	case 'D': t=2;return 300;
   	case 'T': t=3;return 200;
   	case 'K': t=4;return 150;
   }
   return -1;
}//打表
bool dfs(int x){
   vis[x]=1;
   for(int i=h[x];i;i=ne[i]){
   	int y=e[i];double z=len[i];
   	if(d[y]>d[x]+z){
   		d[y]=d[x]+z;
   		if(vis[y]||dfs(y)) return 1;
   	}
   }
   vis[x]=0;
   return 0;
}
bool check(double x){
   for(int i=1;i<=m;++i) len[i]=x-w[i];
   memset(vis,0,sizeof vis);
   memset(d,0x3f,sizeof d);
   for(int i=1;i<N;++i)
   	if(dfs(i)) return 1;
   return 0;
}
int main()
{
   scanf("%d",&m);
   for(int i=1;i<=m;i++){
   	char s[114];
   	scanf("%s",s);
   	x=0,flag=0,n=strlen(s);
   	for(int j=0;j<n;j++){
   		if('0'<=s[j]&&s[j]<='9')x=x*10+s[j]-'0';//数位分离
   		else if(s[j]=='-'){
   			if(!flag) st=x+t*10000;//映射
   			flag=1;
   			x=0;
   		}
   		else w[i]+=f(s[j]);
   	}
   	int ed=x+t*10000;
   	add(st,ed);
   }
   l=0,r=0x3f3f3f3f;
   while(r-l>1e-8){
   	double mid=(l+r)/2;
   	if(check(mid)) l=mid;
   	else r=mid; 
   }
   if(l==0){
   	cout<<-1;
   	return 0;
   }//别忘了没有输出-1
   printf("%.0f\n" ,l);
   return 0;
}