[TIOJ 1089] Asteroids

作法：

先把原題轉成圖論敘述，有一個點落在 ( x,y ) 的話就代表他所在的直的那排和橫的那排至少要有一個有被選到發射光束，考慮一個二部圖，一邊是 n 的點代表表格的行，一邊是 n 個點代表表格的列，如果 ( x,y ) 有隕石的話就在左邊的 x 和右邊的 y 之間連一條邊，並且我們要求的東西是「一個大小最小的頂點集，使得每條邊都有其中一個端點落在這個頂點集裡面」，而這就是有名的NPC問題「vertex cover problem」，但因為這題的圖是二部圖，König's theorem告訴我們答案等於最大匹配數，所以可以直接套二部無權圖最大匹配的算法。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500+10 ;
 
int my[maxn] ;
int adj[maxn][maxn],n ;
bool vis[maxn] ;
bool dfs(int x)
{
    vis[x]=1 ;
    for(int i=1;i<=n;i++) if(adj[x][i])
    {
        if(my[i]==-1 || (!vis[my[i]] && dfs(my[i])))
        {
            my[i]=x ; return 1 ;
        }
    }
    return 0 ;
}
 
main()
{
    int k ; scanf("%d%d",&n,&k) ;
    while(k--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        adj[x][y]=1 ;
    }
    memset(my,-1,sizeof(my)) ;
    int ans=0 ;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis)) ;
        if(dfs(i)) ans++ ;
    }
    printf("%d\n",ans) ;
}