Felix021

function maketbl($str) {
    $str = str_replace("<br/>", "\n", $str);
    $str = str_replace("&#124;", "|", $str);
    $str = trim($str);
    $lines = explode("\n", $str);
    $firstline = explode("|", trim($lines[0]));
    $conf = array();
    foreach($firstline as $v) {
        switch($v) {
        case 'l':
            $conf[] = 'left';
            break;
        case 'r':
            $conf[] = 'right';
            break;
        case 'c':
            $conf[] = 'center';
            break;
        default:
            $conf[] = '';
        }
    }
    $ncols = count($conf);
    $nline = count($lines);
    $ret = '<table cellspacing="0" cellpadding="3" border="1">'. "\n";
    for ($i = 1; $i < $nline; $i++) {
        $line = trim($lines[$i]);
        if (empty($line)) continue;
        $line = explode("|", $line);
        $ret .= "<tr>\n";
        $next = 1;
        for ($j = 0; $j < $ncols; $j++) {
            if ($line[$j] == "[-]") {
                $next++;
                continue;
            }
            $td = $line[$j];
            //$td = htmlspecialchars($td);
            $td = str_replace("[newline]", "<br/>", $td);
            $ret .= <<<eot
<td align="{$conf[$j]}" colspan="{$next}">{$td}</td>

eot;
            if ($line[$j] != "[-]") {
                $next = 1;
            }
        }
        $ret .= "</tr>\n";
    }
    $ret .= "</table>";
    return $ret;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 8

int count;
int rows[N],    cols[N],    slash[2 * N - 1], bslash[2 * N - 1];
//每行放的位置，纵向不可放，斜向不可放（/），斜向不可放(\)

void place(int i) {
    int j;
    for (j = 0; j < N; ++j) {
        if (cols[j] == 0 && slash[i + j] == 0 && bslash[i + (N-1) - j] == 0) {
            rows[i] = j;

            cols[j] = 1;
            slash[i + j] = 1;
            bslash[i + (N-1) - j] = 1;

            if (i == N - 1) {
                /*
                int k;
                for (k = 0; k < N; ++k) {
                    printf("%d ", rows[k]);
                }
                printf("\n");
                */
                count++;
            }
            else {
                place(i + 1);
            }

            //回溯
            cols[j] = 0;
            slash[i + j] = 0;
            bslash[i + (N-1) - j] = 0;
        }
    }
}

int main () {

    memset(rows, 0, sizeof(rows));
    memset(cols, 0, sizeof(cols));
    memset(slash, 0, sizeof(slash));
    memset(bslash, 0, sizeof(bslash));

    count = 0;
    place(0);
    printf("count = %d\n", count);
    return 0;
}

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

/*
* Kruskal贪心算法求最小生成树(heap+并查集)
* 测试输入数据：

6 10 //6个顶点10条边
1 5 2  //从顶点1到顶点5的边权重为2
2 4 3
4 5 1
0 3 6
2 3 7
5 2 6
4 0 7
1 3 5
1 2 4
3 5 9

*/

struct edge {
    int start, end, weight;
};

void siftdown (struct edge *a, int n, int i) {
    struct edge t;
    if (i < 1 || i > n) return;
    while (i * 2 <= n) {
        i *= 2;
        if (i + 1 <= n && a[i].weight > a[i + 1].weight) i++;
        if (a[i].weight < a[i/2].weight ) {
            t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else {
            break;
        }
    }
}

void siftup (struct edge *a, int n, int i) {
    struct edge t;
    if (i < 1 || i > n) return;
    while (i > 1) {
        if (a[i].weight < a[i/2].weight) {
            t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else {
            break;
        }
        i /= 2;
    }
}

void makeheap(struct edge *a, int n) {
    int i;
    for (i = n / 2; i >= 1; --i) {
        siftdown(a, n, i);
    }
}

struct edge pop(struct edge *a, int *n) {
    struct edge t;
    t = a[1];
    a[1] = a[*n];
    (*n)--; //第二次挂在这里，不能写*n--(*n; n-=1;), 要写(*n)--
    siftdown(a, *n, 1);
    return t;
}

void dump(struct edge *a, int n) {
    int i;
    for (i = 0; i < n; ++i) {
        printf("edge (%d, %d), %d\n", a[i].start, a[i].end, a[i].weight);
    }
}

void initUnionSet(int a[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        a[i] = i;
    }
}

int getFather(int a[], int x) {
    return a[x] == x ? x : (a[x] = getFather(a, a[x]));
}

void merge(int a[], int x, int y) {
    x = getFather(a, x);
    y = getFather(a, y);
    a[x] = y;
}

int haveCommonAncestor(int a[], int x, int y) {
    return (getFather(a, x) == getFather(a, y) ? 1 : 0);
}


int main () {
    int m, n, i, k, *father;
    struct edge *input, *output, t;

    scanf("%d%d", &m, &n);
    input = (struct edge *)malloc(sizeof(struct edge) * (n + 1));
    for (i = 1; i <= n; ++i) {
        scanf("%d%d%d", &input[i].start, &input[i].end, &input[i].weight);
    }
    makeheap(input, n);
    dump(input+1, n);
    printf("end input\n");
    
    int n1 = n;
    output = (struct edge *)malloc(sizeof(struct edge) * (m - 1));
    father = (int *)malloc(sizeof(int) * n);
    initUnionSet(father, m);
    k = 0;
    printf("\nStart:\n");
    while (n1 > 0) {
        t = pop(input, &n1);
        printf("edge (%d,%d), %d ", t.start, t.end, t.weight);
        if (0 == haveCommonAncestor(father, t.start, t.end)) {
            printf("added in\n");
            output[k] = t;
            k++;
            merge(father, t.start, t.end);
            if (k == m - 1) {
                printf("~~ok~~\n");
                break;
            }
        }
        else {
            printf("ignored\n");
        }
    }
    printf("\nresult:\n");
    dump(output, k);

    free(input);
    free(output);
    free(father);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#ifdef __GNUC__
    #define WARN_IF_UNUSED __attribute__ ((warn_unused_result))
#else
    #define WARN_IF_UNUSED
#endif


struct node {
    int v;
    struct node *next;
};

struct linklist {
    struct node *head;
    struct node *tail;
};

WARN_IF_UNUSED int init(struct linklist ll[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        ll[i].head = (struct node *)malloc(sizeof(struct node));
        if (ll[i].head == NULL) {
            return 0;
        }
        ll[i].head->next = NULL;
        ll[i].tail = ll[i].head;
    }
    return 1;
}

void dump(struct linklist *ll) {
    struct node *p = ll->head->next;
    while (p != NULL) {
        printf("%d ", p->v);
        p = p->next;
    }
    printf("\n");
}

WARN_IF_UNUSED int push(struct linklist *ll, int v) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (p == NULL) {
        return 0;
    }
    p->v = v;
    p->next = NULL;
    ll->tail->next = p;
    ll->tail = p;
    return 1;
}

int isEmpty(struct linklist *ll) {
    return (ll->head->next == NULL) ? 1 : 0;
}


int pop(struct linklist *ll) {
    if (isEmpty(ll)) {
        exit(1);
    }
    struct node *p = ll->head;
    ll->head = p->next;
    free(p);
    return ll->head->v;
}

void radixSort(int a[], int n) {
    struct linklist ll[10];
    int flag, i, j, t, fact = 1;
    if (init(ll, 10) == 0) {
        exit(2);
    }
    do {
        printf("---------------\n");
        flag = 0;
        for (i = 0; i < n; ++i) {
            t = a[i] / fact % 10;
            flag += !!t;
            //printf("%d: %d\n", a[i], t);
            if (push(&ll[t], a[i]) == 0) {
                exit(2);
            }
        }
        for (i = 0, j = 0; i < 10; ++i) {
            printf("%d: ", i);
            dump(&ll[i]);
        }
        for (i = 0, j = 0; i < 10; ++i) {
            while (isEmpty(&ll[i]) == 0) {
                a[j] = pop(&ll[i]);
                j++;
            }
        }
        fact *= 10;
    }while (flag != 0);
}

int main() {
    int a[] = {26,62,187,32,8754359,45324,54654,0,331,321312,12,4324,87,98};
#define N (sizeof(a) / sizeof(int))
    radixSort(a, N);
    int i;
    for (i = 0; i < N; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}