算法
二分图+匹配
思路
节点
列与行皆为节点
边
一个子链接一个边与一个列。
0要素
一个子不可在两列或是两行。所以连接一个行与一个趔
1要素
每行只可有一个子,列也一样。
代码
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> using namespace std; inline int read() { int s=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') w=-w; c=getchar(); } while(c>='0'&&c<='9') { s=s*10+c-'0'; c=getchar(); } return s*w; } const int N=205; int n,m,k,ans; int fri[N]; bool flag[N][N],vis[N]; bool dfs(int x) { for(int y=1;y<=m;y++) { if(flag[x][y]||vis[y]) continue; vis[y]=1; if(!fri[y]||dfs(fri[y])) { fri[y]=x; return 1; } } return 0; } int main() { n=read(); m=read(); k=read(); for(int i=1;i<=k;i++) { int x,y; x=read(); y=read(); flag[x][y]=1; } ans=0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } printf("%d\n",ans); return 0; } 作者:ruanmowen 链接:https://www.acwing.com/activity/content/code/content/275964/ 来源:AcWing 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。