首页 > 专题系列 > Java解POJ > POJ 1274 The Perfect Stall [解题报告] Java
2013
11-09

POJ 1274 The Perfect Stall [解题报告] Java

The Perfect Stall

问题描述 :

Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John randomly assigned cows to stalls, but it quickly became clear that any given cow was only willing to produce milk in certain stalls. For the last week, Farmer John has been collecting data on which cows are willing to produce milk in which stalls. A stall may be only assigned to one cow, and, of course, a cow may be only assigned to one stall.

Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.

输入:

The input includes several cases. For each case, the first line contains two integers, N (0 <= N <= 200) and M (0 <= M <= 200). N is the number of cows that Farmer John has and M is the number of stalls in the new barn. Each of the following N lines corresponds to a single cow. The first integer (Si) on the line is the number of stalls that the cow is willing to produce milk in (0 <= Si <= M). The subsequent Si integers on that line are the stalls in which that cow is willing to produce milk. The stall numbers will be integers in the range (1..M), and no stall will be listed twice for a given cow.

输出:

For each case, output a single line with a single integer, the maximum number of milk-producing stall assignments that can be made.

样例输入:

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

样例输出:

4

解题代码:

/* @author: [email protected]/
import java.io.*;
import java.util.*;
public class Main
{
   static int m,n;
   static boolean[] flag;
   static int[] occ;
   static int[][] adj;
   public static void main(String args[]) throws Exception
   {
     Scanner cin=new Scanner(System.in);
     while(cin.hasNext())
     {
      	n=cin.nextInt();
      	m=cin.nextInt();
      	adj=new int[n+1][m+1];
       for(int i=0;i< n;i++)
       {
          int a=cin.nextInt();
          while(a--!=0)
           {
             	adj[i+1][cin.nextInt()]=1;
            }
       }
       int count=0;
     	occ=new int[m+1];
      	for(int i=1;i<=n;i++)
      	{
        flag=new boolean[m+1];
        if(find(i))
        {
         count++;
        }
                    		
       }
       System.out.println(count);
    }
  }
            
  public static boolean find(int i)
  {
   for(int j=1;j<=m;j++)
    {
      if(!flag[j]&&adj[i][j]==1)
      {
        flag[j]=true;
        if(occ[j]==0||find(occ[j]))
        {
         occ[j]=i;
         return true;
        }
       }
    }
    return false;
  }
}

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

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  4. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish