//完全背包public int change(int amount, int[] coins) {int []dp=new int[amount+1];//组合问题:初始化非0下标为0,0下标为1Arrays.fill(dp,0);dp[0]=1;//组合问题先遍历物品,后遍历背包for (int i = 0; i <coins.length; i++) {for (int j = coins[i]; j <=amount ; j++) {//组合问题递推公式为加和dp[j]+=dp[j-coins[i]];}}return dp[amount];}

public int findMaxForm(String[] strs, int m, int n) {int [][]dp=new int[m+1][n+1];//m为0,n为1for (String str : strs) {int zero=0,one=0;for (char c:str.toCharArray()){if (c=='0') zero++;else one++;}for (int i = m; i >=zero ; i--) {for (int j = n; j>=one; j--) {dp[i][j]=Math.max(dp[i][j],dp[i-zero][j-one]+1);}}}return dp[m][n];}

public int findTargetSumWays(int[] nums, int target) {int sum=0;for (int i = 0; i < nums.length; i++) {sum+=nums[i];}if ((sum+target)%2==1) return 0; //如果除2有余数说明没有组合,只求正数部分或负数部分if (Math.abs(target)>sum) return 0; //如果目标值的绝对值都大于sum,那么怎么都凑不出来组合了int bagSize=(sum+target)/2; //背包容量int []dp=new int[bagSize+1];Arrays.fill(dp,0);dp[0]=1;//初始化dp[0]=1for (int i = 0; i <nums.length ; i++) {for (int j = bagSize; j >=nums[i] ; j--) {//01背包的组合问题递推公式与之前的不同,组合问题的dp公式是累加dp[j]=dp[j]+dp[j-nums[i]];}}return dp[bagSize];}

//本题目可以转换为:容量为num/2的背包,这n个物品的体积和价值都相等,求dp[sum/2]是否等于sum/2class Solution {public boolean canPartition(int[] nums) {int target=0;for (int num : nums) {target+=num;}if (target%2!=0) return false;target/=2;int []dp=new int[target+1];Arrays.fill(dp,0);for (int i = 0; i <nums.length ; i++) {for (int j = target; j >=nums[i] ; j--) {dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);}}if (dp[target]==target) return true;else return false;}}//当dp[target]=target,说明在sum/2的容量下,里面的数字之和刚好也为sum/2//01背包不仅能解决最大价值问题,还可以解决能否装满背包的问题

class Solution {public int integerBreak(int n) {int []dp=new int[n+1];dp[2]=1; //dp[0]和dp[1]无意义，初始化dp2为1，因为递推公式与前面的有关，所以从前往后遍历for (int i = 3; i <=n; i++) {for (int j = 1; j <=i/2 ; j++) {dp[i]=Math.max(dp[i],Math.max(dp[i-j]*j,j*(i-j)));  //dp[i]表示从i为3开始到最后查找的最大，第三项表示只拆分一次，第二项表示可以拆分多次}}return dp[n];}}

我哥28才找到的对象，而我从出生到现在没谈过恋爱😇你们都什么时候找到的对象

import java.util.*;public class Main {static int []dp;static Scanner sc = new Scanner(System.in);public static void main(String[] args) {int n= sc.nextInt();//商品个数int V=sc.nextInt(); //背包容量int []w=new int[n]; //物品价值int []v=new int[n]; //物品体积dp=new int[V+1];for (int i = 0; i < n; i++) {v[i]=sc.nextInt();w[i]=sc.nextInt();}//先遍历物品后遍历背包,倒序遍历for (int i = 0; i <n; i++) {for (int j = V; j >=v[i] ; j--) {dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);}}System.out.println(dp[V]);}}

import java.util.*;public class Main {static Scanner sc = new Scanner(System.in);static final int INF = Integer.MAX_VALUE;// 边类：存储邻接表中的边信息static class Edge {public Edge(Integer t, Integer w) {this.t = t;  // 目标节点this.w = w;  // 边权重}Integer t;  // 目标节点编号Integer w;  // 边的权重}public static void main(String[] args) {// 输入：n个节点，m条边int n, m;n = sc.nextInt();m = sc.nextInt();// 邻接表：graph[i]表示从节点i出发的所有边List<List<Edge>> graph = new ArrayList<>();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}// 建图过程int s, t, w;for (int i = 0; i < m; i++) {s = sc.nextInt();  // 起点t = sc.nextInt();  // 终点w = sc.nextInt();  // 权重boolean found = false;// 检查是否已存在s->t的边（处理重边）for (Edge edge : graph.get(s)) {if (edge.t.equals(t)) {  // 找到相同边if (edge.w > w) {    // 保留最小权重edge.w = w;}found = true;break;}}// 如果没有找到相同边，添加新边if (!found) {graph.get(s).add(new Edge(t, w));}}// Dijkstra算法核心数据结构int[] mindist = new int[n + 1];    // 最短距离数组：mindist[i] = 从起点1到i的最短距离boolean[] visited = new boolean[n + 1];  // 访问标记数组：visited[i] = 节点i是否已确定最短路径int start = 1, end = n;  // 起点为1，终点为n// 初始化：起点距离为0，其他为无穷大Arrays.fill(mindist, INF);mindist[start] = 0;// Dijkstra主循环：执行n次（最多n个节点）for (int i = 1; i <= n; i++) {int cur = -1;      // 当前选择的节点int minVal = INF;  // 当前最小距离// 在未访问节点中找距离最小的节点for (int j = 1; j <= n; j++) {if (!visited[j] && mindist[j] < minVal) {minVal = mindist[j];cur = j;}}// 如果没有可选节点，提前退出if (cur == -1) break;visited[cur] = true;  // 标记当前节点已确定最短路径// 松弛操作：更新当前节点的所有邻接点距离for (Edge edge : graph.get(cur)) {// 如果通过cur到edge.t的距离更短，则更新if (mindist[cur] + edge.w < mindist[edge.t]) {mindist[edge.t] = mindist[cur] + edge.w;}}}// 输出结果if (mindist[end] == INF) {  // 无法到达终点System.out.println(-1);} else {  // 可达，输出最短距离System.out.println(mindist[end]);}sc.close();}}

import java.util.*;public class Main {static Scanner in=new Scanner(System.in);public static void main(String[] args) {int n,m,start;n=in.nextInt();m=in.nextInt();start=in.nextInt();int [][]graph=new int[n+1][n+1];for (int i = 0; i <= n; i++) {Arrays.fill(graph[i],Integer.MAX_VALUE);}for (int i = 0; i < m; i++) {int u = in.nextInt();int v = in.nextInt();int w = in.nextInt();//如果有重边,需要取最小,如果没有直接读入即可graph[u][v] = Math.min(graph[u][v], w);}int[] minDist=new int[n+1];//初始节点为0,其他设为遥不可及Arrays.fill(minDist,Integer.MAX_VALUE);minDist[start]=0;boolean[] visited=new boolean[n+1];//遍历所有节点for (int i=1;i<=n;i++){int cur=start;int minVal=Integer.MAX_VALUE;//找一个数组中最小的那个值并获取最小值的索引for (int j = 1; j <=n ; j++) {if (!visited[j]&&minDist[j]<minVal){minVal=minDist[j];cur=j;}}//标记当前节点访问过visited[cur]=true;//遍历当前节点能直接到达的所有路径,并更新所有未访问节点到原点的距离for (int j = 1; j <=n; j++) {//三个条件:未访问过,新路径比原路径小,当前位置指向的不是遥不可及的节点(也就是可以直接指向)if (!visited[j]&&graph[cur][j]+minDist[cur]<minDist[j]&&graph[cur][j]!=Integer.MAX_VALUE) {minDist[j]=minDist[cur]+graph[cur][j];}}}System.out.print(minDist[1]);for (int i = 2; i <=n ; i++) {System.out.print(" "+minDist[i]);}}}//使用邻接矩阵可能超内存//迪杰斯特拉算法的权值不能有负数

import java.util.*;public class Main {static Scanner in=new Scanner(System.in);public static void main(String[] args) {int n,m;n=in.nextInt();m=in.nextInt();int []inDegree=new int[n+1];List<List<Integer>> umap=new ArrayList<>();for (int i = 0; i < n; i++) {umap.add(new ArrayList<>());}for (int i = 0; i < m; i++) {int s,t;s=in.nextInt();t=in.nextInt();//记录s指向的节点有哪些,然后让t入度自增umap.get(s).add(t);inDegree[t]++;}//把入度为0的点都加入队列Deque<Integer> queue=new ArrayDeque<>();for (int i = 0; i < n; i++) {if (inDegree[i]==0){queue.offer(i);}}List<Integer>result=new ArrayList<>();//遍历队列while (!queue.isEmpty()){//加入结果int cur=queue.poll();result.add(cur);//获取当前节点指向的节点,并把指向节点的入度减一,如果入度为0加入队列for (Integer i : umap.get(cur)) {inDegree[i]--;if (inDegree[i]==0){queue.offer(i);}}}//如果有节点没有加入,说明成环无答案if (result.size()!=n){System.out.println(-1);return;}System.out.print(result.get(0));for (int i = 1; i <result.size() ; i++) {System.out.print(" "+result.get(i));}}}

import java.util.Arrays;import java.util.Scanner;public class Main {static Scanner in=new Scanner(System.in);//并查集static int n;static int[] parent;static void init(){for (int i = 1; i <= n; i++) {parent[i]=i;}}static int find(int a){if (parent[a]==a) {return a;}parent[a]=find(parent[a]);return parent[a];}static void join(int a,int b){a=find(a);b=find(b);if (a==b){return;}parent[a]=b;}static boolean isSame(int a,int b){return find(a)==find(b);}//存边的类static class Edge{int u,v,w;public Edge(int u, int v, int w) {this.u = u;this.v = v;this.w = w;}}public static void main(String[] args) {int m;n=in.nextInt();m=in.nextInt();parent=new int[n+1];init();//存边Edge[] edges=new Edge[m];for (int i = 0; i < m; i++) {int u=in.nextInt();int v=in.nextInt();int w=in.nextInt();edges[i]=new Edge(u,v,w);}//排序,(a,b)->a.w-b.w表示从小到大,若b.w-a.w表示从大到小Arrays.sort(edges, (a,b)->a.w-b.w);//used表示一共访问了几条边,ans是权值总和int used=0;int ans=0;//把所有的边取出,判断两个节点是否在一个集合里,如果是,则跳过,如果不在则加入集合并且让ans加上权,标记访问for (Edge edge : edges) {if (isSame(edge.u,edge.v)){continue;}join(edge.u,edge.v);ans+=edge.w;used++;//当找到n-1条边后,跳出循环,注意不要写成returnif (used==n-1){break;}}//如果访问过的节点不是n-1,说明不成环无法连接if (used!=n-1){System.out.println("不成环");}else {System.out.println(ans);}}}

import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in =new Scanner(System.in);int  n= in.nextInt();int  m=in.nextInt();//初始化图为最大数字int[][] grid=new int[n+1][n+1];for (int i = 0; i <=n ; i++) {Arrays.fill(grid[i],Integer.MAX_VALUE);}for (int i = 0; i < m; i++) {int s=in.nextInt();int t=in.nextInt();int v=in.nextInt();//如果有重边,需要取最小,即输入数据可能为:// 2 4 44// 4 2 206// 后面的206会覆盖掉前面的44导致答案错误,需要取最小grid[s][t]=grid[t][s]=Math.min(v,grid[t][s]);}int []mindist=new int[n+1];Arrays.fill(mindist,Integer.MAX_VALUE);//从节点1开始mindist[1]=0;boolean []isInTree=new boolean[n+1];//找n-1条边for (int i =1; i < n; i++) {int minVal=Integer.MAX_VALUE;int cur=-1;//找到最小的权值,获取最小权值和他的索引for (int j=1;j<=n;j++){if (!isInTree[j]&&mindist[j]<minVal){minVal=mindist[j];cur=j;}}//如果除了第一步之外,选到的最小值仍然是max,说明图不联通if (cur==-1){//后面的判断条件可以不写,是等价的||minVal==Integer.MAX_VALUESystem.out.println("不成环");return;}//加入生成树isInTree[cur]=true;//更新所有非生成树节点到树的距离for (int j = 1; j <= n; j++) {if (!isInTree[j]&&grid[cur][j]<mindist[j]){mindist[j]=grid[cur][j];}}}//获取结果int result=0;for (int i = 2; i <=n ; i++) {result+=mindist[i];}System.out.println(result);in.close();}}

public class Main {static int n;static int[] parent;public static void main(String[] args) {}//初始化static void  init (){for (int i = 0; i < n; i++) {parent[i]=i;}}//查找根static int find(int u){if (u== parent[u]){return u;}//路径压缩parent[u]=find(parent[u]);return parent[u];}//判断是否同集合static boolean isSame(int a,int b){return find(a)==find(b);}//添加static void join(int  a,int b){a=find(a);b=find(b);if (a==b){return;}parent[a]=b;}}

import javax.xml.transform.Result;import java.util.*;public class Main {//有向图的完全联通，采用邻接表存储图static Scanner in=new Scanner( System.in);static List<List<Integer>> graph=new ArrayList<>();static boolean[] visited;//public static void main(String[] args) {int n, k;n=in.nextInt();k=in.nextInt();visited=new boolean[n+1];//初始化图，由于题目要求从1开始，所以本题所有下标从1开始for (int i = 0; i < n+1; i++) {graph.add(new ArrayList<>());}for (int i = 1; i <1+ k; i++) {graph.get(in.nextInt()).add(in.nextInt());}dfs(1);//如果有节点没被遍历到，输出-1后返回，反之输出1for (int i=1;i<1+n;i++){if (!visited[i]){System.out.println(-1);return;}}System.out.println(1);}//把能连接到的节点都标记为访问static void dfs(int x){if (visited[x]){return;}visited[x]=true;List<Integer> list=graph.get(x);for (Integer next : list) {dfs(next);}}}