保研機試験準備の常用機試験コード
31897 ワード
Java快速IO
コレクションを調べる
トポロジのソート
最小生成ツリーのKruskalアルゴリズム
最短パスのDijkstraアルゴリズム
最短パスのFloydアルゴリズム
前シーケンスと中シーケンスからツリーを構築
1)シーケンスを文字列で表す
2)シーケンスを整数配列で表す
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int n = nextInt();
int m = nextInt();
out.flush();
out.close();
public static int nextInt() throws IOException {
sc.nextToken();
return (int) sc.nval;
}コレクションを調べる
/**
* Union Find Set
* @author andong
*
*/
import java.util.Arrays;
public class UFS {
final int MAX = 20;
int[] par;
int[] rank;
public UFS(){
par = new int[MAX];
rank = new int[MAX];
for(int i=0;i<MAX;i++){
par[i] = i;
}
Arrays.fill(rank, 1);
}
public int find(int x){
int px = x;
while(px!=par[px]){
px = par[px];
}
int t;
while(x!=px){
t = par[x];
par[x] = px;
x = t;
}
return px;
}
public void union(int x,int y){
int px = find(x);
int py = find(y);
if(px != py){
if(rank[px]>=rank[py]){
par[py] = px;
rank[px]+=rank[py];
}
else{
par[px] = py;
rank[py]+=rank[px];
}
}
}
public int count(){
int cnt = 0;
for(int i=0;i<MAX;i++){
if(par[i]==i)
cnt++;
}
return cnt;
}
}トポロジのソート
public class Topo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] g = new int[n+1][n+1];
int m = sc.nextInt();
for(int i=0;i<m;i++){
int a = sc.nextInt();
int b = sc.nextInt();
g[a][b] = 1;
}
int[] cnt = new int[n+1];
boolean[] in = new boolean[n+1];
Arrays.fill(in, false);
Arrays.fill(cnt, 0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(g[i][j]==1)
cnt[j]++;
}
}
Queue<Integer> q = new LinkedList<Integer>();
for(int i=1;i<=n;i++){
if(cnt[i]==0){
q.add(i);
in[i] = true;
}
}
while(!q.isEmpty()){
int p = q.remove();
for(int i=1;i<=n;i++){
if(g[p][i]==1){
cnt[i]--;
if(cnt[i]==0&&!in[i]){
q.add(i);
in[i] = true;
}
}
}
System.out.print(p);
}
}
}最小生成ツリーのKruskalアルゴリズム
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* Kruskal
* @author andong
*
*/
public class Kruskal {
public static final int INF = Integer.MAX_VALUE;
public static int nV;
public static int[][] graph;
public static UFS ufs;
public static PriorityQueue<Edge> priq;
public static ArrayList<Edge> list;
public static void init(int[][] g){
nV = g.length;
graph = g;
ufs = new UFS(nV);
Comparator<Edge> com = new Comparator<Kruskal.Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return o1.w<o2.w?-1:1;
}
};
priq = new PriorityQueue<Edge>(nV,com);
list = new ArrayList<Edge>();
//i->j
for(int i=0;i<nV;i++){
for(int j=0;j<nV;j++){
if(graph[i][j]>0&&graph[i][j]<INF){
priq.add(new Edge(i, j,graph[i][j]));
}
}
}
work();
}
public static void work(){
int cnt = 0;
while(!priq.isEmpty()){
Edge edge = priq.remove();
if(ufs.find(edge.s)!=ufs.find(edge.e)){
ufs.union(edge.s, edge.e);
list.add(edge);
cnt++;
}
if(cnt==nV-1){
output();
break;
}
}
}
public static void output(){
for(int i=0;i<list.size();i++){
System.out.println(list.get(i).w);
}
}
static class Edge {
int s,e,w;
public Edge(int s,int e,int w){
this.s = s;
this.e = e;
this.w = w;
}
}
public static void main(String[] args) {
int[][] a = {{0,1,2,4},{0,0,2,5},{0,0,0,3},{0,0,0,0}};
Kruskal.init(a);
}
}最短パスのDijkstraアルゴリズム
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* Dijkstra
* @author andong
*
*/
public class Dijkstra {
public static int nV;
public static int src;
public static int[][] graph;
public static int[] dist;
public static ArrayList<Integer> list;
public static PriorityQueue<point> priq;
public static void init(int[][] g,int s){
nV = g.length;
src = s;
graph = g;
dist = new int[nV];
list = new ArrayList<Integer>();
Comparator<point> com = new Comparator<point>() {
public int compare(point o1, point o2) {
return o1.dist<o2.dist?-1:1;
}
};
priq = new PriorityQueue<point>(nV,com);
for(int i=0;i<nV;i++){
dist[i] = graph[src][i];
if(i!=src) priq.add(new point(i, dist[i]));
}
}
public static void work(){
while(!priq.isEmpty()){
point p = priq.remove();
for(int i=0;i<nV;i++){
int tmp = dist[p.pos]+graph[p.pos][i];
if(tmp<dist[i]){
dist[i] = tmp;
priq.add(new point(i, dist[i]));
}
}
list.add(p.pos);
}
}
public static void output(int dest){
System.out.println(dist[dest]);
for(int i=0;i<list.size();i++){
System.out.print(list.get(i));
if(list.get(i)==dest){
System.out.println();
break;
}
}
}
static class point{
int pos,dist;
public point(int pos,int dist){
this.pos = pos;
this.dist = dist;
}
}
public static void main(String[] args) {
int[][] a = {{0,1,2,4},{0,0,2,5},{0,0,0,3},{0,0,0,0}};
Dijkstra.init(a, 0);
for(int i=0;i<4;i++){
Dijkstra.output(i);
}
}
}最短パスのFloydアルゴリズム
import java.util.Arrays;
/**
* Floyd
* @author andong
*
*/
public class Floyd {
public static int nV;
public static int[][] dist;
public static int[][] inter;
public static void init(int[][] g){
nV = g.length;
dist = new int[nV][nV];
for(int i=0;i<nV;i++)
for(int j=0;j<nV;j++){
if(g[i][j]<Integer.MAX_VALUE)
dist[i][j] = g[i][j];
else
dist[i][j] = -1;
}
inter = new int[nV][nV];
for(int i=0;i<nV;i++){
for(int j=0;j<nV;j++){
inter[i][j] = j;
}
}
work();
}
public static void work(){
for(int k=0;k<nV;k++){
for(int i=0;i<nV;i++){
for(int j=0;j<nV;j++){
if(dist[i][k]>0&&dist[k][j]>0&&dist[i][j]>dist[i][k]+dist[k][j]){
dist[i][j] = dist[i][k]+dist[k][j];
inter[i][j] = k;
}
}
}
}
}
public static void outputDist(int src,int dest){
System.out.println(dist[src][dest]);
}
public static void outputPath(int src,int dest){
if(src==dest){
System.out.print(src);
return;
}
System.out.print(src);
outputPath(inter[src][dest], dest);
}
public static void main(String[] args) {
int INF = Integer.MAX_VALUE;
int[][] a = {{0,1,2,4},{INF,0,2,7},{INF,INF,0,3},{INF,INF,INF,0}};
Floyd.init(a);
for(int i=0;i<4;i++)
outputDist(1, i);
outputPath(1, 3);
}
}前シーケンスと中シーケンスからツリーを構築
1)シーケンスを文字列で表す
public static void build(String a,String b){
int len = a.length();
if(len==1){
System.out.println(a);
}
else if(len>1){
char c = a.charAt(0);
String[] temp = b.split(c+"");
int len0 = temp[0].length();
int len1 = temp[1].length();
build(a.substring(1, 1+len0),temp[0]);
build(a.substring(len-len1),temp[1]);
System.out.print(c);
}
}2)シーケンスを整数配列で表す
public static void build(int pos, int[] pre, int[] in) {
if (pre.length <= 0)
return;
tree[pos] = pre[0];
int idx = 0;
for (idx = 0; idx < pre.length; idx++) {
if (in[idx] == pre[0])
break;
}
if (idx > 0 && pos * 2 < tree.length) {
int[] leftpre = new int[idx];
int[] leftin = new int[idx];
System.arraycopy(pre, 1, leftpre, 0, idx);
System.arraycopy(in, 0, leftin, 0, idx);
build(pos * 2, leftpre, leftin);
}
if (idx < pre.length - 1 && pos * 2 + 1 < tree.length - 1) {
int[] rightpre = new int[pre.length - idx - 1];
int[] rightin = new int[in.length - idx - 1];
System.arraycopy(pre, 1 + idx, rightpre, 0, pre.length - 1 - idx);
System.arraycopy(in, 1 + idx, rightin, 0, in.length - 1 - idx);
build(pos * 2 + 1, rightpre, rightin);
}
}