首页 > 代码库 > ZOJ 3954 Seven-Segment Display

ZOJ 3954 Seven-Segment Display

二分图匹配。

先检查每个数字$1$的个数是否满足条件,不满足直接就是无解。剩下的情况可以建立二分图,如果现在的某一列可以对应于原图的某一列,那么建边。如果二分图的最大匹配是$7$,则有解,否则误解。

#include<bits/stdc++.h>using namespace std;int n;int num[15],g[15][15];char s[15][15];int c[20];int cx[15], cy[15];int mk[15],nx,ny;int path(int u){    for (int v = 0; v<ny; v++)    {        if (g[u][v] && !mk[v])        {            mk[v] = 1;            if (cy[v] == -1 || path(cy[v]))            {                cx[u] = v;                cy[v] = u;                return 1;            }        }    }    return 0;}int MaxMatch(){    int res = 0;    memset(cx, -1, sizeof(cx));    memset(cy, -1, sizeof(cy));    for (int i = 0; i<nx; i++)    {        if (cx[i] == -1)        {            memset(mk, 0, sizeof(mk));            res = res + path(i);        }    }    return res;}char m[15][15]={    "",    "1001111",    "0010010",    "0000110",    "1001100",    "0100100",    "0100000",    "0001111",    "0000000",    "0000100"};void init(){    c[1]=2;    c[2]=5;    c[3]=5;    c[4]=4;    c[5]=5;    c[6]=6;    c[7]=3;    c[8]=7;    c[9]=6;}int main(){    init();  int T;    scanf("%d",&T);    int fail;    while(T--)    {        fail=0;        scanf("%d",&n);        for(int i=1;i<=n;i++) scanf("%d%s",&num[i],s[i]);        for(int i=1;i<=n;i++)        {            int sum=0;            for(int j=0;s[i][j];j++)            {                if(s[i][j]==0) sum++;            }            if(sum!=c[num[i]]) fail=1;        }        if(fail)        {            printf("NO\n");            continue;        }        for(int i=0;i<=6;i++)        {            for(int j=0;j<=6;j++)            {                g[i][j]=1;            }        }        for(int i=1;i<=n;i++)        {            for(int j=0;s[i][j];j++)            {                for(int k=0;k<m[num[i]][k];k++)                {                    if(s[i][j]!=m[num[i]][k]) g[j][k]=0;                }            }        }        nx=7,ny=7;        int ans = MaxMatch();        if(ans!=7) printf("NO\n");        else printf("YES\n");    }    return 0;}

 

ZOJ 3954 Seven-Segment Display