这个题目说,有一个N*N的规格的方格。某些格子里有*号,每次可以消除一行或者一列中所有的*号。最少需要消多少次?
新学到的,什么什么定理,最少点覆盖等于最大匹配数。
这个定理可以这样来理解(看别人的),对于最大匹配状态下的一条匹配边,不可能两边同时存在可连的未匹配点,因为这样就可以增广了,所以对于一条匹配边,只要选取在其有未匹配点的一边的点就可以了,对于其他的匹配边同理。
接下来就是上模版的时候了。。。
召唤代码君:
#include <cstdio> #include <vector> #define maxn 505 using namespace std; vector<int> r[maxn],c[maxn]; int tr[maxn],tc[maxn],fc[maxn],tagc[maxn]; int n,m,ans,R,C; bool dfs(int cur,int T) { for (unsigned i=0; i<r[cur].size(); i++) { if (tagc[r[cur][i]]==T) continue; tagc[r[cur][i]]=T; if (fc[r[cur][i]]==0 || dfs(fc[r[cur][i]],T)) { fc[r[cur][i]]=cur; return true; } } return false; } int main() { scanf("%d%d",&n,&m); for (int T=1; T<=m; T++) { scanf("%d%d",&R,&C); if (tr[R]!=1) r[R].clear(),tr[R]=1; if (tc[C]!=1) fc[C]=0,tagc[C]=0; r[R].push_back(C); } for (int i=1; i<=n; i++) if (tr[i]!=0 && dfs(i,i)) ans++; printf("%d\n",ans); return 0; }