题目描述
抽象题意:
题目要求求出 在环上,(点权值和/边权值和)最大。
思路
像这种 求谁/谁 最大----> 01分数规划问题
01规划问题做题步骤:
①确认答案区间,假设二分出了一个答案mid。
②推导公式,这个公式往往可以抽象成一个图论问题
③写代码:二分模板+图论算法模板
以下是上述的做题步骤的诠释:
首先 点权值和/边权值和 的答案区间一定在[1,1000]之间。
假如一个二分答案为mid,那么我们列公式:
因此上述推导出的公式我们把它抽象出一个图论问题:
- 判断是否存在mid,在一个环中,如果把每条边的边权值看作f[i]-mid*t[i],使得这个环的边权值和>0。
- 由此相当于让我们在一个边权值都是f[i]-mid*t[i]的图中判断是否存在正环。又因为要最大,通过二分缩小区间即可实现。
java 代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static int n,m;
public static int N=1010,M=5010;
public static int[] e=new int[M],ne=new int[M],h=new int[N],w=new int[M];
public static int idx;
public static int[] f=new int[N];
public static double[] dist=new double[N];
public static int[] cnt=new int[N];
public static boolean[] st=new boolean[N];
public static void main(String[] args) {
Arrays.fill(h,-1);
Scanner scan=new Scanner(System.in);
n=scan.nextInt();//点
m=scan.nextInt();//边
for(int i=1;i<=n;i++){
f[i]=scan.nextInt();
}
for(int i=0;i<m;i++){
int a=scan.nextInt();
int b=scan.nextInt();
int c=scan.nextInt();
add(a,b,c);
}
double l=0,r=1000;
while(r-l>1e-4){
double mid=(l+r)/2;
if(check(mid)){
l=mid;
}else {
r=mid;
}
}
System.out.printf("%.2f",l);
}
public static boolean check(double mid){
Arrays.fill(dist,0);
Arrays.fill(st,false);
Arrays.fill(cnt,0);
Queue<Integer> q=new LinkedList<>();
for(int i=1;i<=n;i++){
q.add(i);
st[i]=true;
}
while(!q.isEmpty()){
int t=q.poll();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]<dist[t]+(f[t]-mid*w[i])){//求正环,因此求最长路;求负环,才是求最短路
dist[j]=(dist[t]+(f[t]-mid*w[i]));
cnt[j]=cnt[t]+1;
if(cnt[j]>=n){
return true;
}
if(st[j]==false){
q.add(j);
st[j]=true;
}
}
}
}
return false;
}
public static void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
}