首页 > ACM题库 > HDU-杭电 > HDU 3385-Mining Maps[解题报告]HOJ
2014
03-23

HDU 3385-Mining Maps[解题报告]HOJ

Mining Maps

问题描述 :

Administrator Selfridge is analyzing possible mining routes on Pandora. He has collected some data in the form of a graph. Your goal is to help him collect some information about each graph.

输入:

Connections between mines are described beginning with the line ”GRAPH BEGIN”. Additional lines lists individual mines (nodes), followed (on the same line) by their neighboring mines (edges). The line ”GRAPH END” ends the list of path descriptions. The entire problem may be repeated as desired, starting from scratch each time. Some mines may appear only as neighboring
mines, without being described on a separate line.

输出:

Connections between mines are described beginning with the line ”GRAPH BEGIN”. Additional lines lists individual mines (nodes), followed (on the same line) by their neighboring mines (edges). The line ”GRAPH END” ends the list of path descriptions. The entire problem may be repeated as desired, starting from scratch each time. Some mines may appear only as neighboring
mines, without being described on a separate line.

样例输入:

GRAPH BEGIN
a b
b c
GRAPH END
GRAPH BEGIN
a b c
b c d
d e f
e f
GRAPH END

样例输出:

NODES 3 EDGES 2
NODES 6 EDGES 7


Problem Description
Administrator Selfridge is analyzing possible mining routes on Pandora. He has collected some data in the form of a graph. Your goal is to help him collect some information about each graph.

Input
Connections between mines are described beginning with the line ”GRAPH BEGIN”. Additional lines lists individual mines (nodes), followed (on the same line) by their neighboring mines (edges). The line ”GRAPH END” ends the list of path descriptions. The entire problem may be repeated as desired, starting from scratch each time. Some mines may appear only as neighboring
mines, without being described on a separate line.

Output
Your output should consist one line (for each graph analyzed), consisting of ”NODES” followed by the number of nodes, followed by ”EDGES” and the number of edges in the graph.
Mining Maps

Sample Input
GRAPH BEGIN a b b c GRAPH END GRAPH BEGIN a b c b c d d e f e f GRAPH END

Sample Output
NODES 3 EDGES 2 NODES 6 EDGES 7

Source
 
比较简单的一题,我的方法:用邻接矩阵
 
import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
 
 public static void main(String[] args) {
  Scanner cin = new Scanner(System.in);
  String str;
  int map[][] = new int[105][105];
  
  while(cin.hasNext()){
   
   str = cin.nextLine();
   int count,max;
   
   
   if(str.equals(“GRAPH BEGIN”)){
    for(int i = 0; i < 105; i++)
     for(int j = 0; j < 105; j++)
      map[i][j] = 0;
    count = max = 0;
    String s = cin.nextLine();
  
    while(!s.equals(“GRAPH END”)){
     if(s.charAt(0)-’a’ > max) max = s.charAt(0)-’a';   
     for(int i = 1; i < s.length(); i++)      
      if(s.charAt(i) >= ‘a’ && s.charAt(i) <= ‘z’)   
      {           
       if(max < s.charAt(i)-’a') max=s.charAt(i)-’a';  
       map[s.charAt(i)-'a'][s.charAt(0)-'a']=map[s.charAt(0)-'a'][s.charAt(i)-'a']=1;  
      }       
     
     s = cin.nextLine();
    }
    for(int i = 0; i <= max; i++)     
     for(int j = 0; j <= max; j++)     
      if(map[i][j] == 1)              
       count++;  
    
    System.out.print(“NODES “+(max+1)+” “);
    System.out.println(“EDGES “+count/2);
    
   }
   
  }
 }
}
参考:http://skogt123.blog.163.com/blog/static/138551746201183001815873/


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  3. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。