LED Display（二分图 + 最小路径覆盖）

LED Display

---

Time Limit: 2 Seconds      Memory Limit: 65536 KB

---

One day in the laboratory, Fred found some LED displays. This seven-segment LED can display digit 0 to 9 properly. But Fred soon find the LED have a serious problem, at the beginning, the seven bars were all on. But when one bar once was trun off, it can't be turn on again! So ecah LED only can display digit in certain oder. For example, one LED can display 9,3,7 successively, but can't display 2,4.

Now, Fred have a task to display a sequence of digit that is between 0 to 9. Because of the shortcoming of these LEDs, he need a number of them. But he also want to minimize the number, can you help him?

NOTE:If two digits in a sequece are the same,Fred want for the clearness, so he thought the latter digit can't be displayed on the same LED.

Input:

The input consists of several test cases. The first line of each test case contains a positive integer N (<=1000), then followed by a list of N digits. Each digit follows with a blank space.

Output:

For each test case, you must print a minimum number of LED that Fred need in one line.

Sample Input:

1
8

4
9 0 7 3

8
8 8 8 9 6 5 4 1

Sample Output:

1
2		(Hint:one mothod is display {9,3} on the first LED; {0,7} on the second)
3		(Hint:one possible solution is {8},{8,9,4,1},{8,6,5})

 

       题意：

       给出 N （1 ~ 1000），代表有 N 个数，后给出这 N 个数是什么。0 ~ 9 中的某些数字灭了其中的一些 LED 灯能够显示成其他的数字，但是不能显示相同的数字，问需要最少多少个数字，能显示给出的所有 N 个数。

 

       思路：

       二分图 + 最小路径覆盖。将每个数字可以到达的下一个数化成一条条路径，不能到达则说明自己是一条路径，建成一个无环有向图，最后 N - 最大匹配既是答案。

 

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 1005;

int n;
int num[MAX], Map[MAX][MAX];
int linker[MAX], vis[MAX];

void build() {
    memset(Map, 0, sizeof(Map));

    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (num[i] == 0) {
                if (num[j] == 1) Map[i][j] = 1;
                if (num[j] == 7) Map[i][j] = 1;
            } else if (num[i] == 3) {
                if (num[j] == 1) Map[i][j] = 1;
                if (num[j] == 7) Map[i][j] = 1;
            } else if (num[i] == 4) {
                if (num[j] == 1) Map[i][j] = 1;
            } else if (num[i] == 6) {
                if (num[j] == 5) Map[i][j] = 1;
            } else if (num[i] == 7) {
                if (num[j] == 1) Map[i][j] = 1;
            } else if (num[i] == 8 &&
                       num[j] != 8) Map[i][j] = 1;
            else if (num[i] == 9) {
                if (num[j] == 1) Map[i][j] = 1;
                if (num[j] == 3) Map[i][j] = 1;
                if (num[j] == 4) Map[i][j] = 1;
                if (num[j] == 5) Map[i][j] = 1;
                if (num[j] == 7) Map[i][j] = 1;
            }
        }
    }
}

bool dfs (int u) {
    for (int v = 1; v <= n; ++v) {
        if (Map[u][v] && !vis[v]) {
            vis[v] = 1;
            if (linker[v] == -1 || dfs(linker[v])) {
                linker[v] = u;
                return true;
            }
        }
    }

    return false;
}

int hungary () {
    int res = 0;
    memset(linker, -1, sizeof(linker));

    for (int u = 1; u <= n; ++u) {
        memset(vis, 0, sizeof(vis));
        if (dfs(u)) ++res;
    }

    return res;
}

int main() {

    while(~scanf("%d", &n)) {

        for (int i = 1; i <= n; ++i)
            scanf("%d", &num[i]);

        build();

        printf("%d\n", n - hungary());
    }

    return 0;
}