nyoj38 布线问题(最小生成树)

最小生成树算法有两个比较出名的，就是prime算法和krakusl算法。
首先说下krakusl算法。这个算法就是三个步骤，
第一，把每个顶点看成一个集合，边集按照权值大小排序。
第二，从最小的边集开始，如果边的加入没有使得生成树成为环（并查集），则把该边加入生成树，否则，判断下一条边。
第三，当所有的顶点都加入了生成树，则所有加入的边构成最小生成树。
更加详细的请查找百度百科。
下面是我写的此题的代码。

#include<stdio.h>  
#include<stdlib.h>  
#include<limits.h>  
#include<string.h>  
#include<algorithm>  
#define min(a,b) a>b?b:a  
using namespace std;  
int L[502];  
int father[502];  
struct P{  
    int val;  
    int v1,v2;  
}a[130000];  
void work();  
int v,e;  
int sum;  
int comp(const void *a,const void *b)  
{  
    P *c=(P *)a;  
    P *d=(P *)b;  
    return c->val-d->val;  
}  
int main()  
{  
    int T;    
    int i;  
    scanf("%d",&T);  
    while(T--)  
    {  
        memset(father,0,sizeof(father));  
        scanf("%d%d",&v,&e);  
        for(i=0;i<e;i++)  
            scanf("%d %d %d",&a[i].v2,&a[i].v1,&a[i].val);  
        for(i=0;i<v;i++)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
            scanf("%d",&L[i]);  
        sum=0;  
        qsort(a,e,sizeof(a[0]),comp);  
        work();  
        printf("%d\n",sum+*min_element(L,L+v));  
          
    }  
    return 0;  
}  
int find(int x)//并查集函数  
{  
    if(x!=father[x]) father[x]=find(father[x]);  
    return father[x];  
}  
void work()//kruskal算法  
{  
    int i;  
    for(i=1;i<=v;i++)  
        father[i]=i;  
    for(i=0;i<e;i++)  
    {  
        int t=find(a[i].v1);  
        int tt=find(a[i].v2);  
        if(t!=tt)  
        {  
            sum+=a[i].val;  
            father[t]=tt;  
        }  
    }     
}

这个算法也不是很理解，但是pime算法我也不太清楚，我写不出来，所以要想了解此算法，请移步此处。

2014-10-29

nyoj123 士兵杀敌-四(树状数组)

这题真的是出乎我的意料，我一直以为是线段树，没想到还是树状数组。我是在网上看的思路，然后自己编代码。

#include<stdio.h>  
int N;  
int c[1000005];  
int lowbit(int i)  
{  
    return i&(-i);  
}  
void updata(int i,int num)  
{  
    while(i<=N)  
    {  
        c[i]+=num;  
        i+=lowbit(i);  
    }  
  
}  
int S(int i)  
{  
    int sum=0;  
    while(i>0)  
    {  
        sum+=c[i];  
        i-=lowbit(i);  
    }  
    return sum;  
}  
  
int main()  
{  
    int T;  
    int i;  
    int num,b,e;  
    scanf("%d%d",&T,&N);  
    char s[10];  
    while(T--)  
    {  
        scanf("%s",s);  
        if(s[0]=='A')  
        {  
            scanf("%d%d%d",&b,&e,&num);  
            updata(b,num);  
            updata(e+1,-num);///////只有这里变一下，然后就和三一样了。太，，，，，，，，，，，，，  
        }  
        else  
        {  
            scanf("%d",&i);  
            printf("%d\n",S(i));  
        }  
    }  
    return 0;  
  
}

这个就不多解释了，会树状数组就会懂。这题放了好多天，今天终于ac了。

2014-10-28

nyoj290 动物统计

#include<stdio.h>  
#include<string.h>  
struct Tire{  
    int count;  
    Tire *next[26];  
};  
Tire *root;  
int Max;  
char Maxs[11];  
char ss[11];  
void insert(char *s)  
{  
    if(root==NULL || *s=='\0')  
        return ;  
    Tire *p=root;  
    int i;  
    int n;  
    while(*s!='\0')  
    {  
        n=*s-'a';  
        if(p->next[n]==NULL)  
        {  
            Tire *temp=new Tire;  
            for(i=0;i<26;i++)  
                temp->next[i]=NULL;  
            temp->count=0;  
            p->next[n]=temp;  
        }  
        p=p->next[n];  
        s++;  
    }  
    p->count++;  
    if(p->count>Max){ Max=p->count; strcpy(Maxs,ss);}  
}  
int main()  
{  
    int N;  
    int i;  
    while(~scanf("%d",&N))  
    {  
        root=new Tire;  
        for(i=0;i<26;i++)  
            root->next[i]=NULL;  
        root->count=0;  
        Max=0;  
        while(N--)  
        {  
            scanf("%s",ss);  
            insert(ss);  
        }  
        printf("%s %d\n",Maxs,Max);  
    }  
    return 0;  
  
}

我觉得这题应该可以用哈希表做，但是我没试验过，不知道可不可以过，不过你们可以试试。

2014-10-27

nyoj685 查找字符串(字典树)

刚学的字典树就用上了。

#include<stdio.h>//685查找字符串  
struct Trie{  
    int count;  
    Trie *next[30];  
};  
Trie *root;;  
int turn(char c)//把字符转换成数组序号  
{  
    if(c>='a' && c<='z')  
        return c-'a';  
    else if(c=='@')  
        return 26;//@  
    else   
        return 27;//  +  
}  
void insert(char *s)//插入一个字符串  
{  
    if(root==NULL || *s=='\0')  
        return ;  
    int i;  
    Trie *p=root;  
    while(*s!='\0')  
    {  
        if(p->next[turn(*s)]==NULL)//字符串不存在，则创建  
        {  
            Trie *temp=new Trie;  
            for(i=0;i<30;i++)  
                temp->next[i]=NULL;  
            temp->count=0;//付初值0  
            p->next[turn(*s)]=temp;  
        }  
        p=p->next[turn(*s)];  
        s++;  
    }  
    p->count++;  
}  
int Tfind(char *s)  
{  
    Trie *p=root;  
    while(p!=NULL && *s!='\0')  
    {  
        p=p->next[turn(*s)];  
        s++;  
    }  
    return p==NULL?0:p->count;//注意如果字符串不存在也是0；不存在时候p==NULL  
}  
void del(Trie *p)//删除，oj提交的时候建议不删除，因为这个也耗时间。系统自动会回收，但是自己写的时候要注意。  
{  
    int i;  
    for(i=0;i<30;i++)  
    {  
        if(p->next[i]!=NULL)  
            del(p->next[i]);  
    }  
    delete p;  
}  
int main()  
{  
    int T;  
    int n,m;  
    int i;  
    char s[20];  
    scanf("%d",&T);  
    getchar();  
    while(T--)  
    {  
        root=new Trie;  
        for(i=0;i<30;i++)  
            root->next[i]=NULL;  
        root->count=0;  
        scanf("%d%d",&n,&m);  
        for(i=0;i<n;i++)  
        {  
            scanf("%s",s);  
            insert(s);  
        }  
        while(m--)  
        {  
            scanf("%s",s);  
            printf("%d\n",Tfind(s));  
        }  
        del(root);  
    }  
    return 0;  
}

2014-10-25

线段树算法(数组和链表两种实现)

虽然oj上超时了吧，那是因为需要优化，暂时没想到怎么优化，但是我学会了线段树，值得纪念一下。

#include<stdio.h>  
#define N 1000005  
struct Node{  
    int left,right;  
    int val;  
}c[N*4+5];  
int father[N+5];  
int n;  
void build(int i,int l,int r)//建立一个以i为祖先的线段树  
{  
    c[i].left=l;  
    c[i].right=r;  
    c[i].val=0;  
    if(l==r)  
    {  
        father[l]=i;  
        return ;  
    }  
    else  
    {  
        build(i*2  ,    l     ,  (l+r)/2 );  
        build(i*2+1, (l+r)/2+1,    r     );  
    }  
}  
void insert(int l,int r,int num,int i)  
{  
    if(l<=c[i].left && c[i].right<=r)  
        c[i].val+=num;  
    if(c[i].left==c[i].right)  
        return ;  
    if(l<=(c[i].left+c[i].right)/2) insert(l,r,num,i*2);  
    if(r>(c[i].left+c[i].right)/2) insert(l,r,num,i*2+1);  
}  
int main()  
{  
    int T,M;  
    int num,l,r;  
    scanf("%d%d",&T,&M);  
    build(1,1,M);  
    char s[15];  
    while(T--)  
    {  
        scanf("%s",s);  
        if(s[0]=='A')  
        {  
            scanf("%d %d %d",&l,&r,&num);  
            insert(l,r,num,1);    
        }  
        else  
        {  
            scanf("%d",&n);  
            printf("%d\n",c[father[n]].val);  
        }  
  
    }  
    return 0;  
}

这是南阳oj上第123题，超时。大家不要抄啊，自己看看如何优化吧，。我也正在想。会了在发一篇博客讲解一下。

#include<cstdio>  
#include<iostream>  
//#define N 1000002  
using namespace std;  
struct Node{  
    int left,right;  
    Node *leftchild,*rightchild;  
    int cover;  
};  
Node *Root;  
int n;  
Node* build(int l,int r)  
{  
    Node *root=new Node;  
    root->left=l;  
    root->right=r;  
    root->leftchild=NULL;  
    root->rightchild=NULL;  
    root->cover=0;  
    if(l<r)  
    {  
        int mid=(r+l)>>1;  
        root->leftchild = build(l,mid);  
        root->rightchild= build(mid+1,r);  
    }  
    return root;  
}  
void insert(int l,int r,int num,Node *root)  
{  
    if(root==NULL)  
        return ;  
    if(l<=root->left && root->right<=r)  
        root->cover+=num;  
    if(l<=(root->left+root->right)/2) insert(l,r,num,root->leftchild);  
    if(r>(root->left+root->right)/2) insert(l,r,num,root->rightchild);  
  
  
}  
int f(int l,int r,Node *root)  
{  
    if(root->left==n && root->right==n)  
        return root->cover;  
    else  
    {  
        int mid=(l+r)>>1;  
        if(n<=mid) f(l,mid,root->leftchild);  
        else f(mid+1,r,root->rightchild);  
    }  
  
}  
/*  
void print(Node *p)  
{  
    if(p->leftchild==NULL)   
    {  
        printf("[%d %d]->[%d] \n",p->left,p->right,p->cover);  
          
    }  
    else{  
    print(p->leftchild);  
    print(p->rightchild);  
    }  
}*/  
int main()  
{  
    int num,l,r;  
    int T,M;  
    char s[15];  
      
    scanf("%d %d",&T,&M);     
    Root=build(1,M+2);  
    while(T--)  
    {  
        scanf("%s",s);  
        if(s[0]=='A')  
        {  
            scanf("%d %d %d",&l,&r,&num);  
            insert(l,r,num,Root);  
        }  
        else  
        {  
            scanf("%d",&n);  
            printf("%d\n",f(1,M+2,Root));  
  
        }         
    }  
    //print(Root);  
  
    return 0;  
      
}

上面是数组写的，这个是链表写的。很不好意思，这个也超时。不知道你们能不能看懂，我写仅仅是纪念。