洛谷 P3386 【模板】二分图匹配
程序员文章站
2022-07-05 08:42:12
[TOC] 题目 "戳" 思路 ~~板子能有啥思路~~ $Code$ cpp include include include include include define MAXN 1001 using namespace std; int n,m,e; int qwq[MAXN][MAXN],ma ......
目录
题目
思路
板子能有啥思路
$code$
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #define maxn 1001 using namespace std; int n,m,e; int qwq[maxn][maxn],match[maxn]; bool vis[maxn]; inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } bool go(int x){ for(int i=1;i<=m;++i){ if(!vis[i]&&qwq[x][i]){ vis[i]=1; if(!match[i]||go(match[i])){ match[i]=x; return 1; } } } return 0; } int main(){ n=read(),m=read(),e=read(); int u,v; for(int i=1;i<=e;++i){ u=read(),v=read(); if(u>n||v>m) continue; qwq[u][v]=1; } int ans=0; for(int i=1;i<=n;++i){ memset(vis,0,sizeof(vis)); if(go(i)) ans++; } printf("%d\n",ans); return 0; }
上一篇: 解析 html 字符串
下一篇: ORACLE关于日志文件基本操作