标签 算法 下的文章

2017-04-16更新:

void init_prime(int n) //欧拉素数筛法
{
    for(int i = 2; i <= n; i++)
    {
        if(!prime[i])
            prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0] && prime[j] <= n / i; j++)
        {
            prime[prime[j] * i] = 1;
            if(i % prime[j] == 0)
                break;
        }
    }
}

以下是原文

- 阅读剩余部分 -

快速幂：a的b次方对n取余

int ksm(int a, int b, int n)
{
    a %= n;
    int ans = 1;
    while(b)
    {
        if(b%2 == 1)
            ans = ans*a%n;
        b /= 2;
        a = a*a%n;
    }
    return ans;
}

第一次碰到需要剪枝优化的题

题目描述

设有n件工作分配给n个人。为第i个人分配工作j所需的费用为ci 。试设计一个算法，计算最佳工作分配方案，为每一个人都分配1 件不同的工作，并使总费用达到最小。

输入

第一行一个正整数n(1<=n<=20),接下来的n 行，每行n 个数，表示工作费用 。

输出

输出有m行，每行输出最小总费用。

样例输入

5
50 43 1 58 60
87 22 5 62 71
62 98 97 27 38
56 57 96 73 71
92 36 43 27 95

样例输出

144

第一次提交代码：






- 阅读剩余部分 -

转载自ICS161,学英语,自娱自乐

Traversal of graphs and digraphs

To traverse(遍历) means to visit the vertices in some systematic order. You should be familiar with various traversal methods for trees:

preorder: visit each node before its children.
postorder: visit each node after its children.
inorder (for binary trees only): visit left subtree, node, right subtree.

We also saw another kind of traversal, topological ordering(拓扑排序), when I talked about shortest paths.

Today, we'll see two other traversals: breadth first search (BFS) and depth first search (DFS). Both of these construct spanning trees with certain properties useful in other graph algorithms. We'll start by describing them in undirected graphs, but they are both also very useful for directed graphs.



- 阅读剩余部分 -

  1. 1
  2. 2