参考模板


迪杰斯特拉算法与其他相关

struct Edge {
    int from,to,dist;
    Edge(int u,int v,int d):from(u),to(v),dist(w) {}
};

struct HeapNode {
    int d,u;
    bool operator < (const HeapNode &rhs) const {
        return d > rhs.d;
    }
};
struct Dijkstra {
    int n,m;
    vector<Edge> edge;
    vector<int> G[maxn];//保存着边的编号 注意不是节点编号
    bool done[maxn];
    int d[maxn];
    int p[maxn];
    
    void init(int n) {
        this->n = n;
        for(int i = 0; i < n; i++) {
            G[i].clear();
        }
        edge.clear();
    }

    void AddEdge(int from,int to,int dist) {
        edge.push_back(Edge(from,to,dist));
        m = edge.size();
        G[from].push_back(m-1);//不是to?
    }

    void dijkstra(int s) {
        priority_queue<HeapNode> Q;
        for(int i = 0; i < n; i++) {
            d[i] = INF;
        }
        d[s] = 0;
        memset(done,0,sizeof(done));
        Q.push((HeapNode){0,s});//
        while(!Q.empty()) {
            HeapNode x = Q.top(); Q.pop();
            int u = x.u;
            if(done[u]) {
                continue;
            }
            done[u] = true;
            for(int i = 0; i < G[u].size(); i++) {
                Edge &e = edge[G[u][i]];
                if(d[e.to] > d[u]+e.dist) {
                    d[e.to] = d[u]+e.dist;
                    p[e.to] = G[u][i];
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }
};


//Bellman-Ford
bool bellman_ford(int s) {
    queue<int> Q;
    memset(inq,0,sizeof(inq));
    memset(cnt,0,sizeof(cnt));
    for(int i = 0l i < n; i++) {
        d[i] = INF;
    }
    d[s] = 0;
    inq[s] = true;
    Q.push(s);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        inq[u] = false;
        for(int i = 0; i <G[u].size(); i++) {
            Edge &e = edge[G[u][i]];
            if(d[u] < INF && d[e.to] > d[u]+e.dist) {
                d[e.to] = d[u]+e.dist;
                p[e.to] = G[u][i];
                if(!inq[e.to]) {
                    Q.push(e.to);
                    inq[e.to] = true;
                    if(++cnt[e.to] > n) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}


//Floyd : 求两点最短距离 / 传递闭包
for(int k = 0; k < n; k++) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(d[i][j] < INF && d[k][j] < INF) {
                d[i][j] = min(d[i]][j],d[i][k]+d[k][j]);
            }
        }
    }
}

Kruskal

int u[maxn],v[maxn],w[maxn];// 边的两端节点\权
int r[maxn];                //序号
int p[maxn];

int cmp(int i,int j) {
    return w[i] < w[j];
}
int find(int x) {//往祖先方向爬
    return p[x] == x ? x : p[x] = find(p[x]); 
}
int Kruskal() {
    int ans = 0;
    for(int i = 0; i < n; i++) {
        p[i] = i;
    }
    for(int i = 0; i < m; i++) {//edge
        r[i] = i;
    }
    sort(r,r+m,cmp); //r[i] != i
    for(int i = 0; i < m; i++) {
        int e = r[i];//map
        int x = find(u[e]);
        int y = find(v[e]);
        if(x != y) { //not same connected component
            ans += w[e];
            p[x] = y;//union
        }
    }
    return ans;
}

表达式树

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000;
int lch[maxn],rch[maxn];
char op[maxn];
int nc = 0;//node count
int build_tree(char *s,int x,int y){
    int i, c1 = -1, c2 = -1, p = 0;
    int u;
    if(y-x == 1){
        u = ++nc;
        lch[u] = rch[u] = 0;;
        op[u] = s[x];
        return u;
    }
    for(i = x; i < y; i++){
        switch(s[i]){
            case '(':
                p++;
                break;
            case ')':
                p--;
                break;
            case '+': case '-':
                if(!p)
                    c1 = i;
                break;
            case '*': case '/':
                if(!p)
                    c2 = i;
                break;
        }
    }
    if(c1 < 0)
        c1 = c2;
    if(c1 < 0)
        return build_tree(s,x+1,y-1);
    u = ++nc;
    lch[u] = build_tree(s,x,c1);
    rch[u] = build_tree(s,c1+1,y);
    op[u] = s[c1];
    return u;
}

图与有根树

#include<iostream>
#include<vector>
vector<int> G[10000];
vecotr<int> p(10000);
void read_tree(int n){
    int u,v;
    cin >> n;
    int n2 = n-1;//注意-1
    while(n2--){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
}
// parent[root]=-1 dfs(root,-1)
void dfs(int u,int fa){//u为根,fa为u的父节点
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v != fa)
            dfs(v,p[v] = u);//关键是p[v]=u  v为根
    }
}

int main(){
    int n;
    read_tree(n);
    int root; cin >> root;
    p[root] = -1;
    dfs(root,p[root]);
    for(int i = 0; i < n; i++)
        cout << p[i] << " ";
    return 0;
}

关于快速幂
求a^b
令a^b = a^(2^b1+2^b2...+2^bn),其中设b1<b2...<bn
b分解为2^b1+2^b2...+2^bn的时间复杂度即为二进制的宽度O(log b),依次就可以设计出简明的也是最基础的算法

引申出来的快速乘法也差不多个意思,由2^i个数相乘变为2^i个数相加,
具体写成 ab = a∑2^bi
思想还是利用当前计算已知的信息量来加快速度
也可以写成递推式来理解,不过既然可以简单迭代实现就不必写了
注意幺元的区别,a*0≠a
矩阵乘法的快速实现有Strassen算法和Coppersmith-Winograd算法,有空再看
//离题一下,大数乘法有Karatsuba快速相乘算法,放到后面再看

#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 110;
const ll  mmod = 1e9;

ll quick_pow(ll a,ll n,ll mmod){
    ll ans = 1;
    while(n){
        if(n&1) ans = ans*a%mmod; //当2^bi符合n的第i位时计算a^∑2^b(i-1) * a^2^bi
        a = a*a%mmod;             //a是递增的2^bi
        n >>= 1;
    }
    return ans;
}
ll quick_mul(ll a,ll n,ll mmod){
    ll ans = 0;                    //注意快速乘法广义上的幺元是0, a+0 = 0+a = a
    while(n){
        if(n&1) ans = (ans+a)%mmod; 
        a = (a+a)%mmod;             
        n >>= 1;
    }
    return ans;
}

typedef struct matrix{
    int m[maxn][maxn];
}matrix;
matrix unit;//使用前记得初始化
void init(){
    for(int i = 0; i < maxn; i++)
        for(int j = 0; j < maxn; j++)
            unit.m[i][j] = 1;
}
matrix operator *(matrix a,matrix b){         //乞丐版乘法运算
    matrix mat = unit;
    ll x;
    for(int i = 0; i < maxn; i++){
        for(int j = 0; j < maxn; j++){
            x = 0;
            for(int k = 0; k < maxn; k++){
                x += (a.m[i][k]*b.m[k][j])%mmod; //(AB)ij = ∑aik*bkj
            }                                  //预处理求模
            mat.m[i][j] = x%mmod;
        }
    }
    return mat;
}
matrix quick_pow(matrix a,ll n){
    matrix ans = unit;
    while(n){
        if(n&1) ans = ans*a;
        a = a*a;//不需麻烦的求模
        n >>= 1;
    }
    return ans;
}

int main(){
    cout << quick_pow(2,3,555) << endl;
    cout << quick_mul(2,3,555) << endl;
    return 0;
}

别人家的筛选

int prime[50005];

int main(){
    int n; cin >> n;
    int i,j;
    int p = 0;//prime
    prime[p++] = 2;
    for(i = 3; i <= n; i+=2)
        for(j = 0; j < p; j++)
            if(i%prime[j] == 0)
                break;
            else if((long long)prime[j]*prime[j] > i || j == p-1){
                prime[p++] = i;
                break;
            } 
} 
#define RUP(i, a, b) for(int i = (a), i##_end_ = (b); i < i##_end_; ++i)
void Euler(int n, int prime[], int& num)
{
    bool wh[maxn] = {0};
    num = -1;
    RUP(i, 2, n + 1)
    {
        if(!wh[i])    prime[++num] = i;
        RUP(j, 0, num + 1)
        {
            int cur = prime[j] * i;
            if(cur > n)    break;
            wh[cur] = 1;
            if(i % prime[j] == 0)    break; 
        }
    }
    return ;
}

hungry

#include<stdio.h>
#include<string.h>
#define N 505
int link[N],flag[N],map[1005][2],K;
int Find(int x)
{
    int i;
    for(i=0;i<K;i++){
        if(map[i][0]==x&&flag[map[i][1]]==0){
            flag[map[i][1]]=1;                //标记访问过的点,防止出现死循环和重复计算
            if(link[map[i][1]]==0 || Find(link[map[i][1]])==1){
                link[map[i][1]]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int n,m,i,cnt;
    while(scanf("%d",&K),K){
        scanf("%d%d",&n,&m);
        memset(link,0,sizeof(link));        
        for(i=0;i<K;i++){
            scanf("%d%d",&map[i][0],&map[i][1]); //二分图 
        }
        for(i=1,cnt=0;i<=n;i++){           //每个点只需要查找一遍:若从某一点开始找不到增广路,
            memset(flag,0,sizeof(flag));   //则无论当前匹配如何改变都无法再从该点找到增广路
            if(Find(i))
                cnt++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

自己敲的,微改成习惯的风格

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1e3; 
vector<int> G[maxn];
bool check[maxn];
int match[maxn][2];//left0right1
int k,m,n,from,to,cnt;
void init(){
    cnt = 0;
    memset(G,0,sizeof G);
    memset(match,0,sizeof match);
}
bool dfs(int u){
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(check[v]) continue;
        check[v] = 1;
        if(!match[v][1]||dfs(match[v][1])){
            match[u][0] = v;
            match[v][1] = u;
            return true;
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>k&&k){
        cin>>m>>n;
        init();
        for(int i = 0; i < k; i++){
            cin >> from >> to;
            G[from].push_back(to);
        }
        for(int i = 1; i <= m; i++){
            memset(check,0,sizeof check); //NOTE
            if(!match[i][0]&&dfs(i)) cnt++;
        }
        cout << cnt << endl;
    } 
    return 0;
} 

无向二分匹配+判断二分图

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 250;
int n,m,u,v,flag,cnt;
bool check[maxn];
int match[maxn],color[maxn];
vector<int> G[maxn];
int Scan(){ 
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
void init(){
    flag = 0; cnt = 0;
    memset(match,0,sizeof match);
    memset(color,0,sizeof color);
    memset(G,0,sizeof G); 
}
bool go(int u,int c){
    if(color[u]) if(color[u]!=c) return false;
    color[u] = c;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(!color[v]){
            color[v] = -c;
            if(!go(v,-c)) return false;
        }
        else if(color[v]==color[u]){
            return false;
        }
    }
    return true;
}
bool dfs(int u){
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(check[v]) continue;
        check[v] = 1;
        if(!match[v]||dfs(match[v])){
            match[v] = u;
            return true;
        }
    }
    return false;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        init(); 
        for(int i = 0; i < m; i++){
            u = Scan(); v = Scan(); 
            G[u].push_back(v);
            G[v].push_back(u);
        }
        flag = !go(1,1)||n==1;
        if(!flag) for(int i = 1; i <= n; i++){
            memset(check,0,sizeof check);
            if(dfs(i)) cnt++; //!match 
        }
        if(!flag) printf("%d\n",cnt/2);
        else printf("No\n");
    }
    return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

ll add_mod(ll a,ll b,ll mod){    //快乘法 基于快速幂的二分思想 
    ll ans=0;                    //由于考虑到取模数很大 快速幂会溢出 
    while(b){                    //必须使用该方法 
        if(b&1)                    //我这里写的是非递归版 
            ans=(ans+a)%mod;
        a=a*2%mod;
        b>>=1;
    }
    return ans;
}

ll pow_mod(ll a,ll n,ll mod){            //快速幂 递归版 
    if(n>1){                            
        ll tmp=pow_mod(a,n>>1,mod)%mod;
        tmp=add_mod(tmp,tmp,mod);
        if(n&1) tmp=add_mod(tmp,a,mod);
        return tmp;
    }
    return a;
}

bool Miller_Rabbin(ll n,ll a){//米勒拉宾素数判断函数主体
    ll d=n-1,s=0,i;    
    while(!(d&1)){            // 先把(2^s)*d 算出来 
        d>>=1;
        s++;
    }
    ll t=pow_mod(a,d,n);    //a^d取一次余判断 
    if(t==1 || t==-1)        //一或负一则可以声明这可能是质数 
        return 1;
    for(i=0;i<s;i++){                //不是的话继续乘上s个2 
        if(t==n-1)            //(n-1)*(n-1)%n=1 这一步是优化 
            return 1;
        t=add_mod(t,t,n);    // 快乘 
    }
    return 0;
}

bool is_prime(ll n){
    ll i,tab[4]={3,4,7,11};//本来应该取[1,n]内任意整数 
    for(i=0;i<4;i++){                //但一般这几个数足以,不需要太多组测试 
        if(n==tab[i])
            return 1;        //小判断小优化~ 
        if(!n%tab[i])
            return 0;
        if(n>tab[i] && !Miller_Rabbin(n,tab[i]))
            return 0;
    }
    return 1;
}
    
int main(){
    ll n;
    scanf("%lld",&n);
    if(n<2) printf("No");
    else if(n==2) printf("Yes");
    else{
        if(!n%2) printf("No");
        else if(is_prime(n))
            printf("Yes");
        else printf("No");
    }
    return 0;
}

//Miller_Rabbin

以下记录一下平时看到的乱七八糟的笔记


unique()函数是一个去重函数,STL中unique的函数 unique的功能是去除相邻的重复元素(只保留一个)
还有一个容易忽视的特性是它并不真正把重复的元素删除。
eg
int num[100];
unique(num,mun+n)返回的是num去重后的尾地址,之所以说比不真正把重复的元素删除,其实是,该函数把重复的元素一到后面去了,
然后依然保存到了原数组中,然后返回去重后最后一个元素的地址,因为unique去除的是相邻的重复元素,所以一般用之前都会要排一下序。

我们可以证明,最小面积的矩形不但要求四条边上都有一个点,而且还要求至少一条边上有两个或两个以上的点。试想,如果每条边上都只有一个点,则我们总可以把这个矩形旋转一点使得这个矩形变“松”,从而有余地得到更小的矩形。于是我们发现,矩形的某条边的斜率必然与某两点的连线相同。如果我们计算出了所有过两点的直线的倾角,那么α的取值只有可能是这些倾角或它减去90度后的角(直线按“”方向倾斜时)这么C(n,2)种。我们说,这个“倾角”已经被我们 “离散化”了。虽然这个算法仍然有优化的余地,但此时我们已经达到了本文开头所说的目的。

使用STL算法离散化:
思路:先排序,再删除重复元素,然后就是索引元素离散化后对应的值。
假定待离散化的序列为a[n],b[n]是序列a[n]的一个副本,则对应以上三步为:

sort(sub_a,sub_a+n);
int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数
for(i=0;i<n;i++)

a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k为b[i]经离散化后对应的值

对于第3步,若离散化后序列为0, 1, 2, ..., size - 1则用lower_bound,从1, 2, 3, ..., size则用upper_bound,其中lower_bound返回第1个不小于b[i]的值的指针,而upper_bound返回第1个大于b[i]的值的指针,当然在这个题中也可以用lower_bound然后再加1得到与upper_bound相同结果,两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。

设G=(V,E)是一个无向图。如顶点集V可分区为两个互不相交的子集V1,V2之并,并且图中每条边依附的两个顶点都分属于这两个不同的子集。则称图G为二分图。二分图也可记为G=(V1,V2,E)。
给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。选择这样的子集中边数最大的子集称为图的最大匹配问题(maximal matching problem)
图的点覆盖:寻找一个点集,使得图中每一条边至少有一点在该点集中
二分图的最小点覆盖 = 最大匹配
定义:二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。

图的独立集:寻找一个点集,其中任意两点在图中无对应边
一般图的最大独立集是NP完全问题
二分图的最大独立集 = 图的点数-最大匹配

图的路径覆盖:用不相交路径覆盖有向无环图的所有顶点
二分图的最小路径覆盖 = 节点数-最大匹配

最小点覆盖的例子:
http://blog.csdn.net/baidu_23955875/article/details/46573537
因此POJ1325所求的最小reset数就是把所有的边都覆盖所需的最小点数,所以除0外其它直接匈牙利可AC

不错的STL参考
http://blog.csdn.net/tianshuai1111/article/details/7674327

求Fibonacci的后几位可以直接矩阵快速幂取模,那么如果求前几位呢?(若n>1e5 用高精度肯定会炸,魔改高精度我又不会)
http://blog.csdn.net/martinue/article/details/47615005
核心部分

int d;
double len=0.0;
len=log10(1.0/sqrt(5)) +(double)n*log10((1.0+sqrt(5))/2.0);
d=(int)(pow(10,len-(int)len+3));
printf("%d...%04d\n",d,ans_e);//将ans_e用0补齐四位

高精度做不了的事情一般要首先想到log,还有显而易见的公式

二分求等比数列
http://rsylareclipse.blog.163.com/blog/static/185501440201163142628899/
进阶
http://blog.csdn.net/hcbbt/article/details/38377909

A, B, C都是浮点数矩阵 for (i=0; i<N; i++) for (j=0; j<N; j++) for (k=0; k<N; k++) Ci += AiBk;这是个很简单的矩阵乘法算法。但是这么写效率是不高的,原因在于当N很大的时候,比如2048, 4096,会产生cache conflict。要解释这个术语比较麻烦,想知道的话去看computer system: a programmer's perspective那本书的第六章。但是矩阵乘法有别的写法。比如 for (i=0; i<N; i++) for (k=0; k<N; k++) for (j=0; j<N; j++) Ci += AiBk;这种写法交换了k和j的位置,效率应该会比前面那个高些。(术语是loop permutation)还有的写法叫loop tiling,tiling的实质是将大矩阵的乘法变成小的分块矩阵的乘法。就用上一个例子吧。 for(it=0; it<N; it+=T) for(jt=0; jt<N; jt+=T) for(kt=0; kt<N; kt+=T) for(i=it; i<it+T; i++) for(j=jt; j<jt+T; j++) for(k=kt; k<kt+T; k++) Ci += Ai*Bk;其中的T叫tiling size,能整除N。 这样先算小矩阵的话,cache 就能装下参与运算的elements, 对速度提升很大。在实验中有一道题,经过优化之后把运行时间从49秒降到13秒了。

github上的资料:https://github.com/qincaicai/acm

标签: 算法, 学习

添加新评论