首页 > 代码库 > 【POJ 1698】Alice's Chance(二分图多重匹配)

【POJ 1698】Alice's Chance(二分图多重匹配)

http://poj.org/problem?id=1698

电影和日子匹配,电影可以匹配多个日子。

最多有maxw*7个日子。

二分图多重匹配完,检查一下是否每个电影都匹配了要求的日子那么多。

#include<cstdio>#include<cstring>#include<algorithm>#define N 360#define M 30using namespace std;int t,n,m;int g[N][M];int linker[M][N],num[M];bool vis[M];bool dfs(int u){    for(int v=0;v<m;v++)    if(g[u][v]&& !vis[v]){        vis[v]=1;        if(linker[v][0]<num[v]){            linker[v][++linker[v][0]]=u;            return 1;        }        for(int i=1;i<=num[v];i++)        if(dfs(linker[v][i])){            linker[v][i]=u;            return 1;        }    }    return 0;}int hungary(){    int res=0;    for(int i=0;i<m;i++)        linker[i][0]=0;    for(int u=0;u<n;u++){        memset(vis,0,sizeof vis);        if(dfs(u))res++;    }    return res;}bool solve(){    hungary();    for(int i=0;i<m;i++){     //   printf("{%d}",linker[i][0]);        if(linker[i][0]!=num[i])            return 0;    }    return 1;}int main(){    scanf("%d",&t);    while(t--){        scanf("%d",&m);        memset(g,0,sizeof g);        int maxw=0;        for(int i=0;i<m;i++)        {            for(int j=0;j<7;j++)                scanf("%d",&g[j][i]);            int w;            scanf("%d%d",&num[i],&w);            maxw=max(maxw,w);            for(int j=0;j<7;j++)if(g[j][i])            for(int k=1;k<w;k++)                g[j+k*7][i]=1;        }        n=maxw*7;        if(solve())puts("Yes");        else puts("No");    }    return 0;}

  

【POJ 1698】Alice's Chance(二分图多重匹配)