传送门：
很长时间没做二分图的题，今天挑个简单了温习下。没想到。。。。
二分图是没有有向图和有向图的概念吧。那这道题用双向图建图可能会被坑死吧。我用双向图交了n遍都不能过。
或许是后台数据男孩和女孩编号可能会大于a，b吧？那么你用mp的话点数就要开大一点了，不止500了。
WA代码：
#include#include #include using namespace std;const int maxn = 1000+5;int e[maxn][maxn];int match[maxn];int book[maxn];int k;int n;int a,b;int dfs(int u){ for(int i=1; i<=n; i++) { if(book[i]==0 && e[u][i]==1) { book[i]=1; //标记点i已访问过 if(match[i]==0||dfs(match[i])) { //更新配对关系 match[i]=u; match[u]=i; return 1; } } } return 0;}int main(){// freopen("in.txt","r",stdin); int sum; while(scanf("%d",&k)&&k!=0) { scanf("%d%d",&a,&b); sum = 0; n = a+b; memset(e,0,sizeof(e)); memset(book,0,sizeof(book)); memset(match,0,sizeof(match)); sum=0; for(int i = 1; i <= k; i++) { int t1,t2; scanf("%d%d",&t1,&t2); t2 += a; e[t1][t2] = 1; e[t2][t1] = 1; } for(int i=1; i<=n; i++) { memset(book,0,sizeof(book));//清空上次搜索时的标记 if(dfs(i)) sum++; //寻找增广路，如果找到，配对数加1. } printf("%d\n",sum); } return 0;}
如果出现编号大于a的情况，加a不够吧，那我+500？还是WA。。
他么的，我加1000吧，然后过了。。。。诶，没意思。
双向的话，把编号当做下标的话，遍历的时候，是要比最大的下标为最后一个，所以dfs的时候也要到maxn，因为match可能到达那里。。。
你双向建图的话 两边编号要分开
男孩的编号就要+上最大那个女孩的编号
AC:
#include#include #include using namespace std;const int maxn = 2000+5;int e[maxn+5][maxn+5];int match[maxn+5];int book[maxn+5];int k;int n;int a,b;int dfs(int u){ for(int i=1; i
傻逼吧，还是单向建图轻松一点，只要一边女孩连完了，就结束了...
AC：
#include#include #include using namespace std;const int maxn = 1000+5;int e[maxn][maxn];int match[maxn];int book[maxn];int k;int n;int a,b;int dfs(int u){ //每个女生连通男孩的边最多为b，枚举最多可能b的边 for(int i=1; i<=b; i++) { if(book[i]==0 && e[u][i]==1) { book[i]=1; //标记点i已访问过 if(match[i]==0||dfs(match[i])) { //更新配对关系 match[i]=u; return 1; } } } return 0;}int main(){// freopen("in.txt","r",stdin); int sum; while(scanf("%d",&k)&&k!=0) { scanf("%d%d",&a,&b); sum = 0; n = a+b; memset(e,0,sizeof(e)); memset(book,0,sizeof(book)); memset(match,0,sizeof(match)); sum=0; for(int i = 1; i <= k; i++) { int t1,t2; scanf("%d%d",&t1,&t2); e[t1][t2] = 1; } //每个女生必须找个男生，所以每个女生搜一遍就可以了 for(int i=1; i<=a; i++) { memset(book,0,sizeof(book));//清空上次搜索时的标记 if(dfs(i)) sum++; //寻找增广路，如果找到，配对数加1. } printf("%d\n",sum); } return 0;}
这题跟啊哈算法上面的例子不同就在编号上，编号和人数是分开的。=-=
但是别人用的这个Vector 加了女生的数量为什么就A了呢，求解啊！！！
#include#include #include #include #include using namespace std;#define met(a,b) memset(a,b,sizeof(a))#define inf 0x3f3f3f3fconst int maxn = 1000+10;vector p[maxn];int match[maxn];bool visited[maxn];void add(int u,int v){ p[u].push_back(v); p[v].push_back(u);}bool dfs(int u){ visited[u]=true; for(int i=0;i
所以单向建图吧！