HDU 3829 Cat VS Dog ( 最大獨立集 = 頂點數 - 最大匹配數)

Cat VS Dog Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 125536/65536 K (Java/Others) Total Submission(s): 2148    Accepted Submission(s): 748     Problem Description The zoo have N cats and M dogs, today there are P children visiting the zoo, each child has a like-animal and a dislike-animal, if the child's like-animal is a cat, then his/hers dislike-animal must be a dog, and vice versa. Now the zoo administrator is removing some animals, if one child's like-animal is not removed and his/hers dislike-animal is removed, he/she will be happy. So the administrator wants to know which animals he should remove to make maximum number of happy children.     Input The input file contains multiple test cases, for each case, the first line contains three integers N <= 100, M <= 100 and P <= 500. Next P lines, each line contains a child's like-animal and dislike-animal, C for cat and D for dog. (See sample for details)     Output For each case, output a single integer: the maximum number of happy children.     Sample Input 1 1 2 C1 D1 D1 C1   1 2 4 C1 D1 C1 D1 C1 D2 D2 C1     Sample Output 1 3      題意：動物園有 N只貓，M只狗，有P個小孩去動物園，現在動物管理員，移除小孩不喜歡的而動物，最多可以使多少個小孩高興。 思路：建立完二分圖之後，相當於求二分圖的最大獨立集 = 頂點數 - 最大匹配數。

import java.io.*;  
import java.util.*;  
public class Main {  
    int n,m,p;  
    int[][] map;  
    int[] link=new int[600];  
    boolean[] mark=new boolean[600];  
    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();  
            m=sc.nextInt();  
            p=sc.nextInt();  
            Node node[]=new Node[p];  
            map=new int[600][600];  
            for(int i=0;i<p;i++){  
                String like=sc.next();  
                String dis=sc.next();  
                node[i]=new Node(like,dis);  
            }  
            //建立二分圖  
            for(int i=0;i<p;i++){  
                for(int j=i+1;j<p;j++){  
                    if(node[i].like.equals(node[j].dis)||node[i].dis.equals(node[j].like)){  
                        map[i][j]=1;  
                        map[j][i]=1;  
                    }  
                }  
            }  
            hungary();  
        }  
    }  
    //匈牙利算法  
    void hungary(){  
        Arrays.fill(link,0);  
        int ans=0;  
        for(int i=0;i<p;i++){  
            Arrays.fill(mark,false);  
            if(DFS(i))  
                ans++;  
        }  
        System.out.println(p-ans/2);//每個點用了兩次，所以要除以2  
    }  
      
      
    boolean DFS(int x){  
        for(int i=0;i<p;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{  
        String like;  
        String dis;  
        Node(String like,String dis){  
            this.like=like;  
            this.dis=dis;  
        }  
    }  
}