首页 > 代码库 > poj 1469(二分图 最大匹配)
poj 1469(二分图 最大匹配)
这道题让我认识到了c++cin,cout确实会使其超时,还是我用的c printf吧
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<climits>using namespace std;#define MAX 5005int p,n; int V1,V2; bool grid[105][305]; bool vis[305]; int link[305]; int m; //最大匹配数 bool dfs(int x) { for(int y=1;y<=V2;y++) if(grid[x][y] && !vis[y]) { vis[y]=true; if(link[y]==0 || dfs(link[y])) { link[y]=x; return true; } } return false; } void search(void) { for(int x=1;x<=V1;x++) { memset(vis,false,sizeof(vis)); if(dfs(x)) m++; } return; }int main(void){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&p,&n); int cn; m=0; memset(grid,0,sizeof(grid)); memset(link,0,sizeof(link)); for(int i=1;i<=p;i++) { scanf("%d",&cn); for(int j=1;j<=cn;j++) { int s; scanf("%d",&s); grid[i][s]=1; } } V1=p;V2=n; search(); if(m==p) printf("YES\n"); else printf("NO\n"); } return 0;}
poj 1469(二分图 最大匹配)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。