{"id":667,"date":"2019-06-09T09:15:57","date_gmt":"2019-06-09T01:15:57","guid":{"rendered":"http:\/\/fankasy.xyz\/?p=667"},"modified":"2019-09-25T09:16:58","modified_gmt":"2019-09-25T01:16:58","slug":"noj1049-%e9%a3%9e%e6%9c%ba%e6%9c%80%e5%b0%91%e6%8d%a2%e4%b9%98%e6%ac%a1%e6%95%b0%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"http:\/\/fankasy.xyz\/index.php\/2019\/06\/09\/noj1049-%e9%a3%9e%e6%9c%ba%e6%9c%80%e5%b0%91%e6%8d%a2%e4%b9%98%e6%ac%a1%e6%95%b0%e9%97%ae%e9%a2%98\/","title":{"rendered":"NOJ1049 \u98de\u673a\u6700\u5c11\u6362\u4e58\u6b21\u6570\u95ee\u9898"},"content":{"rendered":"
#include<stdio.h> \/\/ printf()\r\n#include<stdlib.h> \/\/ malloc(), free()\r\n#include<limits.h> \/\/ INT_MAX for noEdgeValue\r\n\r\ntypedef int ElemType;\r\n\r\ntypedef int BOOL;\r\n#define TRUE 0\r\n#define FALSE -1\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\/\/ P.34\r\n\/\/ Program 3.2 Queue\r\ntypedef struct\r\n{\r\n    int front;\r\n    int rear;\r\n    int maxSize;\r\n    ElemType* element;\r\n}Queue;\r\n\r\nvoid Create(Queue* Q, int mSize)\r\n{\r\n    Q->maxSize = mSize;\r\n    Q->element = (ElemType*)malloc(sizeof(ElemType) * mSize);\r\n    Q->front = Q->rear = 0;\r\n}\r\n\r\n\/\/ Function name conflicted with Destroy() of mGraph, so I changed its name...\r\nvoid Destroy_Queue(Queue* Q)\r\n{\r\n    Q->maxSize = -1;\r\n    free(Q->element);\r\n    Q->front = Q->rear = -1;\r\n}\r\n\r\nBOOL IsEmpty(Queue* Q)\r\n{\r\n    return Q->front == Q->rear;\r\n}\r\n\r\nBOOL IsFull(Queue* Q)\r\n{\r\n    return (Q->rear + 1) % Q->maxSize == Q->front;\r\n}\r\n\r\nBOOL Front(Queue * Q, ElemType * x)\r\n{\r\n    if (IsEmpty(Q))\r\n        return FALSE;\r\n\r\n    *x = Q->element[(Q->front + 1) % Q->maxSize];\r\n\r\n    return TRUE;\r\n}\r\n\r\nBOOL EnQueue(Queue * Q, ElemType x)\r\n{\r\n    if (IsFull(Q))\r\n        return FALSE;\r\n\r\n    Q->rear = (Q->rear + 1) % Q->maxSize;\r\n    Q->element[Q->rear] = x;\r\n\r\n    return TRUE;\r\n}\r\n\r\nBOOL DeQueue(Queue * Q)\r\n{\r\n    if (IsEmpty(Q))\r\n        return FALSE;\r\n\r\n    Q->front = (Q->front + 1) % Q->maxSize;\r\n\r\n    return TRUE;\r\n}\r\n\r\nvoid Clear(Queue * Q)\r\n{\r\n    Q->front = Q->rear = 0;\r\n}\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\/\/ MGraph\r\n\/\/ P.139 - 141\r\n\r\n\/\/ P.139\r\ntypedef int ElemType;\r\ntypedef struct\r\n{\r\n    ElemType** a;\r\n    int n;\r\n    int e;\r\n    ElemType noEdge;\r\n}mGraph;\r\n\r\n\/\/ P.139 Program 9.1\r\n#define ERROR 0\r\n#define OK 1\r\n#define Overflow 2\r\n#define Underflow 3\r\n#define NotPresent 4\r\n#define Duplicate 5\r\ntypedef int Status;\r\n\r\nStatus Init(mGraph * mg, int nSize, ElemType noEdgeValue)\r\n{\r\n    int i, j;\r\n\r\n    mg->n = nSize;\r\n    mg->e = 0;\r\n    mg->noEdge = noEdgeValue;\r\n    mg->a = (ElemType * *)malloc(nSize * sizeof(ElemType*));\r\n    if (!mg->a)\r\n        return ERROR;\r\n\r\n    for (i = 0; i < mg->n; i++)\r\n    {\r\n        mg->a[i] = (ElemType*)malloc(nSize * sizeof(ElemType));\r\n\r\n        for (j = 0; j < mg->n; j++)\r\n            mg->a[i][j] = mg->noEdge;\r\n\r\n        mg->a[i][i] = 0;\r\n    }\r\n\r\n    return OK;\r\n}\r\n\r\n\/\/ P.140 Program 9.2\r\nvoid Destroy(mGraph * mg)\r\n{\r\n    int i;\r\n\r\n    for (i = 0; i < mg->n; i++)\r\n        free(mg->a[i]);\r\n\r\n    free(mg->a);\r\n}\r\n\r\n\/\/ P.140 Program 9.3\r\nStatus Exist(mGraph * mg, int u, int v)\r\n{\r\n    if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v || mg->a[u][v] == mg->noEdge)\r\n        return ERROR;\r\n\r\n    return OK;\r\n}\r\n\r\n\/\/ P.140 Program 9.4\r\nStatus Insert(mGraph * mg, int u, int v, ElemType w)\r\n{\r\n    if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v)\r\n        return ERROR;\r\n\r\n    if (mg->a[u][v] != mg->noEdge)\r\n        return Duplicate;\r\n\r\n    mg->a[u][v] = w;\r\n    mg->e++;\r\n\r\n    return OK;\r\n}\r\n\r\n\/\/ P.140 Program 9.5\r\nStatus Remove(mGraph * mg, int u, int v)\r\n{\r\n    if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v)\r\n        return ERROR;\r\n\r\n    if (mg->a[u][v] == mg->noEdge)\r\n        return NotPresent;\r\n\r\n    mg->a[u][v] = mg->noEdge;\r\n    mg->e--;\r\n\r\n    return OK;\r\n}\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\/\/ DFS\r\n\/\/ There are not any DFS programs based on MGraph in the textbook, \r\n\/\/ so I made it...\r\nvoid DFS(int v, int visited[], mGraph g)\r\n{\r\n    int i;\r\n\r\n    printf(\"%d \", v);\r\n    visited[v] = 1;\r\n\r\n    for (i = 0; i < g.n; i++)\r\n    {\r\n        if (g.a[v][i] != 0 && g.a[v][i] != g.noEdge && !visited[i])\r\n        {\r\n            DFS(i, visited, g);\r\n        }\r\n    }\r\n}\r\n\r\nvoid DFSGraph(mGraph g)\r\n{\r\n    int i;\r\n\r\n    \/\/ Init visited\r\n    int* visited = malloc(g.n * sizeof(int));\r\n    for (i = 0; i < g.n; i++)\r\n        visited[i] = 0;\r\n\r\n    \/\/ Do DFS\r\n    for (i = 0; i < g.n; i++)\r\n    {\r\n        if (!visited[i])\r\n        {\r\n            DFS(i, visited, g);\r\n        }\r\n    }\r\n\r\n    free(visited);\r\n}\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\/\/ BFS\r\n\/\/ There are not any BFS programs based on MGraph in the textbook, \r\n\/\/ so I made it...\r\nvoid BFS(int v, int visited[], mGraph g)\r\n{\r\n    int i;\r\n\r\n    Queue q;\r\n    Create(&q, g.n);\r\n\r\n    visited[v] = 1;\r\n    printf(\"%d \", v);\r\n\r\n    EnQueue(&q, v);\r\n    while (!IsEmpty(&q))\r\n    {\r\n        Front(&q, &v);\r\n        DeQueue(&q);\r\n\r\n        for (i = 0; i < g.n; i++)\r\n        {\r\n            if (g.a[v][i] != 0 && g.a[v][i] != g.noEdge && !visited[i])\r\n            {\r\n                visited[i] = 1;\r\n                printf(\"%d \", i);\r\n                EnQueue(&q, i);\r\n            }\r\n\r\n        }\r\n    }\r\n}\r\n\r\nvoid BFSGraph(mGraph g)\r\n{\r\n    int i;\r\n\r\n    \/\/ Init visited\r\n    int* visited = malloc(g.n * sizeof(int));\r\n    for (i = 0; i < g.n; i++)\r\n        visited[i] = 0;\r\n\r\n    \/\/ Do BFS\r\n    for (i = 0; i < g.n; i++)\r\n    {\r\n        if (!visited[i])\r\n        {\r\n            BFS(i, visited, g);\r\n        }\r\n    }\r\n\r\n    free(visited);\r\n}\r\n\r\n\/\/n is the number of edges\r\nvoid Dijkstra(mGraph g,int n, int start)\r\n{\r\n    int* d = calloc(n, sizeof(int));  \/\/storage the distance\r\n    int* s = calloc(n, sizeof(int));  \/\/record which node has been confirmed\r\n    int minrange =999 ;\r\n    for (int y = 0; y < n; y++)\r\n    {\r\n        d[y] = g.a[start][y];   \/\/initlize the array'd', storage the inital range\r\n    }\r\n    s[start] = 1;\r\n    \/\/Initilize completed\r\n\r\n\r\n\r\n\r\n    for (int y = start; y<n||(y%n < start); y++)\r\n    {\r\n        int temp = -1; minrange = 999;\r\n        for (int u = start; u<n||(u%n < start); u++)    \/\/find the minium and mark\r\n        {\r\n            if (s[u%n] == 0 && d[u%n] < minrange)\r\n            {\r\n                minrange = d[u%n];\r\n                temp = u%n;\r\n            }\r\n        }\r\n        if (temp == -1)\r\n            break;\r\n        s[temp] = 1;   \/\/mark the minium range\r\n        for (int u = start; u < n || (u % n < start) ; u++)\r\n        {\r\n            if (g.a[temp][u%n] + d[temp] < d[u%n] )      \/\/current range plus transfer cost still less than origin distance...\r\n                d[u%n] = g.a[temp][u%n] + d[temp];          \/\/update the range\r\n        }\r\n    }\r\n\r\n\r\n\r\n\r\n    for (int y = 0; y < n; y++) { if (y == start) { ; } else { if (d[y] > 999)\r\n                printf(\"-1\\n\");\r\n            else\r\n                printf(\"%d\\n\", d[y]);\r\n        }\r\n    }\r\n\r\n\r\n    free(d);\r\n    free(s);\r\n}\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\nint main()\r\n{\r\n    mGraph GBA;\r\n    int nSize = 0, edge = 0;\r\n    int start = 0;\r\n    int u = 0, v = 0;\r\n    scanf(\"%d %d %d\", &nSize, &edge, &start);\r\n    Init(&GBA, nSize, 65536);\r\n    for (int a = 0; a < edge; a++)\r\n    {\r\n        scanf(\"%d %d\", &u, &v);\r\n        Insert(&GBA, u, v, 1);\r\n    }\r\n    Dijkstra(GBA, nSize, start);\r\n \r\n    \/\/\u8fd9\u91cc\u9700\u8981\u5bfb\u627e\u6700\u77ed\u8def\u5f84\r\n\r\n    Destroy(&GBA);\r\n\r\n    return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
#include<stdio.h> \/\/ printf() #include<stdlib. […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[17],"tags":[],"_links":{"self":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts\/667"}],"collection":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/comments?post=667"}],"version-history":[{"count":0,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts\/667\/revisions"}],"wp:attachment":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/media?parent=667"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/categories?post=667"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/tags?post=667"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}