黄色日韩网站视频,欧美在线亚洲综合一区,欧美日产在线观看

問題描述及代碼:

  1 /*
  2  * Problem:
  3  * given you the coins, and the total amount of money to change, find a solution
  4  * for this change which minimize the number of coins needed.
  5  *
  6  * Example:
  7  * coins[] = {1, 5, 10, 21, 25};
  8  * money = 19;
  9  * solution[] = {10, 5, 1, 1, 1, 1};
10  *
11  * Points:
12  * Dynamic Programming
13  * Greey Algorithm here is usually uncorrect
14  */
15 #include<stdio.h>
16 #include<stdlib.h>
17 #include<string.h>
18 #define MAX_COINS 10
19 #define MAX_MONEY 32767
20 #define INF 0x7FFFFFFF
21 int coins_num, coins[MAX_COINS];
22 int total, changes_num[MAX_MONEY], changes[MAX_MONEY];
23
24 int
25 is_continue()
26 {
27     char ch[2];
28     while(1) {
29         printf("Are you gonna continue this game(Y if yes, or N)?\n");
30         scanf("%s", ch);
31         if(ch[0] == 'Y' || ch[0] == 'y')
32             return 1;
33         else if(ch[0] == 'N' || ch[0] == 'n')
34             return 0;
35     }
36 }
37
38 void
39 input()
40 {
41     int i;
42     printf("Enter the number of coins: ");
43     scanf("%d", &coins_num);
44     printf("Enter the amount of coins(ascending order, separated by space): \n");
45     for(i=0; i<coins_num; i++)
46         scanf("%d", coins+i);
47     printf("Enter the amount of money to change: ");
48     scanf("%d", &total);
49 }
50
51 void
52 output()
53 {
54     int i, tmp;
55     printf("Solution: \n");
56     printf("Minimum number of coins needed: %d\n", changes_num[total]);
57     printf("Coins: \n");
58     tmp = total;
59     while(tmp > 0) {
60         printf("%d ", changes[tmp]);
61         tmp -= changes[tmp];
62     }
63     printf("\n");
64 }
65
66 /*
67  * Dynamic Programming: f(m) = min (f[m-coins[i] + 1)
68  * O(N*K), N is the number of coins, K is the total amount of money to change
69  */
70 void
71 solve()
72 {
73     int i, j, k, min;
74     changes_num[0] = 0;
75     for(i=1; i<=total; i++) { /* Money: from '1' to 'total' */
76         min = INF;
77         k = -1;
78         for(j=0; j<coins_num; j++) { /* Coins: ascending, and always contains '1' */
79             if(i >= coins[j]) {
80                 if(min > changes_num[i-coins[j]]+1) {
81                     min = changes_num[i-coins[j]]+1;
82                     k = j;
83                 }
84             } else
85                 continue;
86         }
87         changes_num[i] = min;
88         changes[i] = coins[k];
89     }
90 }
91
92 int
93 main(int argc, char **argv)
94 {
95     while(is_continue()) {
96         input();
97         solve();
98         output();
99     }
100 }

posted @ 2010-09-29 14:18 simplyzhao 閱讀(793) | 評論 (0) | 編輯收藏

USACO Barn Repair

問題:
http://ace.delos.com/usacoprob2?a=KIjVa3gj0ap&S=barn1

思路:
簡單的貪心算法
一直不敢怎么用貪心算法(這題比較好理解)，因為不知道該如何證明其正確性
如何保證每次選擇當前最優解最后可以得到整體的最優解？

對于該題:
假設存在M塊boards，那么從最左端到最右端(指存在cow的stall)可以存在M-1處gap
最優子結構:
設f(x)表示存在x塊boards時的the minimum number of stalls that must be blocked，那么
f(x) = min(f(x-1) + gap[i] that hasn't been selected)
貪心選擇性質: 每次從尚未選擇過的gaps中選擇最大的gap即可得到最優解(假設為gap[x1], gap[x2], ...gap[x(M-1)])
證明(反證):
假設存在一個最優解，其不包含gap[x(i)]
那么，采用cut-and-paste方法即可證明其不是最優解

代碼:

1 /*
2 ID: simplyz2
3 LANG: C
4 TASK: barn1
5 */
6 #include<stdio.h>
7 #include<stdlib.h>
8 #include<string.h>
9 #define MAX_LEN 205
10 #define Min(a,b) ((a)<(b) ? (a) : (b))
11 int M, S, C;
12 int rt, stalls[MAX_LEN], diff[MAX_LEN];
13
14 int
15 asc_cmp(const void *arg1, const void *arg2)
16 {
17     return (*(int *)arg1) - (*(int *)arg2);
18 }
19
20 int
21 desc_cmp(const void *arg1, const void *arg2)
22 {
23     return (*(int *)arg2) - (*(int *)arg1);
24 }
25
26 void
27 init()
28 {
29     int i;
30     for(i=0; i<C; i++)
31         scanf("%d", stalls+i);
32     qsort(stalls, C, sizeof(int), asc_cmp);
33     rt = stalls[C-1] - stalls[0] + 1;
34     for(i=1; i<C; i++)
35         diff[i-1] = stalls[i] - stalls[i-1] - 1;
36     qsort(diff, C-1, sizeof(int), desc_cmp);
37 }
38
39 void
40 solve()
41 {
42     int i, up;
43     up = Min(C-1, M-1);
44     for(i=0; i<up; i++)
45         rt -= diff[i];
46     printf("%d\n", rt);
47 }
48
49 int
50 main(int argc, char **argv)
51 {
52     freopen("barn1.in", "r", stdin);
53     freopen("barn1.out", "w", stdout);
54     while(scanf("%d %d %d", &M, &S, &C) != EOF) {
55         init();
56         solve();
57     }
58     return 0;
59 }

posted @ 2010-09-29 10:49 simplyzhao 閱讀(269) | 評論 (0) | 編輯收藏

USACO Milking Cows

問題:
http://ace.delos.com/usacoprob2?a=sAaEFWx5xo1&S=milk2

思路:
如果想通了，該題還是挺簡單的
首先按照開始時間進行排序，然后依次查看相鄰時間段是否可以合并
針對合并后的時間段，很容易即可求出解

代碼:

1 /*
2 ID: simplyz2
3 LANG: C
4 TASK: milk2
5 */
6 #include<stdio.h>
7 #include<stdlib.h>
8 #include<string.h>
9 #define MAX_LEN 5001
10 #define Max(a,b) ((a)>(b) ? (a) : (b))
11 struct Intv {
12     int begin, end;
13 } intvs[MAX_LEN], merge[MAX_LEN];
14 int num, m_num;
15
16 int
17 compare(const void *arg1, const void *arg2)
18 {
19     return (((struct Intv *)arg1)->begin - ((struct Intv *)arg2)->begin);
20 }
21
22 void
23 merge_intv()
24 {
25     int i;
26     m_num = 0;
27     qsort(intvs, num, sizeof(struct Intv), compare);
28     merge[m_num] = intvs[0];
29     for(i=1; i<num; i++) {
30         if(intvs[i].begin > merge[m_num].end)
31             merge[++m_num] = intvs[i];
32         else if(intvs[i].end > merge[m_num].end)
33             merge[m_num].end = intvs[i].end;
34     }
35 }
36
37 void
38 solve()
39 {
40     int i, rt_a, rt_b;
41     rt_a = rt_b = 0;
42     for(i=0; i<=m_num; i++) {
43         rt_a = Max(rt_a, merge[i].end - merge[i].begin);
44         if(i)
45             rt_b = Max(rt_b, merge[i].begin - merge[i-1].end);
46     }
47     printf("%d %d\n", rt_a, rt_b);
48 }
49
50 int
51 main(int argc, char **argv)
52 {
53     int i;
54     freopen("milk2.in", "r", stdin);
55     freopen("milk2.out", "w", stdout);
56     while(scanf("%d", &num) != EOF) {
57         for(i=0; i<num; i++)
58             scanf("%d %d", &intvs[i].begin, &intvs[i].end);
59         merge_intv();
60         solve();
61     }
62     return 0;
63 }

posted @ 2010-09-27 15:01 simplyzhao 閱讀(271) | 評論 (0) | 編輯收藏

USACO Broken Necklace

問題:
http://ace.delos.com/usacoprob2?a=sAaEFWx5xo1&S=beads

思路:
如果純粹枚舉的話，代碼還是挺簡單的（關鍵是將循環結構巧妙地用線性結構表示: s -> ss）
枚舉的復雜度很容易地看出是O(n*n)，對于本題，還是沒問題的

官方給出的Analysis中，提供了一種O(n)的動態規劃的解法，卻始終想不明白，艾...
有時間再繼續思考

posted @ 2010-09-27 14:58 simplyzhao 閱讀(246) | 評論 (0) | 編輯收藏

PKU 1273 Drainage Ditches

問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1273

思路:
第一道最大流，Edmonds-Karp算法
參考了別人的代碼，其實自己也能寫出來，不過肯定沒有這么精致(*^__^*) 嘻嘻……
從別人的代碼里學到很多，例如：
一條路徑只需要pre[]數組進行保存即可，路徑的殘留容量也可以邊擴展(BFS)邊記錄，還有代碼居然就只需要一個殘留網絡的二維數組

代碼:

1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_M 201
5 #define INF 0x7FFFFFFF
6 #define Min(a,b) ((a)<(b) ? (a) : (b))
7 int n, m, source, sink;
8 int pre[MAX_M]; /* excellent for path recording */
9 int flow[MAX_M];
10 int residual[MAX_M][MAX_M]; /* only need this matrix */
11 int queue[MAX_M];
12
13 int
14 bfs() /* operation on the residual network */
15 {
16     int i, head, tail, cur;
17     head = -1;
18     tail = 0;
19     memset(pre, -1, sizeof(pre));
20     for(i=1; i<=m; i++)
21         flow[i] = INF;
22     queue[tail] = source;
23     pre[source] = 0;
24     while(head < tail) {
25         ++head;
26         cur = queue[head];
27         if(cur == sink)
28             return flow[sink];
29         for(i=1; i<=m; i++) {
30             if(pre[i]!=-1 || !residual[cur][i])
31                 continue;
32             pre[i] = cur;
33             flow[i] = Min(flow[cur], residual[cur][i]);
34             ++tail;
35             queue[tail] = i;
36         }
37     }
38     return -1;
39 }
40
41 int
42 edmonds_karp()
43 {
44     int tmp, next, cur, rt = 0;
45     while(1) {
46         tmp = bfs();
47         if(tmp == -1) /* there's no argment path */
48             return rt;
49         rt += tmp;
50         cur = sink;
51         while(cur != source) {
52             next = cur;
53             cur = pre[cur];
54             residual[cur][next] -= tmp;
55             residual[next][cur] += tmp;
56         }
57     }
58 }
59
60 int
61 main(int argc, char **argv)
62 {
63     int i, f, t, c, ans;
64     while(scanf("%d %d", &n, &m) != EOF) {
65         memset(residual, 0, sizeof(residual));
66         for(i=1; i<=n; i++) {
67             scanf("%d %d %d", &f, &t, &c);
68             residual[f][t] += c; /* Attention: multiple lines */
69         }
70         source = 1;
71         sink = m;
72         ans = edmonds_karp();
73         printf("%d\n", ans);
74     }
75 }

posted @ 2010-09-16 21:10 simplyzhao 閱讀(208) | 評論 (0) | 編輯收藏

PKU 2777 Count Color

問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2777

思路:
線段樹的典型題

參考:
http://blog.csdn.net/xiaofengsheng/archive/2009/03/03/3953265.aspx

代碼:

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 #define MAX_N 100001
  5 #define MAX_T 31
  6 #define LEFT(i) (i<<1)
  7 #define RIGHT(i) ((i<<1)+1)
  8 int L, T, O;
  9 struct Node {
10     int left, right;
11     int color;
12 };
13 struct Node nodes[MAX_N*3];
14 int rt, visited[MAX_T];
15
16 void
17 build(int begin, int end, int step)
18 {
19     int mid;
20     nodes[step].left = begin;
21     nodes[step].right = end;
22     nodes[step].color = 1;
23     if(begin == end)
24         return;
25     mid = (begin+end)>>1;
26     build(begin, mid, LEFT(step));
27     build(mid+1, end, RIGHT(step));
28 }
29
30 void
31 insert(int begin, int end, int color, int step)
32 {
33     int mid;
34     if(nodes[step].left==begin && nodes[step].right==end) {
35         nodes[step].color = color;
36         return;
37     };
38     if(nodes[step].color != -1) {
39         nodes[LEFT(step)].color = nodes[RIGHT(step)].color = nodes[step].color;
40         nodes[step].color = -1; /* mixed color */
41     }
42     mid = (nodes[step].left+nodes[step].right)>>1;
43     if(begin > mid)
44         insert(begin, end, color, RIGHT(step));
45     else if(end<=mid)
46         insert(begin, end, color, LEFT(step));
47     else {
48         insert(begin, mid, color, LEFT(step));
49         insert(mid+1, end, color, RIGHT(step));
50     }
51 }
52
53 void
54 calculate(int begin, int end, int step)
55 {
56     if(nodes[step].color != -1) {
57         if(!visited[nodes[step].color]) {
58             visited[nodes[step].color] = 1;
59             ++rt;
60         }
61         return;
62     }
63     int mid = (nodes[step].left+nodes[step].right)>>1;
64     if(mid < begin)
65         calculate(begin, end, RIGHT(step));
66     else if(mid >= end)
67         calculate(begin, end, LEFT(step));
68     else {
69         calculate(begin, mid, LEFT(step));
70         calculate(mid+1, end, RIGHT(step));
71     }
72 }
73
74 int
75 main(int argc, char **argv)
76 {
77     int i, a, b, c;
78     char ops[2];
79     while(scanf("%d %d %d", &L, &T, &O) != EOF) {
80         build(1, L, 1);
81         for(i=1; i<=O; i++) {
82             scanf("%s", ops);
83             if(ops[0] == 'C') {
84                 scanf("%d %d %d", &a, &b, &c);
85                 if(a <= b)
86                     insert(a, b, c, 1);
87                 else
88                     insert(b, a, c, 1);
89             } else if(ops[0] == 'P') {
90                 scanf("%d %d", &a, &b);
91                 rt = 0;
92                 memset(visited, 0, sizeof(visited));
93                 if(a <= b)
94                     calculate(a, b, 1);
95                 else
96                     calculate(b, a, 1);
97                 printf("%d\n", rt);
98             }
99         }
100     }
101 }

posted @ 2010-09-16 10:57 simplyzhao 閱讀(270) | 評論 (0) | 編輯收藏

[zz] 線段樹(2)

摘要: 從簡單說起，線段樹其實可以理解成一種特殊的二叉樹。但是這種二叉樹較為平衡，和靜態二叉樹一樣，都是提前已經建立好的樹形結構。針對性強，所以效率要高。這里又想到了一句題外話：動態和靜態的差別。動態結構較為靈活，但是速度較慢；靜態結構節省內存，速度較快。接著回到線段樹上來，線段樹是建立在線段的基礎上，每個結點都代表了一條線段[a , b]。長度為1的線段成為元線段。非元線段都有兩個子結點，左結點代表的線... 閱讀全文

posted @ 2010-09-15 18:49 simplyzhao 閱讀(221) | 評論 (0) | 編輯收藏

[zz] 線段樹(1)

好久沒寫過算法了，添一個吧，寫一個線段樹的入門知識，比較大眾化。

上次在湖大，其中的一道題數據很強，我試了好多種優化都TLE，相信只能用線段樹才能過?；貋碇蟀蛋涤謱W了一次線段樹，想想好像是第三次學了，像網絡流一樣每學一次都有新的體會。

把問題簡化一下：

在自然數，且所有的數不大于30000的范圍內討論一個問題：現在已知n條線段，把端點依次輸入告訴你，然后有m個詢問，每個詢問輸入一個點，要求這個點在多少條線段上出現過；

最基本的解法當然就是讀一個點，就把所有線段比一下，看看在不在線段中；

每次詢問都要把n條線段查一次，那么m次詢問，就要運算m*n次，復雜度就是O(m*n)

這道題m和n都是30000，那么計算量達到了10^9；而計算機1秒的計算量大約是10^8的數量級，所以這種方法無論怎么優化都是超時

-----

因為n條線段是固定的，所以某種程度上說每次都把n條線段查一遍有大量的重復和浪費；

線段樹就是可以解決這類問題的數據結構

舉例說明：已知線段[2,5] [4,6] [0,7]；求點2,4,7分別出現了多少次

在[0,7]區間上建立一棵滿二叉樹：（為了和已知線段區別，用【】表示線段樹中的線段）

                                               【0,7】
                               /                                            \
                     【0,3】                                           【4,7】
                  /               \                                    /                \
       【0,1】             【2,3】                     【4,5】               【6,7】
         /      \                 /      \                     /      \                   /      \
【0,0】【1,1】    【2,2】【3,3】   【4,4】【5,5】       【6,6】【7,7】

每個節點用結構體：

struct line
{
int left,right;//左端點、右端點
int n;//記錄這條線段出現了多少次，默認為0
}a[16];

和堆類似，滿二叉樹的性質決定a[i]的左兒子是a[2*i]、右兒子是a[2*i+1];

然后對于已知的線段依次進行插入操作：

從樹根開始調用遞歸函數insert

void insert(int s,int t,int step)//要插入的線段的左端點和右端點、以及當前線段樹中的某條線段
{
      if (s==a[step].left && t==a[step].right)
      {
            a[step].n++;//插入的線段匹配則此條線段的記錄+1
            return;//插入結束返回
      }
      if (a[step].left==a[step].right)   return;//當前線段樹的線段沒有兒子，插入結束返回
      int mid=(a[step].left+a[step].right)/2;
      if (mid>=t)    insert(s,t,step*2);//如果中點在t的右邊，則應該插入到左兒子
      else if (mid<s)    insert(s,t,step*2+1);//如果中點在s的左邊，則應該插入到右兒子
      else//否則，中點一定在s和t之間，把待插線段分成兩半分別插到左右兒子里面
      {
            insert(s,mid,step*2);
            insert(mid+1,t,step*2+1);
      }
}

三條已知線段插入過程：

[2,5]

--[2,5]與【0,7】比較，分成兩部分：[2,3]插到左兒子【0,3】，[4,5]插到右兒子【4,7】

--[2,3]與【0,3】比較，插到右兒子【2,3】；[4,5]和【4,7】比較，插到左兒子【4,5】

--[2,3]與【2,3】匹配，【2,3】記錄+1；[4,5]與【4,5】匹配，【4,5】記錄+1

[4,6]

--[4,6]與【0,7】比較，插到右兒子【4,7】

--[4,6]與【4,7】比較，分成兩部分，[4,5]插到左兒子【4,5】；[6,6]插到右兒子【6,7】

--[4,5]與【4,5】匹配，【4,5】記錄+1；[6,6]與【6,7】比較，插到左兒子【6,6】

--[6,6]與【6,6】匹配，【6,6】記錄+1

[0,7]

--[0,7]與【0,7】匹配，【0,7】記錄+1

插入過程結束，線段樹上的記錄如下（紅色數字為每條線段的記錄n）：

                                               【0,7】
                                                    1
                               /                                             \
                     【0,3】                                             【4,7】
                         0                                                     0
                 /                 \                                     /                 \
       【0,1】                 【2,3】                【4,5】                  【6,7】
            0                           1                          2                         0
          /    \                      /      \                     /     \                    /      \
【0,0】【1,1】       【2,2】   【3,3】       【4,4】【5,5】     【6,6】【7,7】
     0            0            0            0            0            0           1           0

詢問操作和插入操作類似，也是遞歸過程，略

2——依次把【0,7】【0,3】【2,3】【2,2】的記錄n加起來，結果為2

4——依次把【0,7】【4,7】【4,5】【4,4】的記錄n加起來，結果為3

7——依次把【0,7】【4,7】【6,7】【7,7】的記錄n加起來，結果為1

不管是插入操作還是查詢操作，每次操作的執行次數僅為樹的深度——logN

建樹有n次插入操作，n*logN，一次查詢要logN，m次就是m*logN；總共復雜度O(n+m)*logN，這道題N不超過30000，logN約等于14，所以計算量在10^5～10^6之間，比普通方法快了1000倍；

這道題是線段樹最基本的操作，只用到了插入和查找；刪除操作和插入類似，擴展功能的還有測度、連續段數等等，在N數據范圍很大的時候，依然可以用離散化的方法建樹。

湖大的那道題目繞了個小彎子，alpc12有詳細的題目和解題報告，有興趣的話可以看看http://www.shnenglu.com/sicheng/archive/2008/01/09/40791.html

線段樹的經典題目就是poj1177的picturehttp://acm.pku.edu.cn/JudgeOnline/problem?id=1177

posted @ 2010-09-15 18:46 simplyzhao 閱讀(257) | 評論 (0) | 編輯收藏

PKU 1456 Supermarket

問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1456

思路:
這題就是個悲劇...
都說這題是貪心，還有并查集的優化，不過我對于貪心一直不敢用，因為不知道為什么可以貪心
然后，那就動態規劃吧，結果，徹底受打擊了，對于動態規劃還是沒掌握啊...

其實，用value[i][j]來表示前i件product到時刻j為止所得到的最大profit
value[i][j] = max (value[i-1][j], value[i-1][j-1]+profit[i])
跟01背包的形式是一樣的，所以就可以用滾動數組進行空間優化

代碼:

1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 10001
5 #define Max(a,b) ((a)<(b)?(b):(a))
6 struct Prod {
7     int profit;
8     int deadline;
9 } prods[MAX_N];
10 int n, upper, value[MAX_N];
11
12 int
13 compare(const void *arg1, const void *arg2) /* ascend order: deadline */
14 {
15     struct Prod *a = (struct Prod *)arg1;
16     struct Prod *b = (struct Prod *)arg2;
17     return a->deadline-b->deadline;
18 }
19
20 void
21 init()
22 {
23     int i;
24     for(i=0; i<n; i++)
25         scanf("%d %d", &prods[i].profit, &prods[i].deadline);
26     qsort(prods, n, sizeof(struct Prod), compare);
27     upper = prods[n-1].deadline;
28 }
29
30 void
31 solve()
32 {
33     int i, j;
34     memset(value, 0, sizeof(value));
35     for(i=0; i<n; i++) {
36         for(j=prods[i].deadline; j>=1; j--)
37             value[j] = Max(value[j], value[j-1]+prods[i].profit);
38         for(j=prods[i].deadline+1; j<=upper; j++)
39             value[j] = Max(value[prods[i].deadline], value[j]);
40     }
41     printf("%d\n", value[upper]);
42 }
43
44 int
45 main(int argc, char **argv)
46 {
47     while(scanf("%d", &n) != EOF) {
48         init();
49         solve();
50     }
51 }

posted @ 2010-09-15 16:25 simplyzhao 閱讀(225) | 評論 (0) | 編輯收藏

PKU 1270 Following Orders

問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1270

思路:
拓撲排序適合于描述事件發生的先后次序
這題，對于a>b這樣的題目要求，就非常適合用拓撲排序來進行

一次AC，寫的過程還接了個女朋友的電話，跟同學聊了會天，o(∩_∩)o...哈哈

代碼:

1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define STR_LEN 207
5 #define MAX_N 26
6 int adj[MAX_N][MAX_N], in_dgr[MAX_N];
7 int visited[MAX_N];
8 int total, ch[MAX_N];
9 char ans[MAX_N];
10
11 int
12 init()
13 {
14     int i, f, t, len;
15     char str[STR_LEN];
16     total = 0;
17     memset(ch, 0, sizeof(ch));
18     memset(in_dgr, 0, sizeof(in_dgr));
19     memset(adj, 0, sizeof(adj));
20     memset(visited, 0, sizeof(visited));
21     memset(ans, 0, sizeof(ans));
22     if(fgets(str, STR_LEN, stdin) == NULL)
23         return 0;
24     len = strlen(str);
25     for(i=0; i<len; i+=2) {
26         if(str[i]>='a' && str[i]<='z') {
27             ++total;
28             ++ch[str[i]-'a'];
29         }
30     }
31     fgets(str, STR_LEN, stdin);
32     len = strlen(str);
33     for(i=0; i<len; i+=2) {
34         if((i>>1)%2 == 0)
35             f = str[i]-'a';
36         else {
37             t = str[i]-'a';
38             adj[f][t] = 1;
39             ++in_dgr[t];
40         }
41     }
42     return 1;
43 }
44
45 void
46 topo_sort(int depth)
47 {
48     int i, j;
49     if(depth == total) {
50         printf("%s\n", ans);
51         return;
52     }
53     for(i=0; i<MAX_N; i++) {
54         if(ch[i] && !visited[i] && !in_dgr[i]) {
55             visited[i] = 1;
56             ans[depth] = 'a'+i;
57             for(j=0; j<MAX_N; j++)
58                 if(adj[i][j])
59                     --in_dgr[j];
60             topo_sort(depth+1);
61             visited[i] = 0;
62             for(j=0; j<MAX_N; j++)
63                 if(adj[i][j])
64                     ++in_dgr[j];
65         }
66     }
67 }
68
69 int
70 main(int argc, char **argv)
71 {
72     while(init()) {
73         topo_sort(0);
74         printf("\n");
75     }
76 }

posted @ 2010-09-14 20:00 simplyzhao 閱讀(201) | 評論 (0) | 編輯收藏

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

A Za, A Za, Fighting...

導航

統計

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜