1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <stdio.h>
#include <stdlib.h>

#define N 10    // 問題規模

// 求最大不相交連接數
void maxNum(int pi[], int **size);

// 建構最大不相交連接集合，net[i]表示最大不相交子集中第i條連線的上端接線柱的序號
int constructSet(int pi[], int **size, int *net);

int main(void){
    // 索引從1開始
    int pi[N+1] = {0, 8, 7, 4, 2, 5, 1, 9, 3, 10, 6};
    int net[N];

    int **size;
    size = (int**)malloc(sizeof(int*)*(N+1));
    for(int i=0;i<N+1;i++)
        size[i]=(int*)malloc(sizeof(int)*(N+1));
    maxNum(pi, size);
    int m = constructSet(pi, size, net);   
    printf("最大不相交連接數為：%d\n",m);
    printf("包含的連線為：\n");
    for(int i=0; i<m; i++){
        printf("(%d,%d)\n", net[i], pi[net[i]]);
    }

}

void maxNum(int pi[], int **size){
    // size[i][j]: 上下端分別有i個和j個接線柱的電路板的第一層最大不相交連接數
    int i,j;

    // when j<pi(1)
    for(j=0; j<pi[1]; j++)
        size[1][j];

    // when j>=pi(1)
    for(j=pi[1]; j<=N; j++)
        size[1][j];

    for(i=2; i<N; i++){

        // when j<pi(i)
        for(j=0; j<pi[i]; j++)
            size[i][j] = size[i-1][j];   

        // when j>=c[i]
        for(j=pi[i]; j<=N; j++)
            size[i][j]=size[i-1][j]>=size[i-1][pi[i]-1]+1 ? size[i-1][j] : size[i-1][pi[i]-1]+1;
    }

    // 最大連接數
    size[N][N] = size[N-1][N]>=size[N-1][pi[N]-1]+1 ? size[N-1][N] : size[N-1][pi[N]-1]+1;
}

// 建構最大不相交連接集合，net[i]表示最大不相交子集中第i條連線的上端接線柱的序號
int constructSet(int pi[], int **size, int *net){
    int i;
    int j=N;
    int m=0;    // 記錄最大連接集合中的接線柱

    for(i=N; i>1; i--){ // 遞減
        // (i,pi[i])是最大不相交子集的一條連線
        if(size[i][j] != size[i-1][j]){
            net[m++]=i; // 將i記錄到陣列net中，連線數自增1
            j=pi[i]-1;  // 更新擴充連線柱區間
        }
    }

    // when i=1
    if(j>=pi[1])
        net[m++] = 1;

    return m;
}