首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。