首页 > 代码库 > 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(二分图 最大匹配)