图论练习6

[NOIP2013]车站分级

Here

 解题思路

  • 由于起始点之间所选的站号，相互之间一定满足\geq
  • 那么对于起始点间未选择的站号，一定满足<选择的站号
  • 考虑用边来维护<信息，u\rightarrow v表示u的级别大于v
  • 按题意，则车站会被分为几个联通块，且保证块内无环，即一定存在一个有序序列
  • 则通过拓扑排序，找到连通块内的最长路径，即为最小的必要分级数


import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;









public class Main{
	static long md=(long)998244353;
	static long Linf=Long.MAX_VALUE/2;
	static int inf=Integer.MAX_VALUE/2;


	public static void main(String[] args) throws IOException{
		AReader input=new AReader();
	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));	
	    /*
	     * 用有向边维护大于号
	     * 按题意，则车站会被分为几个联通块，且保证块内无环，即一定存在一个有序序列
	     * 最长的序列即为最小的必要分级数
	    */
	    
	    int n=input.nextInt();
	    int m=input.nextInt();
	    boolean[][] e=new boolean[n+1][n+1];
	    boolean[] vis=new boolean[n+1];
	    int[] st=new int[n+1];
	    int[] in=new int[n+1];
	    for(int i=1;i<=m;++i) {
	    	int t=input.nextInt();
	    	Arrays.fill(vis, false);
	    	for(int j=1;j<=t;++j) {
	    		int x=input.nextInt();
	    		vis[x]=true;
	    		st[j]=x;
	    	}
	    	for(int j=st[1];j<=st[t];++j) {
	    		if(vis[j])continue;
	    		for(int k=1;k<=t;++k) {
	    			if(e[st[k]][j])continue;
	    			e[st[k]][j]=true;
	    			in[j]++;
	    		}
	    	}
	    }
	    Queue<Integer> q=new LinkedList<Integer>();
	    for(int i=1;i<=n;++i)if(in[i]==0)q.add(i);
	    int[] a=new int[n+1];
	    Arrays.fill(a, 1);
	    while(!q.isEmpty()) {
	    	int x=q.peek();
	    	q.poll();
	    	for(int i=1;i<=n;++i) {
	    		if(e[x][i]) {
	    			a[i]=Math.max(a[i], a[x]+1);
	    			in[i]--;
	    			if(in[i]==0)q.add(i);
	    		}
	    		
	    	}
	    }
	    int mx=0;
	    for(int i=1;i<=n;++i)mx=Math.max(mx, a[i]);
	    out.print(mx);
 	    out.flush();
	    out.close();
	}
	//System.out.println();
	//out.println();
	static
	class AReader{ 
	    BufferedReader bf;
	    StringTokenizer st;
	    BufferedWriter bw;

	    public AReader(){
	        bf=new BufferedReader(new InputStreamReader(System.in));
	        st=new StringTokenizer("");
	        bw=new BufferedWriter(new OutputStreamWriter(System.out));
	    }
	    public String nextLine() throws IOException{
	        return bf.readLine();
	    }
	    public String next() throws IOException{
	        while(!st.hasMoreTokens()){
	            st=new StringTokenizer(bf.readLine());
	        }
	        return st.nextToken();
	    }
	    public char nextChar() throws IOException{
	        //确定下一个token只有一个字符的时候再用
	        return next().charAt(0);
	    }
	    public int nextInt() throws IOException{
	        return Integer.parseInt(next());
	    }
	    public long nextLong() throws IOException{
	        return Long.parseLong(next());
	    }
	    public double nextDouble() throws IOException{
	        return Double.parseDouble(next());
	    }
	    public float nextFloat() throws IOException{
	        return Float.parseFloat(next());
	    }
	    public byte nextByte() throws IOException{
	        return Byte.parseByte(next());
	    }
	    public short nextShort() throws IOException{
	        return Short.parseShort(next());
	    }
	    public BigInteger nextBigInteger() throws IOException{
	        return new BigInteger(next());
	    }
	    public void println() throws IOException {
	        bw.newLine();
	    }
	    public void println(int[] arr) throws IOException{
	        for (int value : arr) {
	            bw.write(value + " ");
	        }
	        println();
	    }
	    public void println(int l, int r, int[] arr) throws IOException{
	        for (int i = l; i <= r; i ++) {
	            bw.write(arr[i] + " ");
	        }
	        println();
	    }
	    public void println(int a) throws IOException{
	        bw.write(String.valueOf(a));
	        bw.newLine();
	    }
	    public void print(int a) throws IOException{
	        bw.write(String.valueOf(a));
	    }
	    public void println(String a) throws IOException{
	        bw.write(a);
	        bw.newLine();
	    }
	    public void print(String a) throws IOException{
	        bw.write(a);
	    }
	    public void println(long a) throws IOException{
	        bw.write(String.valueOf(a));
	        bw.newLine();
	    }
	    public void print(long a) throws IOException{
	        bw.write(String.valueOf(a));
	    }
	    public void println(double a) throws IOException{
	        bw.write(String.valueOf(a));
	        bw.newLine();
	    }
	    public void print(double a) throws IOException{
	        bw.write(String.valueOf(a));
	    }
	    public void print(char a) throws IOException{
	        bw.write(String.valueOf(a));
	    }
	    public void println(char a) throws IOException{
	        bw.write(String.valueOf(a));
	        bw.newLine();
	    }
	}
}

P4366 [Code+#4] 最短路

Here

解题思路

  • 主要是对于i\rightarrow j,w=(i\ xor j)*c，如何处理，避免建n(n-1)条边
  •  考虑二进制
  • i\rightarrow j，可以看作是通过某些w=2^k*c的边到达
  • 设k=2^k，则i\rightarrow (i\ xor \ k),w=k,(i\ xor\ k)\leq n，建边
  • 然后跑最短路即可
  • 注意3\rightarrow 4\Rightarrow 3\overset{1*c}{\rightarrow}2\overset{2*c}{\rightarrow}0\overset{4*c}{\rightarrow}4，需要添一点0
  • 边总共有m+n*20
  • 洛谷该题内存不够，可以点链接去牛客交

import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;












//implements Runnable
public class Main{
	static long md=(long)998244353;
	static long Linf=Long.MAX_VALUE/2;
	static int inf=Integer.MAX_VALUE/2;
	static int N=500010+20*100010;
	static int n=0;
	static int m=0;
	static int c=0;
	
	static
	class Edge{
		int fr,to,nxt;
		int val;
		public Edge(int u,int v,int w) {
			fr=u;
			to=v;
			val=w;
		}
	}
	static Edge[] e;
	static int[] head;
	static int cnt=0;
	static void addEdge(int fr,int to,int val) {
		cnt++;
		e[cnt]=new Edge(fr, to, val);
		e[cnt].nxt=head[fr];
		head[fr]=cnt;
	}
	static
	class Node{
		int x;
		int y;
		public Node(int u,int v) {
			x=u;
			y=v;
		}
	}
	static int Dij(int s,int t) {
		int[] dis=new int[n+1];
		Arrays.fill(dis, inf);
		boolean[] vis=new boolean[n+1];
		dis[s]=0;
		PriorityQueue<Node> q=new PriorityQueue<Node>((o1,o2)->{
			return o1.y-o2.y;
		});
		q.add(new Node(s, 0));
		while(!q.isEmpty()) {
			Node now=q.peek();
			q.poll();
			int x=now.x;
			if(vis[x])continue;
			vis[x]=true;
			for(int i=head[x];i>0;i=e[i].nxt) {
				int v=e[i].to;
				int w=e[i].val;
				if(vis[v])continue;
				if(dis[v]>dis[x]+w) {
					dis[v]=dis[x]+w;
					q.add(new Node(v, dis[v]));
				}
			}
		}
		return dis[t];
	}
	static void solve() throws Exception{
		AReader input=new AReader();
	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));	
	    n=input.nextInt();
	    m=input.nextInt();
	    c=input.nextInt();
	    e=new Edge[m+20*n+1];
	    head=new int[n+1];
	    cnt=0;
	    for(int i=1;i<=m;++i) {
	    	int u=input.nextInt();
	    	int v=input.nextInt();
	    	int w=input.nextInt();
	    	
	    	addEdge(u, v, w);
	    }
	    for(int i=0;i<=n;++i) {
	    	for(int j=1;j<=n;j<<=1) {
	    		int x=i^j;
	    		if(x>n)continue;
	    		addEdge(i, x, j*c);
	    	}
	    }
	    int s=input.nextInt();
	    int t=input.nextInt();
	    out.print(Dij(s, t));
 	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
		solve();
	}
//	public static final void main(String[] args) throws Exception {
//		  new Thread(null, new Main(), "线程名字", 1 << 27).start();
//	}
//		@Override
//		public void run() {
//			try {
//				//原本main函数的内容
//				solve();
//
//			} catch (Exception e) {
//			}
//		}
		static
		class AReader{ 
		    BufferedReader bf;
		    StringTokenizer st;
		    BufferedWriter bw;

		    public AReader(){
		        bf=new BufferedReader(new InputStreamReader(System.in));
		        st=new StringTokenizer("");
		        bw=new BufferedWriter(new OutputStreamWriter(System.out));
		    }
		    public String nextLine() throws IOException{
		        return bf.readLine();
		    }
		    public String next() throws IOException{
		        while(!st.hasMoreTokens()){
		            st=new StringTokenizer(bf.readLine());
		        }
		        return st.nextToken();
		    }
		    public char nextChar() throws IOException{
		        //确定下一个token只有一个字符的时候再用
		        return next().charAt(0);
		    }
		    public int nextInt() throws IOException{
		        return Integer.parseInt(next());
		    }
		    public long nextLong() throws IOException{
		        return Long.parseLong(next());
		    }
		    public double nextDouble() throws IOException{
		        return Double.parseDouble(next());
		    }
		    public float nextFloat() throws IOException{
		        return Float.parseFloat(next());
		    }
		    public byte nextByte() throws IOException{
		        return Byte.parseByte(next());
		    }
		    public short nextShort() throws IOException{
		        return Short.parseShort(next());
		    }
		    public BigInteger nextBigInteger() throws IOException{
		        return new BigInteger(next());
		    }
		    public void println() throws IOException {
		        bw.newLine();
		    }
		    public void println(int[] arr) throws IOException{
		        for (int value : arr) {
		            bw.write(value + " ");
		        }
		        println();
		    }
		    public void println(int l, int r, int[] arr) throws IOException{
		        for (int i = l; i <= r; i ++) {
		            bw.write(arr[i] + " ");
		        }
		        println();
		    }
		    public void println(int a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		    public void print(int a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void println(String a) throws IOException{
		        bw.write(a);
		        bw.newLine();
		    }
		    public void print(String a) throws IOException{
		        bw.write(a);
		    }
		    public void println(long a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		    public void print(long a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void println(double a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		    public void print(double a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void print(char a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void println(char a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		}
	}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/438544.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C#与python交互（flask发送Get/Post请求）

C#与python交互（flask发送Get/Post请求）

先运行python&#xff0c;再运行C# **ps: 注意修改端口号**python发送Get/Post请求 # -*- coding: utf-8 -*- # Time : 2024/1/25 15:52 # Author : YY # File : post_test.py # Content&#xff1a;提交数据给客户端 from flask import Flask, request, jsonify, redirect…
阅读更多...
Java 学习和实践笔记（30）：继承树的追溯

Java 学习和实践笔记（30）：继承树的追溯

如上图所示&#xff0c;在上图中&#xff0c; 在最下面的子类Husky(哈士奇&#xff09;中&#xff0c;假定要查找一个变量或者方法h, 那么其查找顺序属性/方法查找顺序是这样的&#xff1a; 首先&#xff0c;查找当前类中有没有属性h 如果没有&#xff0c;则依次往上上溯每个…
阅读更多...
Nodejs 18.19.0 基本环境搭建(无版本管理)

Nodejs 18.19.0 基本环境搭建(无版本管理)

简介 记录一次安装Nodejs的过程, 及设置install 安装路径等… 基本安装及设置步骤 1. 下载Nodejs并安装 NodeJs 18.19.0 LTS Windows安装msi, 下载后安装在自己想要的路径, 例如 D:\Softwares\Dev_Tools\nodejs cmd 中输入 nodejs version 可以查看版本 2. 设置 npm config ls…
阅读更多...
Object.defineproperty

Object.defineproperty

Object.defineproperty 的作用就是直接在一个对象上定义一个新属性&#xff0c;或者修改一个已经存在的属性.。并返回此对象。 Object.defineproperty 参数 Object.defineproperty方法需要传递3个参数Object.defineproperty&#xff08;obj, prop, desc &#xff09; 参数1…
阅读更多...
【微信小程序】屏幕适配

【微信小程序】屏幕适配

在网页中一般是使用 rem 单位&#xff0c;它能够根据html的字号大小自动改变尺寸&#xff0c;开发者可以动态的计算屏幕尺寸&#xff0c;然后根据屏幕大小的不同设置html的字号 小程序解决适配使用 rpx 单位&#xff0c;它能够根据屏幕大小自动进行转换。 每一个机型的宽度和高…
阅读更多...
Python实例☞数据类型及运算符案例

Python实例☞数据类型及运算符案例

实例一&#xff1a; ❶要求☞从键盘获取一个4位整数&#xff0c;并分别输出个、十、百、千位 ❷程序代码☞ ①第一种方法 print(请输入一个4位整数&#xff1a;) xeval(input()) print(个位数为&#xff1a;,x%10) print(十位数为&#xff1a;,(x//10)%10) print(百位数为&am…
阅读更多...
第一次捡垃圾

第一次捡垃圾

配置 cpu e3 1225 v6 淘宝 130 显卡 p106-100(1060矿卡的特称) 咸鱼 118 内存 8g 3200频率 2 咸鱼 702140 硬盘 128g 固态 咸鱼 35 主板 ex-b150m-v3 咸鱼 110 电源 400w 咸鱼 58 4热管cpu散热器 咸鱼 28 机箱 迷你 拼多多 28 电源线 1m5 淘宝 8 pcie转m.2 拼多多 9 编程器 用…
阅读更多...
关于Vue3的一些操作

关于Vue3的一些操作

1. 设置浏览器自动打开 在package.json 中设置 dev: vite --open 2.给src文件夹配置别名 在vite.config.ts配置文件中添加以下内容 3. 如果2中有红色波浪线的问题 ***安装一个文件包***npm install types/node3. 在tsconfig.json配置文件中&#xff0c;找到配置项compi…
阅读更多...
凌鲨微应用开发流程

凌鲨微应用开发流程

微应用开发流程 使用vite,nextjs等框架创建前端项目引入需要的api包通过调试界面进行调试 创建前端项目 vite yarn create vitenextjs yarn create next-app引入需要的api包 名称权限说明http跨域访问跨域http访问tauri提供的apilinksaas-minapp/api打开浏览器读本地文件…
阅读更多...
无法更新下载安装升级谷歌浏览器Chrome无法更新至最新版本怎么解决下载更新谷歌浏览器？

无法更新下载安装升级谷歌浏览器Chrome无法更新至最新版本怎么解决下载更新谷歌浏览器？

谷歌Chrome浏览器有新版本chrome可用&#xff0c;点击后无法更新chrome至最新版本&#xff0c;造成每次在电脑上打开谷歌chrome浏览器都会提示更新&#xff0c;重新安装chrome又无法打开谷歌浏览器官方网站。 谷歌浏览器Chrome无法更新至最新版本怎么办&#xff1f; 1、百度搜…
阅读更多...
社区店运营方案分享：从推广到盈利的实战经验

社区店运营方案分享：从推广到盈利的实战经验

对于想要开实体店或创业的朋友们&#xff0c;社区店是一个具有很大发展潜力的选择。 作为一名鲜奶吧5年的创业者&#xff0c;我将分享一些从推广到盈利的实战经验&#xff0c;希望能给大家提供有价值的参考。 1、市场调研&#xff1a; 在开店之前&#xff0c;深入了解社区的…
阅读更多...
挑战杯 基于深度学习的水果识别 设计 开题 技术

挑战杯 基于深度学习的水果识别 设计 开题 技术

1 前言 Hi&#xff0c;大家好&#xff0c;这里是丹成学长&#xff0c;今天做一个 基于深度学习的水果识别demo 这是一个较为新颖的竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f9ff; 更多资料, 项目分享&#xff1a; https://gitee.com/dancheng-senior/pos…
阅读更多...
【自动驾驶系列丛书学习】2.《自动驾驶汽车环境感知》学习笔记

【自动驾驶系列丛书学习】2.《自动驾驶汽车环境感知》学习笔记

《自动驾驶技术概论》学习笔记 致谢&#xff1a;作者&#xff1a;甄先通、黄坚、王亮、夏添 -------------------------------------------------------------------------------------------------------- 笔记目录 -----------------------------------------------------…
阅读更多...
1911_野火FreeRTOS教程阅读笔记_请求任务切换

1911_野火FreeRTOS教程阅读笔记_请求任务切换

1911_野火FreeRTOS教程阅读笔记_请求任务切换 全部学习汇总&#xff1a; g_FreeRTOS: FreeRTOS学习笔记 (gitee.com) 还有一部分任务切换请求的代码没有分析。 实现上是一个宏定义&#xff0c;实现的工作主要的核心点还是请求PendSV的exception。当这个调用的时候&#xff0c;下…
阅读更多...
基于Spring Boot的图书个性化推荐系统 ，计算机毕业设计(带源码+论文)

基于Spring Boot的图书个性化推荐系统 ，计算机毕业设计(带源码+论文)

源码获取地址&#xff1a; 码呢-一个专注于技术分享的博客平台一个专注于技术分享的博客平台,大家以共同学习,乐于分享,拥抱开源的价值观进行学习交流http://www.xmbiao.cn/resource-details/1765769136268455938
阅读更多...
消息队列的原理与基本使用

消息队列的原理与基本使用

文章目录 消息队列定义优点 与 缺点优点缺点常见的消息队列 消息队列的配置消息队列的简单使用生产者消费者运行 消息队列 定义 消息队列&#xff08;message queue&#xff09;是一种用于在软件系统中传输、存储和处理消息的机制。它通常用于异步通信&#xff0c;允许不同的组…
阅读更多...
机器学习：探索计算机的自我进化之路

机器学习：探索计算机的自我进化之路

当我们谈论机器学习时&#xff0c;我们在谈论什么呢&#xff1f;机器学习是一门跨学科的学科&#xff0c;它使用计算机模拟或实现人类学习行为&#xff0c;通过不断地获取新的知识和技能&#xff0c;重新组织已有的知识结构&#xff0c;从而提高自身的性能。简单来说&#xff0…
阅读更多...
导数与微分错题本

导数与微分错题本

《1800》 1 缺乏构造函数的技巧 2 3 等价无穷小构造函数 4 这个构造有点难。补充几个数字构造导数定义 5 6 通过举例子排除真的好 7 8 我不想输 9 注意自变量为x的平方 10 导数对应的x为y的变量 11 代入定义式 12 13 14 15 16 17 18 19 20
阅读更多...
php调用guzzlehttp库时出现Segmentation fault的解决方案

php调用guzzlehttp库时出现Segmentation fault的解决方案

先说结论&#xff0c;这个问题的原因是因为php7.4与openssl3不兼容产生的&#xff0c;解决方案如下&#xff1a; 输入openssl version -a查看openssl版本&#xff0c;如果是3以上的版本与php7.4不兼容&#xff0c;7.4以下的没测试过&#xff0c;估计也有问题。我最终是安装上了…
阅读更多...
日韩媒体宣传案例分析：CloudNEO 为您提供海外媒体宣传最佳途径

日韩媒体宣传案例分析：CloudNEO 为您提供海外媒体宣传最佳途径

近年来&#xff0c;随着互联网的迅速发展和全球化的加速推进&#xff0c;海外市场对于企业的重要性日益凸显。尤其是在亚洲地区&#xff0c;日本和韩国作为亚洲最具活力和潜力的市场之一&#xff0c;成为众多企业争相开拓的目标。在这个过程中&#xff0c;媒体宣传不仅是企业推…
阅读更多...
最新文章

Copyright @ 2022~2023