HDU 4160 Dolls （最小路径覆盖=顶点数-最大匹配数）

Dolls

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 869 Accepted Submission(s): 403

Problem DescriptionInputOutputSample InputSample Outputimport java.io.*;import java.util.*;public class Main {int n,MAX=10010;int[][] map;int[] link=new int[MAX];boolean[] mark=new boolean[MAX];public static void main(String[] args) {new Main().work();}void work(){Scanner sc=new Scanner(new BufferedInputStream(System.in));while(sc.hasNext()){n=sc.nextInt();if(n==0) break;Node node[]=new Node[n];for(int i=0;i<n;i++){int wi=sc.nextInt();int li=sc.nextInt();int hi=sc.nextInt();node[i]=new Node(wi,li,hi);}Arrays.sort(node);map=new int[500][508];for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(node[i].wi<node[j].wi&&node[i].li<node[j].li&&node[i].hi<node[j].hi){map[i][j]=1;}}}hungary();}}void hungary(){int ans=0;Arrays.fill(link, 0);for(int i=0;i<n;i++){Arrays.fill(mark, false);if(DFS(i))ans++;}System.out.println(n-ans);}boolean DFS(int x){for(int i=0;i<n;i++){if(map[x][i]==1&&!mark[i]){mark[i]=true;if(link[i]==0||DFS(link[i])){link[i]=x;return true;}}}return false;}class Node implements Comparable<Node>{int wi;int li;int hi;Node(int wi,int li,int hi){this.wi=wi;this.li=li;this.hi=hi;}public int compareTo(Node o) {if(this.wi>o.wi) return 1;if((this.wi==o.wi)&&(this.li>o.li)) return 1;if((this.wi==o.wi)&&(this.li==o.li)&&(this.hi>o.hi))return 1;return -1;}}}