首页 > 代码库 > poj1466二分图

poj1466二分图

  左右互搞。要除以(roll神 教的)

二分图中

最大独立点集 = 顶点 -  最大匹配

#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;const int maxn=555;int used[maxn];int link[maxn];int Map[maxn][maxn];int n;int dfs(int x){    for(int i=0;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(){    memset(link,-1,sizeof(link));    int ans=0;    for(int i=0;i<n;i++){        memset(used,0,sizeof(used));        if(dfs(i)) ans++;    }    cout<<n-ans/2<<endl;}int main(){    int a;int b;int c;    char str[100];    while(scanf("%d",&n)!=EOF){        for(int i=0;i<n;i++)        for(int j=0;j<n;j++)        Map[i][j]=0;        for(int i=0;i<n;i++){            scanf("%d: (%d)",&a,&b);            for(int j=0;j<b;j++){                scanf("%d",&c);                Map[a][c]=1;            }        }        solve();    }    return 0;}