pku3041-Asteroids 最小点覆盖

把行列看成点
再用匈牙利算法过

[cpp]
#include<iostream> 
#include<stdio.h> 
#include<string.h> 
using namespace std; 
 
bool mp[500][500],visit[500]; 
int link[500]; 
int m,n; 
bool find(int x) 
{ 
    int i; 
    for(i=1;i<=n;i++) 
    { 
        if(mp[x][i]&&!visit[i]) 
        { 
            visit[i]=1; 
            if(!link[i]||find(link[i])) 
            { 
                link[i]=x; 
        //      printf("%d,%d\n",x,i); 
                return true; 
            } 
        } 
    } 
    return false; 
} 
int main() 
{ 
    int i,j,x,y; 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
        memset(mp,0,sizeof(mp)); 
        for(i=1;i<=m;i++) 
        { 
            scanf("%d%d",&x,&y); 
            mp[x][y]=1; 
        } 
        memset(link,0,sizeof(link)); 
         
        x=0; 
        for(i=1;i<=n;i++) 
        { 
            memset(visit,0,sizeof(visit)); 
            if(find(i)) x++; 
        } 
        printf("%d\n",x); 
    } 
    return 0; 
} 

补充：软件开发 , C++ ,

上一个：pku1942-Paths on a Grid
下一个：SPOJ 1182. Sorted bit squence (数位统计+二分)