首页 > 专题系列 > Java解POJ > POJ 1422 Air Raid [解题报告] Java
2013
11-09

POJ 1422 Air Raid [解题报告] Java

Air Raid

问题描述 :

Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town’s streets you can never reach the same intersection i.e. the town’s streets form no cycles.

With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper.

输入:

Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:

no_of_intersections

no_of_streets

S1 E1

S2 E2

……

Sno_of_streets Eno_of_streets

The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town’s streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections.

There are no blank lines between consecutive sets of data. Input data are correct.

输出:

The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town.

样例输入:

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

样例输出:

2
1

解题代码:

//* @author: 
import java.io.*;
import java.util.*;
import java.math.*;
public class Main 
{
    static int n,m,match[]=new int[201];
    static boolean mat[][]=new boolean[201][201],v[]=new boolean[201];
    static boolean findmatch(int pre)
    {
        int i;
        for(i=0;i< m;i++)
        {
            if(mat[pre][i]&&!v[i])
            {
                v[i]=true;
                int buf=match[i];
                match[i]=pre;
                if(buf==-1||findmatch(buf))return true;
                match[i]=buf;
            }
        }
        return false;
    }
    static int bmatch()
    {
        int ret=0,i;
        for(i=0;i< n;i++)
        {
            Arrays.fill(v, false);
            if(findmatch(i))ret++;
        }
        return ret;
    }
    public static void main(String args[]) throws Exception {
        Scanner cin=new Scanner(System.in);
        int t=cin.nextInt(),k,a,b;
        while(t-->0)
        {
            m=n=cin.nextInt();
            int i,j;
            for(i=0;i< n;i++) for(j=0;j< n;j++)mat[i][j]=false;
            k=cin.nextInt();
            while(k-->0)
            {
                a=cin.nextInt();
                b=cin.nextInt();
                a--;
                b--;
                mat[a][b]=true;
            }
            Arrays.fill(match, -1);
            System.out.println(n-bmatch());
        }
    }
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。