恩。。。最小顶点覆盖。
给你N*N的矩阵，里面有的方格里有小行星，你需要用激光射掉它。。。激光可以射掉一行 或者一列的小行星，问最小需要发射多少次
最小顶点覆盖。。恩。。
对二分图最大匹配开始有点小误区，以为必须两个相连的顶点必须是不同编号的，所以呢，我之前都是把图建的好大。。。恩。。。
这个呢，正好看的某个论文里有类似这题的，直接建图就好了 = =。。按照给的行星的坐标建就好。。
开始一直WA，换了个数组模拟邻接表的那个模板，还是WA。。。仔细检查了下，发现增广最后的return 1了 = =。。。哎。。粗心死。。
I
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <algorithm> #define MAX 505 using namespace std; int map[MAX][MAX]; int used[MAX]; int match[MAX]; int Augement(int n,int x) { int i; for(i=1; i<=n; i++) if( !used[i] && map[x][i]) { used[i] = 1; if( match[i] == 0 || Augement(n,match[i]) ) { match[i] = x; return 1; } } return 0; } int Hungary(int n) { memset(match,0,sizeof(match)); int i,sum = 0; for(i=1; i<=n; i++) { memset(used,0,sizeof(used)); if( Augement(n,i) ) sum++; } return sum; } int main() { int n,m,ans,i,x,y; while( ~scanf("%d%d",&n,&m) ) { memset(map,0,sizeof(map)); for(i=1; i<=m; i++) { scanf("%d%d",&x,&y); map[x][y] = 1; } ans = Hungary(n); printf("%d/n",ans); } return 0; }
II
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <algorithm> #define MAX 505 using namespace std; int map[MAX][MAX]; int used[MAX]; int match[MAX]; int Augement(int x) { int i,k; for(i=1; i<=map[x][0]; i++) { k = map[x][i]; if( !used[k] ) { used[k] = 1; if( match[k] == 0 || Augement(match[k]) ) { match[k] = x; return 1; } } } return 0; } int Hungary(int n) { memset(match,0,sizeof(match)); int i,sum = 0; for(i=1; i<=n; i++) { memset(used,0,sizeof(used)); if( Augement(i) ) sum++; } return sum; } int main() { int n,m,ans,i,x,y; while( ~scanf("%d%d",&n,&m) ) { memset(map,0,sizeof(map)); for(i=1; i<=m; i++) { scanf("%d%d",&x,&y); map[x][++map[x][0]] = y; } ans = Hungary(n); printf("%d/n",ans); } return 0; }
