[Acwing] 376. 机器任务 二分图上的最小点集覆盖

前言

传送门 :

思路

最小点集覆盖问题 : 即求最小的点集使得每条边至少有一个端点在这个集合当中

因为对于顺序不做要求,因此这题是最小点集覆盖问题

由前人栽树后人乘凉定律 :

我们可以知道

定理 : 最小点覆盖 = 最大匹配

当然这题还需要注意的是,默认的模式是 0 0 0,因此对于 0 0 0我们不作考虑即可

粗略的证明: 选最少的点，满足每条边至少有一个端点被选，不难发现补集是独立集。 二分图中，最小点覆盖 =- 最大独立集。

Mycode

const int N = 110;
int n,m,k;
int match[N];
bool g[N][N],st[N];

bool find(int x){
	for(int i= 0;i>m>>k;
	memset(g,0,sizeof g);
	memset(match,-1,sizeof match);
	
	while(k -- ){
		int t,a,b;
		cin>>t>>a>>b;
		if(!a||!b)continue;//最初的模式是0
		g[a][b] = true;
	}
	
	int res = 0;
	for(int i = 0;i