图论练习1

内容：，拆点，分层，传递，带限制的最小生成树

---

[HNOI2015]菜肴制作

题目链接

题目大意 

• 有个限制，号菜肴在号前完成
• 在满足限制的条件下，按照出菜( 是为了满足的限制 )

解题思路

• 由限制，可以考虑
• 若直接正向，以  为例， 则会先出
• 而反向，
• 此时对于一路限制，最先出的最小的号
• 题目有要求先满足较小号的限制
• 所以将队列改为由大到小排序的堆，再倒序输出每次出堆的号
• 排序的内容实际为正向限制路径上的最终菜肴
• 有环则无解

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;public class Main{static int cnt=0;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].fr=fr;e[cnt].to=to;e[cnt].val=val;e[cnt].nxt=head[fr];head[fr]=cnt;}staticclass Node{int x;long dis;public Node() {}public Node(int I,long D) {x=I;;dis=D;}}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int T=input.nextInt();while(true) {if(T==0) break;int n=input.nextInt();int m=input.nextInt();e=new Edge[m+1];head=new int[n+1];cnt=0;int[] in=new int[n+1];for(int i=1;i<=m;++i) {int u=input.nextInt();int v=input.nextInt();in[u]++;addEdge(v, u, 0);}PriorityQueue<Integer> qu=new PriorityQueue<Integer>((o1,o2)-> {return o2-o1;});boolean[] vis=new boolean[n+1];for(int i=1;i<=n;++i) {if(in[i]==0) {qu.add(i);vis[i]=true;}}int[] op=new int[n+1];int cnt=0;while(!qu.isEmpty()) {int x=qu.peek();qu.poll();cnt++;op[cnt]=x;for(int i=head[x];i>0;i=e[i].nxt) {int v=e[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 i=cnt;i>0;--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 inf=Integer.MAX_VALUE/2;staticclass Edge{int fr,to,nxt;int val;public Edge(int u,int v,int w) {fr=u;to=v;val=w;}}staticclass Node{int x,y;public Node(int X,int Y) {x=X;y=Y;}}static class Map{int[] head;int cnt;Edge[] e;int ans=inf;public Map(int n,int m) {e=new Edge[m];head=new int[n+1];cnt=0;}void addEdge(int fr,int to,int val) {cnt++;e[cnt]=new Edge(fr, to, val);e[cnt].nxt=head[fr];head[fr]=cnt;}void Dij(int s,int n,int[] t) {int[] dis=new int[n+1];boolean[] vis=new boolean[n+1];PriorityQueue<Node> q=new PriorityQueue<Node>((o1,o2)->{return o1.y-o2.y;});for(int i=1;i<=n;++i)dis[i]=inf;dis[s]=0;q.add(new Node(s, 0));while(!q.isEmpty()) {Node now=q.peek();q.poll();int x=now.x;if(vis[x])continue;int disu=now.y;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]>disu+w) {dis[v]=disu+w;q.add(new Node(v,dis[v]));}}}ans=Math.min(ans, Math.min(dis[t[0]], dis[t[1]]));}}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int n=input.nextInt();char[][] map=new char[n+1][n+1];for(int i=1;i<=n;++i) {for(int j=1;j<=n;++j)map[i][j]=input.nextChar();}int N=4*n*n;Map T=new Map(N, 200000);int[] s=new int[2];int[] t=new int[2];for(int i=1;i<=n;++i) {for(int j=1;j<=n;++j) {if(map[i][j]=='x')continue;int num=(i-1)*n+j;int l=(num-1)*4;int u=l+1;int r=l+2;int v=l+3;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(j+1<=n&&map[i][j+1]!='x') {int nxtl=num*4;T.addEdge(r, nxtl, 0);T.addEdge(nxtl, r, 0);}if(j>=2&&map[i][j-1]!='x') {int nxtr=(num-2)*4+2;T.addEdge(nxtr, l, 0);T.addEdge(l, nxtr, 0);}if(i>=2&&map[i-1][j]!='x') {int nxtv=((i-2)*n+j-1)*4+3;T.addEdge(u, nxtv, 0);T.addEdge(nxtv, u, 0);}if(i+1<=n&&map[i+1][j]!='x') {int nxtu=(i*n+j-1)*4+1;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.ans==inf)out.print("-1");else out.print(T.ans);out.flush();out.close();}staticclass 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();}}
}

---

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 input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int n=input.nextInt();int m=input.nextInt();BitSet[] a=new BitSet[n+1];for(int i=0;i<n;++i)a[i]=new BitSet(n);for(int i=1;i<=m;++i) {int x=input.nextInt()-1;int y=input.nextInt()-1;a[x].set(y);//对应位置赋为true}for(int k=0;k<n;++k) {for(int i=0;i<n;++i) {if(a[i].get(k)) {a[i].or(a[k]);//或运算}}}int ans=0;for(int i=0;i<n;++i) {for(int j=i+1;j<n;++j) {if(a[i].get(j)==false&&a[j].get(i)==false) {ans++;//因为不知道是i>j还是i<j，无法传递}}}out.print(ans);out.flush();out.close();}staticclass 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();}}
}

---

[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 cnt=0;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].fr=fr;e[cnt].to=to;e[cnt].val=val;e[cnt].nxt=head[fr];head[fr]=cnt;}staticclass Node{int x;int h;long dis;public Node(){}public Node(int X,long D,int H){x=X;h=H;dis=D;}}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();int[] H=new int[n+1];e=new Edge[m<<1|1];head=new int[n+1];for(int i=1;i<=n;++i) {H[i]=input.nextInt();}for(int i=1;i<=m;++i) {int u=input.nextInt();int v=input.nextInt();long val=input.nextLong();if(H[u]>=H[v])addEdge(u, v, val);if(H[v]>=H[u])addEdge(v, u, val);}boolean[] vis=new boolean[n+1];PriorityQueue<Node> qu=new PriorityQueue<Node>((o1,o2)->{if(o1.h==o2.h){if(o1.dis-o2.dis>0)return 1;else if(o1.dis-o2.dis<0)return -1;else return 0;}else return o2.h-o1.h;});int num=0;long ans=0;qu.add(new Node(1,0,H[1]));while(!qu.isEmpty()) {Node now=qu.peek();qu.poll();int x=now.x;if(vis[x])continue;vis[x]=true;ans+=now.dis;num++;for(int i=head[x];i>0;i=e[i].nxt) {int v=e[i].to;long w=e[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());}}
}

---