传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2063
很长时间没做二分图的题，今天挑个简单了温习下。没想到。。。。
二分图是没有有向图和有向图的概念吧。那这道题用双向图建图可能会被坑死吧。我用双向图交了n遍都不能过。
或许是后台数据男孩和女孩编号可能会大于a，b吧？那么你用mp的话点数就要开大一点了，不止500了。
WA代码：
#include <iostream> #include <cstdio> #include <cstring> 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 ",sum); } return 0; }
如果出现编号大于a的情况，加a不够吧，那我+500？还是WA。。
他么的，我加1000吧，然后过了。。。。诶，没意思。
双向的话，把编号当做下标的话，遍历的时候，是要比最大的下标为最后一个，所以dfs的时候也要到maxn，因为match可能到达那里。。。
你双向建图的话
两边编号要分开
两边编号要分开
男孩的编号就要+上最大那个女孩的编号
AC:
#include <iostream> #include <cstdio> #include <cstring> 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<maxn; 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 += 1000; 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 ",sum); } return 0; }
傻逼吧，还是单向建图轻松一点，只要一边女孩连完了，就结束了...
AC：
#include <iostream> #include <cstdio> #include <cstring> 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 ",sum); } return 0; }
这题跟啊哈算法上面的例子不同就在编号上，编号和人数是分开的。=-=
但是别人用的这个Vector 加了女生的数量为什么就A了呢，求解啊！！！
#include <cmath> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; #define met(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f const int maxn = 1000+10; vector<int> 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<p[u].size();i++) { int v=p[u][i]; if(!visited[v]) { visited[v]=true; if(match[v]==-1||dfs(match[v])) { match[v]=u; match[u]=v; return true; } } } return false; } int main() { int k,n,m; while(scanf("%d%d%d",&k,&n,&m)!=EOF&&k!=0) { for(int i=1;i<=max(n,m);i++) p[i].clear(); for(int i=0;i<k;i++) { int a,b; scanf("%d%d",&a,&b); b+=n+1; add(a,b); } int ans=0; met(match,-1); for(int i=1;i<=n;i++) { met(visited,false); if(dfs(i)) ans++; } printf("%d ",ans); } }
所以单向建图吧！