Java实现蓝桥杯算法训练 Remember the A La Mode（暴力）

朴灿烈づ我的快乐病毒、 2023-07-25 06:29 15阅读 0赞

## 试题 算法训练 Remember the A La Mode ##

问题描述  
　　Hugh Samston经营着一个为今年的ICPC世界总决赛的参与者提供甜点的餐饮服务。他将会提供上面有冰激凌的饼片。为了满足不同的需求，他准备了许多不同的饼片和冰激凌。  
　　Hugh希望以一份饼片上一份冰激凌的方式来提供甜点。然而，作为一个商人，他希望能赚到尽可能多的钱。他知道不同种类的饼片和冰激凌组合的价格，也知道那些冰激凌和那些饼片不能组合在一起。  
　　Hugh想根据每种饼片和冰激凌的数量，以及之前提到的不同组合的情况，确定他能获得的利润的范围。  
输入格式  
　　测试数据的输入一定会满足的格式。  
　　输入的第一行包含两个整数P, I，分别表示饼片和冰激凌的种类数。  
　　接下来一行包含P个整数，表示每种类型饼片的数量。  
　　接下来一行包含I个整数，表示每种类型冰激凌的数量。  
　　接下来P行，每行包含I个实数，表示每种类型饼片和冰激凌组合的结果。  
　　如果这种饼片和这种冰激凌可以组合，则为一个(0,10)的实数，表示这种组合的收益。  
　　否则，则为-1,表示这两种之间不能组合。  
输出格式  
　　输出一行，以"(最小收益) to (最大收益)"的方式输出利润的范围。

请注意：所有的饼片和冰激凌都必须用完。  
样例输入  
2 3  
40 50  
27 30 33  
1.11 1.27 0.70  
\-1 2 0.34  
样例输出  
91.70 to 105.87  
数据规模和约定  
　　0 < P,I <= 50，每种类型饼片或冰激凌数量不超过100。

PS：

## `这个题给我晕坏了，我的天，这半天就肝了这么几道题，躺了，浑身晕` ##

import java.math.BigDecimal;
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Main { 
    	static int[] PArray, IArray, pre, dis;
    	
    	/*分别用来保存P和I的数量，pre和dis用作SPFA算法中保存前节点和点到源点的距离*/
    	
    	static int[][] Weight;
    	
    	/* 保存权重 */
    	
    	static List<List<Integer>> index;
    	
    	/* index[i]表示所有从i出发的边的集合 */
    	
    	static int minCost = 0, maxCost = 0, P, I,count = -1;
    	
    	static List<Edge> E;
    	
    	/* 保存图中所有边 */
    	
    	public static void main(String[] args) 
    	{ 
    		Scanner sc = new Scanner(System.in);
    		P = sc.nextInt();
    		I = sc.nextInt();
    		PArray = new int[P];
    		IArray = new int[I];
    		pre = new int[P + I + 2];
    		dis = new int[P + I + 2];
    		Weight = new int[P + I + 2][P + I + 2];
    		index = new ArrayList<List<Integer>>();
    		E = new ArrayList<Edge>();
    		sc.nextLine();
    		
    		for (int i = 0; i < P + I + 2; i++)
    		{ 
    			index.add(new ArrayList<Integer>());
    		}
    		for (int i = 0; i < P; i++)
    		{ 
    			PArray[i] = sc.nextInt();
    		}
    		sc.nextLine();
    		for (int i = 0; i < I; i++)
    		{ 
    			IArray[i] = sc.nextInt();
    		}
    		sc.nextLine();
    		for (int i = 1; i <= P; i++)
    		{ 
    			for (int j = P + 1; j <= I + P; j++)
    			{ 
    				BigDecimal in = new BigDecimal(Double.toString(sc.nextDouble()));
    				in = in.multiply(new BigDecimal(100));
    				String toStr = in.toString();
    				int num = Integer.parseInt(toStr.substring(0, toStr.indexOf('.')));
    				Weight[i][j] = num;
    				if (num != -100)
    				{ 
    					add(i, j, Math.min(PArray[i - 1], IArray[j - P - 1]), 0, -num);
    					add(j, i, 0, 0, num);
    					/* 同时构造边和反向边，正向边的权重先取反，来求最大花费 */
    				}
    			}
    			sc.nextLine();
    		}
    		for (int i = 1; i <= P; i++)
    		{ 
    			add(0, i, PArray[i - 1], 0, 0);
    			add(i, 0, 0, 0, 0);
    			/* 构造超级源点的边以及反向边 */
    		}
    		
    		for (int i = P + 1; i <= P + I; i++)
    		{ 
    			add(i, P + I + 1, IArray[i - P - 1], 0, 0);
    			add(P + I + 1, i, 0, 0, 0);
    			/* 构造超级汇点的边以及反向边 */
    		}
    		MCMF(0, P + I + 1);
    		maxCost = -minCost;
    		E.clear();
    		minCost = 0;
    		
    		/* 重新按照weight数组保存的权重值构造Edge集合，来计算最小收益 * 事先已经构造好index集合，这次可以直接向E中add */
    		for (int i = 1; i <= P; i++)
    		{ 
    			for (int j = P + 1; j <= I + P; j++)
    			{ 
    				if (Weight[i][j] != -100)
    				{ 
    					E.add(new Edge(i, j, Math.min(PArray[i - 1], IArray[j - P - 1]), 0, Weight[i][j]));
    					E.add(new Edge(j, i, 0, 0, -Weight[i][j]));
    				}
    			}
    		}
    		for (int i = 1; i <= P; i++)
    		{ 
    			E.add(new Edge(0, i, PArray[i - 1], 0, 0));
    			E.add(new Edge(i, 0, 0, 0, 0));
    		}
    		
    		for (int i = P + 1; i <= P + I; i++)
    		{ 
    			E.add(new Edge(i, P + I + 1, IArray[i - P - 1], 0, 0));
    			E.add(new Edge(P + I + 1, i, 0, 0, 0));
    		}
    		MCMF(0, I + P + 1);
    		System.out.format("%.2f to %.2f", minCost / 100.0, maxCost / 100.0);
    	}
    	
    	public static void add(int from, int to, int cap, int flow, int weight)
    	{ 
    		/* 构造并保存边时，同时填写index */
    		E.add(new Edge(from, to, cap, flow, weight));
    		count++;
    		index.get(from).add(count);
    	}
    	
    	public static Edge getByNum(int from, int to, List<Edge> E)
    	{ 
    		/* 通过起点和终点确定边 */
    		for (int i : index.get(from))
    		{ 
    			if (E.get(i).to == to)
    			{ 
    				return E.get(i);
    			}
    		}
    		return null;
    	}
    	
    	public static void MCMF(int s, int n)
    	{ 
    		while (SPFA(s, n))
    		{ 
    			int now = n, minFlow = Integer.MAX_VALUE;
    			while (now != s)
    			{ 
    				/* 算出增广路径上每条边上能允许多出的最大流 */
    				minFlow = Math.min(minFlow, getByNum(pre[now], now, E).cap);
    				now = pre[now];
    			}
    			now = n;
    			minCost += minFlow * dis[n];
    			while (now != s)
    			{ 
    				/* 增广路径上每条边的容量减少minFlow， 反向路径则增加minFlow */
    				getByNum(pre[now], now, E).cap -= minFlow;
    				getByNum(now, pre[now], E).cap += minFlow;
    				now = pre[now];
    			}
    		}
    	}
    	
    	public static boolean SPFA(int s, int n)
    	{ 
    		/* 寻找s-n增广路径， 并用pre保存这条路径上每个节点的前节点 */
    		Queue<Integer> Q = new LinkedList<Integer>();
    		for (int i = 0; i < dis.length; i++)
    		{ 
    			dis[i] = Integer.MAX_VALUE;
    			pre[i] = -1;
    		}
    		int[] count = new int[102];
    		Q.add(s);
    		dis[s] = 0;
    		pre[s] = -1;
    		count[s]++;
    		while (!Q.isEmpty())
    		{ 
    			int from = Q.poll();
    			for (int i : index.get(from))
    			{ 
    				if (E.get(i).cap > 0)
    				{ 
    					Edge e = E.get(i);
    					int to = e.to;
    					if (dis[to] > dis[from] + e.weight)
    					{ 
    						/* relax操作 */
    						dis[to] = dis[from] + e.weight;
    						pre[to] = from;
    						if (!Q.contains(to))
    						{ 
    							Q.add(to);
    							count[to]++;
    							if (count[to] > n)
    							{ 
    								return false;
    							}
    						}
    					}
    				}
    			}
    		}
    		return !(pre[n] == -1);
    		/* 单纯写成 return true 则在pre数组全是-1的情况下也会return true */
    	}
    
    }
    
    class Edge
    { 
    	int from, to, cap, flow, weight;
    	
    	public Edge(int f, int t, int c, int fl, int w)
    	{ 
    		this.from = f;
    		this.to = t;
    		this.cap = c;
    		this.flow = fl;
    		this.weight = w;
    	}
    }