牛客练习赛30消消乐

r神在和小b比赛玩一个名为“消消乐”的游戏，在一个n*m的棋盘上，一些棋子分布在格点上，游戏玩家有一个名为超蓝光波的武器，可以消除一行或者一列的所有棋子，使用超蓝光波需要耗费一点能量，消除完所有的棋子之后，花费能量越少得分越高。 r神为了超过排名第一的小b，夺得荣誉称号“天下第一”，他需要寻求你的帮助，他希望知道最少需要使用多少次“超蓝光波”，以及在哪行、哪列使用。

主要是第二问吧 二分图匹配啊，dinic可秒了此题 去跑未匹配的，则这条边指向的点必匹配，这条边指向的点的匹配点必不匹配

#include<cstdio> #include<cctype> #include<cstring> #include<vector> using namespace std; const int N=2002; bool S[N],T[N]; int lky[N],lkx[N]; vector<int>G[N]; bool match(int u){ S[u]=1; for(int sz=G[u].size(),i=0;i<sz;i++){ int v=G[u][i]; if(!T[v]){ T[v]=1; if(!lky[v]||match(lky[v])){ lky[v]=u,lkx[u]=v; return 1; } } } return 0; } int n,m,k; void read(int& x){ char c=getchar();x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)){x=x*10+c-'0',c=getchar();} } char s[N][N]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%s",s[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;++j) if(s[i][j]=='*') G[i].push_back(j); int ans=0; for(int i=1;i<=n;i++)memset(T,0,sizeof(T)),ans+=match(i); printf("%d\n",ans); memset(S,0,sizeof S); memset(T,0,sizeof(T)); for(int i=1;i<=n;i++) if(!lkx[i])match(i); ans=0;for(int i=1;i<=n;i++)if(!S[i])++ans; printf("%d",ans); for(int i=1;i<=n;++i)if(!S[i])printf(" %d",i); puts("");ans=0; for(int i=1;i<=m;i++)if(T[i])++ans; printf("%d",ans); for(int i=1;i<=m;++i)if(T[i])printf(" %d",i); puts(""); return 0; }

转载于:https://www.cnblogs.com/MikuKnight/p/9903739.html