公司网站建设企业网站,深圳做网站排名哪家专业,wordpress转移过电脑,建设部网站一级开发资质内容#xff1a;#xff0c;拆点#xff0c;分层#xff0c;传递#xff0c;带限制的最小生成树 [HNOI2015]菜肴制作
题目链接
题目大意
有个限制#xff0c;号菜肴在号前完成在满足限制的条件下#xff0c;按照出菜( 是为了满足的限制 )
解题思路
由限制#xf…内容拆点分层传递带限制的最小生成树 [HNOI2015]菜肴制作
题目链接
题目大意
有个限制号菜肴在号前完成在满足限制的条件下按照出菜( 是为了满足的限制 )
解题思路
由限制可以考虑若直接正向以 为例 则会先出而反向此时对于一路限制最先出的最小的号题目有要求先满足较小号的限制所以将队列改为由大到小排序的堆再倒序输出每次出堆的号排序的内容实际为正向限制路径上的最终菜肴有环则无解 import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;public class Main{static int cnt0;static Edge[] e;static int[] head;staticclass Edge{long val;int to;int fr;int nxt;}static void addEdge(int fr,int to,long val) {cnt;e[cnt]new Edge();e[cnt].frfr;e[cnt].toto;e[cnt].valval;e[cnt].nxthead[fr];head[fr]cnt;}staticclass Node{int x;long dis;public Node() {}public Node(int I,long D) {xI;;disD;}}public static void main(String[] args) throws IOException{AReader inputnew AReader();PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));int Tinput.nextInt();while(true) {if(T0) break;int ninput.nextInt();int minput.nextInt();enew Edge[m1];headnew int[n1];cnt0;int[] innew int[n1];for(int i1;im;i) {int uinput.nextInt();int vinput.nextInt();in[u];addEdge(v, u, 0);}PriorityQueueInteger qunew PriorityQueueInteger((o1,o2)- {return o2-o1;});boolean[] visnew boolean[n1];for(int i1;in;i) {if(in[i]0) {qu.add(i);vis[i]true;}}int[] opnew int[n1];int cnt0;while(!qu.isEmpty()) {int xqu.peek();qu.poll();cnt;op[cnt]x;for(int ihead[x];i0;ie[i].nxt) {int ve[i].to;if(vis[v])continue;in[v]--;if(in[v]0) {qu.add(v);vis[v]true;}}}if(cnt!n) {out.println(Impossible!);}else {for(int icnt;i0;--i) {out.print(op[i] );}out.println();}T--;}out.flush();out.close();}staticclass AReader {private BufferedReader reader new BufferedReader(new InputStreamReader(System.in));private StringTokenizer tokenizer new StringTokenizer();private String innerNextLine() {try {return reader.readLine();} catch (IOException ex) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String nextLine innerNextLine();if (nextLine null) {return false;}tokenizer new StringTokenizer(nextLine);}return true;}public String nextLine() {tokenizer new StringTokenizer();return innerNextLine();}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}}
} 胖胖的牛牛
题目链接
题目大意
在图上从到不可经过有水平和垂直两个方向在且方向为垂直往左或右走需要转变方向求最少的转变方向次数
解题思路
将看作两步先判断转向再移动所以将一个点拆为上下左右4个求拆点后的最短路 import java.io.*;
import java.io.ObjectInputStream.GetField;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{static int infInteger.MAX_VALUE/2;staticclass Edge{int fr,to,nxt;int val;public Edge(int u,int v,int w) {fru;tov;valw;}}staticclass Node{int x,y;public Node(int X,int Y) {xX;yY;}}static class Map{int[] head;int cnt;Edge[] e;int ansinf;public Map(int n,int m) {enew Edge[m];headnew int[n1];cnt0;}void addEdge(int fr,int to,int val) {cnt;e[cnt]new Edge(fr, to, val);e[cnt].nxthead[fr];head[fr]cnt;}void Dij(int s,int n,int[] t) {int[] disnew int[n1];boolean[] visnew boolean[n1];PriorityQueueNode qnew PriorityQueueNode((o1,o2)-{return o1.y-o2.y;});for(int i1;in;i)dis[i]inf;dis[s]0;q.add(new Node(s, 0));while(!q.isEmpty()) {Node nowq.peek();q.poll();int xnow.x;if(vis[x])continue;int disunow.y;for(int ihead[x];i0;ie[i].nxt) {int ve[i].to;int we[i].val;if(vis[v])continue;if(dis[v]disuw) {dis[v]disuw;q.add(new Node(v,dis[v]));}}}ansMath.min(ans, Math.min(dis[t[0]], dis[t[1]]));}}public static void main(String[] args) throws IOException{AReader inputnew AReader();PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));int ninput.nextInt();char[][] mapnew char[n1][n1];for(int i1;in;i) {for(int j1;jn;j)map[i][j]input.nextChar();}int N4*n*n;Map Tnew Map(N, 200000);int[] snew int[2];int[] tnew int[2];for(int i1;in;i) {for(int j1;jn;j) {if(map[i][j]x)continue;int num(i-1)*nj;int l(num-1)*4;int ul1;int rl2;int vl3;T.addEdge(l, u, 1);T.addEdge(u, l, 1);T.addEdge(u, r, 1);T.addEdge(r, u, 1);T.addEdge(r, v, 1);T.addEdge(v, r, 1);T.addEdge(v, l, 1);T.addEdge(l, v, 1);T.addEdge(l, r, 0);T.addEdge(r, l, 0);T.addEdge(u, v, 0);T.addEdge(v, u, 0);if(j1nmap[i][j1]!x) {int nxtlnum*4;T.addEdge(r, nxtl, 0);T.addEdge(nxtl, r, 0);}if(j2map[i][j-1]!x) {int nxtr(num-2)*42;T.addEdge(nxtr, l, 0);T.addEdge(l, nxtr, 0);}if(i2map[i-1][j]!x) {int nxtv((i-2)*nj-1)*43;T.addEdge(u, nxtv, 0);T.addEdge(nxtv, u, 0);}if(i1nmap[i1][j]!x) {int nxtu(i*nj-1)*41;T.addEdge(nxtu, v, 0);T.addEdge(v, nxtu, 0); } if(map[i][j]A) {s[0]l;s[1]u;}else if(map[i][j]B) {t[0]l;t[1]u;}}}T.Dij(s[0], N, t);T.Dij(s[1], N, t);if(T.ansinf)out.print(-1);else out.print(T.ans);out.flush();out.close();}staticclass AReader{BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bfnew BufferedReader(new InputStreamReader(System.in));stnew StringTokenizer();bwnew BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){stnew 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();}}
} UVALive7250 Meeting
题目大意
个点个集合集合内的点有权为的边从出发从出发走单位距离花费时间问相遇与一点的最少时间
解题思路
若点集合任意两点之间连边共连当很大存不下考虑将集合看作一点则集合内两点连边变为 连边降为可以存下 在个点上的任意一点相遇以和为出发点跑最短路再枚举点求 [USACO 2007 Mar G] Ranking the cows
题目链接 题目大意
有 个数字已经比较了对问至少还需要多少对比较可以将个数由大到小排列
解题思路
对于若已知则类似枚举中间点定义表示可以省去枚举 表示与其他点的状态用若则不知道大小关系需要比较此时不知道比较后的结果无法传递要满足至少都得比较 import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{public static void main(String[] args) throws IOException{AReader inputnew AReader();PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));int ninput.nextInt();int minput.nextInt();BitSet[] anew BitSet[n1];for(int i0;in;i)a[i]new BitSet(n);for(int i1;im;i) {int xinput.nextInt()-1;int yinput.nextInt()-1;a[x].set(y);//对应位置赋为true}for(int k0;kn;k) {for(int i0;in;i) {if(a[i].get(k)) {a[i].or(a[k]);//或运算}}}int ans0;for(int i0;in;i) {for(int ji1;jn;j) {if(a[i].get(j)falsea[j].get(i)false) {ans;//因为不知道是ij还是ij无法传递}}}out.print(ans);out.flush();out.close();}staticclass AReader{BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bfnew BufferedReader(new InputStreamReader(System.in));stnew StringTokenizer();bwnew BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){stnew 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();}}
} [SCOI2012]滑雪与时间胶囊
题目链接
题目大意
条边每个边的端点为景点共个 每个点有高度能到满足有边权为从从号景点出发走最短路访问尽量多的节点同时可以回到经过的任意一个节点再次出发问最多能访问多少个节点和此时走过的最小路径长度
解题思路
由于可以任意回溯所以可以访问到号节点能到的任意一个节点 设号节点能到的点数为则最终边有条考虑生成最小树由于边有高度通行限制所以要访问尽可能多的点高度高的点先出其次再比较边权每出一个点进行答案更新
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;public class Main{static int cnt0;static Edge[] e;static int[] head;staticclass Edge{long val;int to;int fr;int nxt;}static void addEdge(int fr,int to,long val) {cnt;e[cnt]new Edge();e[cnt].frfr;e[cnt].toto;e[cnt].valval;e[cnt].nxthead[fr];head[fr]cnt;}staticclass Node{int x;int h;long dis;public Node(){}public Node(int X,long D,int H){xX;hH;disD;}}public static void main(String[] args) throws IOException{AReader inputnew AReader();PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));int ninput.nextInt();int minput.nextInt();int[] Hnew int[n1];enew Edge[m1|1];headnew int[n1];for(int i1;in;i) {H[i]input.nextInt();}for(int i1;im;i) {int uinput.nextInt();int vinput.nextInt();long valinput.nextLong();if(H[u]H[v])addEdge(u, v, val);if(H[v]H[u])addEdge(v, u, val);}boolean[] visnew boolean[n1];PriorityQueueNode qunew PriorityQueueNode((o1,o2)-{if(o1.ho2.h){if(o1.dis-o2.dis0)return 1;else if(o1.dis-o2.dis0)return -1;else return 0;}else return o2.h-o1.h;});int num0;long ans0;qu.add(new Node(1,0,H[1]));while(!qu.isEmpty()) {Node nowqu.peek();qu.poll();int xnow.x;if(vis[x])continue;vis[x]true;ansnow.dis;num;for(int ihead[x];i0;ie[i].nxt) {int ve[i].to;long we[i].val;if(vis[v])continue;qu.add(new Node(v,w,H[v]));}}out.println(num ans);out.flush();out.close();}staticclass AReader {private BufferedReader reader new BufferedReader(new InputStreamReader(System.in));private StringTokenizer tokenizer new StringTokenizer();private String innerNextLine() {try {return reader.readLine();} catch (IOException ex) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String nextLine innerNextLine();if (nextLine null) {return false;}tokenizer new StringTokenizer(nextLine);}return true;}public String nextLine() {tokenizer new StringTokenizer();return innerNextLine();}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}}
}
