Java實作藍橋杯 算法訓練 Professor Monotonic's Network

試題 算法訓練 Professor Monotonic’s Network

資源限制

時間限制：1.0s 記憶體限制：256.0MB

問題描述

　　無聊的教授最近在做一項關于比較網絡的實驗。一個比較網絡由若幹個含兩個輸入端和兩個輸出端的比較器組成。如下圖，一個比較器将會比較它的兩個輸入端的值i1和i2，把它們防止在輸出端o1和o2上使得o1<=o2。

一個比較網絡有n個輸入端a1,a2,…,an和n個輸出端b1,b2,…,bn。對于每個比較器，它的輸入端要麼直接連在比較網絡的輸入端上，要麼連在另一個個比較器的輸出端上。這樣的關系組成的有向圖是無環的。下圖給出了一個擁有4個輸入端、4個輸出端、5個比較器的比較網絡。

　　在比較網絡運作時，值從輸入端輸入，然後比較器開始工作。當然，一個比較器僅當它的所有輸入值已經被算出來後才能開始工作。假設一個比較器需要1機關時間來工作。那麼，上面的例子中的比較網絡需要3機關時間來計算輸出值。圖中的comp-1和comp-2是并行工作的，comp-3和comp-4也是，comp-5隻有等comp-3和comp-4完成後才能工作。

　　無聊的教授現在需要幫助确定那些比較網絡是排序網絡，并且它們需要多長時間來計算輸出值。一個排序網絡是一個比較網絡，并且無論輸入如何，它的輸出都單調增。上面的例子也是一個比較網絡。因為對于每一種可能的輸入，輸出值都存在關系b1<=b2<=b3<=b4。

輸入格式

　　第一行兩個整數n,k，分别表示輸入值的個數和比較器的個數。

　　它們滿足1<=n<=12，0<=k<=150。

　　之後從左到右依次給出每個比較器的資訊

　　之後每行兩個整數x,y表示第i個比較器将ax,ay做了比較，把其中較小的數放回ax,較大的數放回ay。

輸出格式

　　第一行輸出YES或NO表示該比較網絡是否是排序網絡

　　第二行輸出一個整數表示該比較網絡的運作時間。

樣例輸入

樣例1：

4 5

1 2

3 4

1 3

2 4

2 3

樣例2：

8 0

樣例3：

3 3

1 2

2 3

1 2

樣例輸出

樣例1：

YES

3

樣例2：

NO

樣例3：

YES

3

樣例說明

　　樣例1即圖檔上所給的比較網絡。

package 第九次模拟;

import java.util.Scanner;

public class 排序 {
	public static class Node{
		int first;
		int second;
	}
	static 	int n=0,m=0,x=0,y=0;
	static 	int N=15;
	static int []a = new int [N];
	static 	int [] num = new int [N];
	  	static 	int res=0;
	static int cnt=0;
	static 	Node [] T = new Node[155];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		while(m-->0){
			  x= sc.nextInt();
			  y = sc.nextInt();
			T[++cnt]=new Node();
			T[cnt].first=x;
			T[cnt].second=y;
			int t =Math.max(num[x], num[y])+1;
			num[x]=t;
			num[y]=t;
			res=Math.max(res, t);
		}
		sc.close();
		boolean yes=true;
		for(int i=0;i<(1<<n);i++){
			for(int j=0;j<n;j++){
				a[j+1]=(i>>j&1);
			}
			for(int j=1;j<=cnt;j++){
				x=T[j].first;
				y=T[j].second;
				int tt=Math.min(a[x],a[y]);
				a[y]=Math.max(a[x],a[y]);
				a[x]=tt;
			}
			for(int j=1;j<n;j++)
				if(a[j]==1&&a[j+1]==0){
					yes=false;break;
				}
			if(!yes)
				break;
		}
		if(yes)
			System.out.println("YES");
		else
			System.out.println("NO");
			
		System.out.println(res);
	}

}

           

package 第九次模拟;

import java.util.Scanner;

public class 排序 {
	//轉自https://blog.csdn.net/a1439775520/article/details/104653580
	public static class Node{
		int first;
		int second;
	}
	 
	public static void main(String[] args) {
	 	 int n=0,m=0,x=0,y=0;
	     int N=15;
	    
	     int [] num = new int [N];
	  	 int res=0;
	     int cnt=0;
	     int t=0;
	     Node [] T = new Node[155];
	     Scanner sc = new Scanner(System.in);
		  n = sc.nextInt();
		  m = sc.nextInt();
		
		while(m-->0){
			  x= sc.nextInt();
			  y = sc.nextInt();
			  T[++cnt]=new Node();
			  T[cnt].first=x;
			  T[cnt].second=y;
			   t = Math.max(num[x], num[y])+1;
			  num[x]=t;
			  num[y]=t;
			  res= Math.max(res, t);
		}
		sc.close();
		 int []a = new int [N];
	     int tt=0;
//		boolean yes=true;
		for(int i=0;i<(1<<n);i++){
			for(int j=0;j<n;j++){
				a[j+1]=(i>>j&1);
			}
			for(int j=1;j<=cnt;j++){
				x=T[j].first;
				y=T[j].second;
				  tt= Math.min(a[x],a[y]);
				a[y]= Math.max(a[x],a[y]);
				a[x]=tt;
			}
			for(int j=1;j<n;j++)
				if(a[j]==1&&a[j+1]==0){
					System.out.println("NO");
					System.out.println(res);return;
				}
//			if(!yes)
//				break;
		}
//		if(yes)
			System.out.println("YES");
//		else
//			System.out.println("NO");
			
		System.out.println(res);
	}
//	public static int min(int a,int b){
//		return a<b?a:b;
//	}
//	public static int max(int a,int b){
//		return a<b?b:a;
//	}

}