2.牛奶工厂
题目链接：牛奶工厂https://www.acwing.com/problem/content/1473/
题目分析：
如果明白了上一道题，那么这道题也会马上明白思路，因为做法是完全一模一样的。我们直接写上状态表示和转移方程就能明白了。
状态表示 f[i][j]=true说明从i能走到j static boolean[][] f=new boolean[N][N]; 转移方程： //同理如果能找到一条从i到k，再从k到j，说明能从i到j f[i][j]|=(f[i][k]&&f[k][j]);
代码转换：
import java.util.Scanner; public class Main { static int N=110; //f[i][j]=true说明从i能走到j static boolean[][] f=new boolean[N][N]; static int n; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); for (int i = 0; i < n-1; i++) { int a=sc.nextInt(); int b=sc.nextInt(); f[a][b]=true; } for (int k = 1; k <=n; k++) { for (int i = 1; i <=n; i++) { for (int j = 1; j <=n; j++) { f[i][j]|=(f[i][k]&&f[k][j]); } } } for (int i = 1; i <=n; i++) { int res=0; for (int j = 1; j <=n; j++) { //注意我们找的是能从其他点都能到i点 if (f[j][i]) res++; } if (res>=n-1){ System.out.println(i); return; } } System.out.println(-1); } }
3.最短路径
给定一个 n 个点 m 条边构成的无重边和自环的无向连通图。
点的编号为 1∼n。
请问：
从 1 到 n 的最短距离。
去掉 k 条边后，从 1 到 n 的最短距离。
题目链接：最短路径 https://www.acwing.com/problem/content/description/3559/
这是一道Floyd的练手模板题，不过题目存在一些要注意的问题，是多组测试数据所以每次我们都需要初始化一下数组，然后需要存一下需要删除的边，而且图是无向图。这里直接贴上模板代码。
import java.util.*; public class Main { static int N=60; static int[][] g=new int[N][N]; static int[][] bck=new int[N][N]; static int n,m,k,INF=0x3f3f3f3f; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while (t-->0){ n=sc.nextInt(); m=sc.nextInt(); k=sc.nextInt(); init(); List<int[]> list=new ArrayList<>(); for (int i = 0; i < m; i++) { int a=sc.nextInt(); int b=sc.nextInt(); int w=sc.nextInt(); g[a][b]=g[b][a]=w; bck[a][b]=bck[b][a]=w; list.add(new int[]{a,b}); } System.out.println(floyd(g)); for (int i = 0; i < k; i++) { int m=sc.nextInt(); int[] curr=list.get(m-1); int a=curr[0]; int b=curr[1]; bck[a][b]=bck[b][a]=INF; } System.out.println(floyd(bck)); } } static int floyd(int[][] f){ for (int k = 1; k <=n; k++) { for (int i = 1; i <=n; i++) { for (int j = 1; j <=n; j++) { f[i][j]= Math.min(f[i][j],f[i][k]+f[k][j]); } } } return f[1][n]==INF?-1:f[1][n]; } static void init(){ for (int i = 1; i <=n; i++) { Arrays.fill(g[i],INF); Arrays.fill(bck[i],INF); g[i][i]=bck[i][i]=0; } } }
