阿祁的部落格

ZeroJudge i179 - 防守城堡 解題心得( 題目 )

解題概念:匈牙利演算法

解題方法:這題每個十字剛好影響一個直和橫的炮台，所以可以看成圖論，而且他是二分圖，答案其實就和二分圖匹配有關，可用匈牙利演算法以O(N^3)求得。

Java參考程式碼(有更好意見可留言於下方，謝謝!):

//Author:En Chi Tsung(欉恩祁)

//Date:2022/05/18

import java.io.*;

import java.math.*;

import java.util.*;

public class zji179{

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static int ret,rd;

    public static int[] vis=new int[1005];

    public static int[] mat=new int[1005];

    public static ArrayList<ArrayList<Integer>> e=new ArrayList<>();

    public static void main(String[] args) throws Exception{

        final int m=readint();

        final int n=readint();

        final int t=readint();

        for(int i=0;i<m;i++) {

            e.add(new ArrayList<>());


            vis[i]=-1;

            mat[i]=-1;

        }

        Arrays.fill(vis,-1);

        Arrays.fill(mat,-1);

        for(int i=0;i<t;i++) {

            e.get(readint()).add(readint()+m);

        }

        int ans=m+n;

        for(int i=0;i<m;i++) {

            ans-=dfs(i,i);

        }

        System.out.println(ans);

    }

    

    public static int dfs(int x,int y){

        if(vis[x]==y)return 0;

         vis[x]=y;

        for(int i:e.get(x)){

            if((mat[i]==-1)||(dfs(mat[i],y)==1)){

                mat[i]=x;

                return 1;

            }

        }

        return 0;

    }

    

    public static int readint() throws Exception{

        ret=0;

        rd=br.read();

        while(rd>47&&rd<58) {

            ret*=10;

            ret+=(rd&15);

            rd=br.read();

        }

        return ret;

    }

}