题目描述
抽象题意:
xi表示第i个小朋友分到的糖果数量
求解所有xi最小值,算出所有xi的和即为老师需要准备的糖果数。
原理
1.求不等式的可行解:
○ 将不等式转化为边:
□ 可以将不等式转化为xi<=xj+ck的形式(a)
□ 也可以将不等式转化为xi>=xj+ck的形式(b)
□ 建立一条从j ----ck---->i的边
○ 根据上面的转化形式对应求最短路或最长路
□ 对于(a)这种形式,我们求最短路,这样满足每个点的dist[i]<=dist[j]+ck。刚好与我们的不等式对应。因此dist[i]就是这个不等式的可行解
□ 对于(b)这种形式,我们求最长路,这样满足每个点的dist[i]>=dist[j]+ck。刚好与我们的不等式对应。因此dist[i]就是这个不等式的可行解
□ 注意:我们知道,求最短路最长路都需要确立一个源点,这个源点要满足从这个源点出发,能遍历所有边。
2.求不等式可行解的最小值或最大值:
○ 注意这种情况与上面的情况差别就在于我们不仅要求出可行解,我们还要保证这个解是最小或最大的。
○ 与上面做法不同在于,上面是可以任意选择将不等式转化为>或<的形式,然后求最短路或最长路都可以。而这里的结论是:
□ 如果求可行解的最大值,则求最短路。
□ 如果求可行解的最小值,则求最长路。
○ 其他的都与上面求可行解的做法一样。
• 为什么求最短路就可以得到最大值呢?
§ 所有从x[i]出发,构成的不等式链
x[i] ≤ x[j] + c[j]
≤ x[k] + c[k] + c[j]
≤ x[0] + c[1]+ c[2]+... + c[j]
= 0 + c[1]+ ... + c[j]
最终x[i]的最大值
=所有上界的最小值
§ 而这个上界其实就是路径和,我们要路径和最小,所以我们要求最短路。
这道题的思路
因此,我们要求xi最小值的话,
1.确定怎么转化不等式,建边。
• 求最小值,将不等式转化为xi>=xj+ck的形式,建立i和j之间的边。
1.xi==xj <=> xi>=xj xj>=xi
2.xi<=xj <=> xj>=xi
3.xi>=xj <=> xi>=xj
4.xi>xj <=> xi>=xj+1
5.xi<=xj <=> xj>=xi
6.xi>=1 <=> xi>=x0+1
2.确定源点:x0,求最长路。
算法1
import java.util.*;
public class Main {
public static int n,idx;
public static int N=100010,M=300010,INF=0x3f3f3f3f;
public static int[] dist=new int[N],cnt=new int[N];
public static boolean[] st=new boolean[N];
public static int[] e=new int[M],ne=new int[M],w=new int[M],h=new int[N];
public static void main(String[] args) {
Arrays.fill(h,-1);
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
int k=scan.nextInt();
for(int i=1;i<=n;i++){
add(0,i,1);
}
while(k-->0){//建图
int x=scan.nextInt();
int a=scan.nextInt();
int b=scan.nextInt();
if(x==1) {
add(b, a, 0);
add(a, b, 0);
}else if(x==2){
add(a,b,1);
}else if(x==3){
add(b,a,0);
}else if(x==4){
add(b,a,1);
}else if(x==5){
add(a,b,0);
}
}
if(!spfa()){
System.out.println("-1");
}else {
long ans=0;
for(int i=1;i<=n;i++){
ans+=dist[i];
}
System.out.println(ans);
}
}
//spfa求最长路+判断是否存在负环
//为什么这里求负环,不用将所有点先加入队列:
//首先我们要知道将所有点加入队列的原理是怕会漏掉一些边没有遍历到
//怕会漏掉负环没判断,而这里已经确定从源点开始可以遍历到所有边,
//所有不需要再都加到队列里了。
public static boolean spfa(){
Arrays.fill(dist,-INF);//求最长路,要初始化为-INF
dist[0]=0;
Stack<Integer> q=new Stack<>();
q.push(0);
st[0]=true;
while(!q.isEmpty()){
int t=q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]<dist[t]+w[i]){
dist[j]=dist[t]+w[i];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n+1){
return false;
}
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
return true;
}
public static void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
}