首页 > 代码库 > poj1469二分图

poj1469二分图

  题意: 给你一个二分图,求最大匹配是否是 课程这边集合的顶点数。

数组开错了 wa了数次。

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;int Map[305][306];int link[305];int used[305];int p;int n;int dfs(int x){    int temp;    for(int i=1;i<=n;i++){        if(!used[i]&&Map[x][i]){            used[i]=1;            if(link[i]==-1||dfs(link[i])){                link[i]=x;                return 1;            }        }    }    return 0;}void solve(){    int ans=0;    memset(link,-1,sizeof(link));    for(int i=1;i<=p;i++){        memset(used,0,sizeof(used));        if(dfs(i)) ans++;    }    if(ans==p) cout<<"YES"<<endl;    else cout<<"NO"<<endl;}int main(){    int T;int c;    scanf("%d",&T);    while(T--){        memset(Map,0,sizeof(Map));        scanf("%d%d",&p,&n);        for(int i=1;i<=p;i++){            scanf("%d",&c);            for(int j=0;j<c;j++){                int t;                scanf("%d",&t);                Map[i][t]=1;            }        }        solve();    }    return 0;}