The Accomodation of Students---hdu2444

最终没找到我自己的错误求大神指点。贴一个正确的#include<stdio.h> #include <vector> #include <string.h> #include<iostream> #define max_V 1000 using namespace std; int V; vector<int> G[max_V];//图的邻接表 int match[max_V];//妹子是否被相亲 bool used[max_V];//不能嫁给自己 void add_edge(int u,int v) { G[u].push_back(v); G[v].push_back(u); } bool dfs(int v) { used[v]=1; for(int i=0; i<G[v].size(); i++) { int u=G[v][i]; int w=match[u]; if(w<0||(!used[w]&&dfs(w))) { match[v]=u; match[u]=v; return 1; } } return 0; } int bi_match() { int res=0; memset(match,-1,sizeof(match)); for(int v=0; v<V; v++) { memset(used,0,sizeof(used)); if(dfs(v))res++; } return res; } int color[201]; int main() { int n,k,x,y; int flag=0; while(~scanf("%d%d",&n,&k)) { flag=0; V=2*n; memset(color, 0, sizeof(color)); for(int i=0; i<k; i++) { scanf("%d%d",&x,&y); add_edge(x-1,n+y-1); if(color[x]==0 && color[y]==0) { color[x] = 1; color[y] = -1; } else if(color[x]!=0 && color[y]==0) color[y] = -color[x]; else if(color[x]==0 && color[y]!=0) color[x] = -color[y]; else if(color[x]==color[y] && color[x]!=0) flag=1; } if(flag==1){ printf("No\n"); continue;} printf("%d\n",bi_match()); } return 0; } 自己的 #include<stdio.h> #include <vector> #include <string.h> #include<iostream> #define max_V 1000 using namespace std; int V; vector<int> G[max_V];//图的邻接表 int match[max_V];//妹子是否被相亲 bool used[max_V];//不能嫁给自己 void add_edge(int u,int v) { G[u].push_back(v); // G[v].push_back(u); } bool dfs(int v) { used[v]=1; for(int i=0; i<G[v].size(); i++) { int u=G[v][i]; int w=match[u]; if(w<0||(!used[w]&&dfs(w))) { match[v]=u; match[u]=v; return 1; } } return 0; } int bi_match() { int res=0; memset(match,-1,sizeof(match)); for(int v=0; v<V; v++) { memset(used,0,sizeof(used)); if(dfs(v))res++; } return res; } int color[201]; int main() { int n,k,x,y; int flag=0; while(~scanf("%d%d",&n,&k)) { flag=0; V=2*n; memset(color, 0, sizeof(color)); for(int i=0; i<k; i++) { scanf("%d%d",&x,&y); add_edge(x-1,n+y-1); if(color[x]==0 && color[y]==0) { color[x] = 1; color[y] = -1; } else if(color[x]!=0 && color[y]==0) color[y] = -color[x]; else if(color[x]==0 && color[y]!=0) color[x] = -color[y]; else if(color[x]==color[y] && color[x]!=0) flag=1; } if(flag==1){ printf("No\n"); continue;} printf("%d\n",bi_match()); } return 0; }