暑期7.26-8.14学习小结

#include<iostream> #include<cstdio> #include<string.h> #include<vector> #include<queue> #include<algorithm> using namespace std; int n; int next[1001]; int pre[1001]; int map[1001][1001]; int dis[1001]; int vis[1001]; char s1[10001]; char s2[1001]; int num[1001]; int dp[1001]; const int inf=0x7FFFFFFF; //----------------Dijkstra算法-------------------------- void Dijkstra(int st) {     int pos,min;     memset(vis,0,sizeof(vis));     vis[st]=1;     for(int i=1;i<=n;i++)         dis[i]=map[st][i];         dis[st]=0;     for(int i=1;i<=n;i++)     {         min=inf;         for(int j=1;j<=n;j++)             if(!vis[j]&&dis[j]<min)             {                 min=dis[j];                 pos=j;             }         if(min>=inf) break;         vis[pos]=1;         for(int j=1;j<=n;j++)         {             if(!vis[j]&&map[pos][j]+dis[pos]<dis[j])                 dis[j]=map[pos][j]+dis[pos];         }     } } //----------------SPFA算法-------------------------- void SPFA(int st) {     memset(vis,0,sizeof(vis));     for(int i=1;i<=n;i++)         dis[i]=inf;         dis[st]=0;     queue<int> q;     q.push(st);     vis[st]=1;     while(!q.empty())     {         int cur;         cur=q.front();         q.pop();         vis[cur]=0;         for(int i=1;i<=n;i++)             if(dis[cur]+map[cur][i]<dis[i])             {                 dis[i]=dis[cur]+map[cur][i];                 if(!vis[i])                 {                    q.push(i);                    vis[i]=1;                 }             }     } } //-----------------Prim算法-------------------------- void Prim() {     memset(vis,0,sizeof(vis));     for(int i=1;i<=n;i++)         dis[i]=map[1][i];     vis[1]=1;     for(int i=1;i<=n;i++)     {         int min=inf,pos;         for(int j=1;j<=n;j++)         {             if(!vis[j]&&dis[j]<min)             {                 min=dis[j];                 pos=j;             }         }         vis[pos]=1;         for(int j=1;j<=n;j++)         {             if(!vis[j]&&map[pos][j]<dis[j])             {                 dis[j]=map[pos][j];             }         }     } } //----------------并查集-------------------------- int find(int x) {     int r=x;     while(r!=pre[r])         r=pre[r];     int i=x,j;     while(i!=r)  //路径压缩     {         j=pre[i];         pre[i]=r;         i=j;     }     return r; } void join(int x,int y) {     if(find(x)!=find(y))         pre[find(x)]=find(y); } //----------------KMP算法---------------------- int findnext(int len) {     int j;     next[0]=-1;     for(int i=1;i<len;i++)     {         j=next[i-1];         while(s2[j+1]!=s2[i]&&j>=0)             j=next[j];         if(s2[j+1]==s2[i])             next[i]=j+1;         else next[i]=-1;     } } int KMP(int len1,int len2) {     int i=0,j=0;     while(i<len1&&j<len2)     {         if(s1[i]==s2[j])         {             i++;             j++;         }         else         {             if(j==0) i++;             else j=next[j-1]+1;         }     }     return j==len2?(i-len2):-1; } //-----------------二分算法------------------- //在0到100内查找一个平方等于n的数  double half(double n) {     double l=0;     double r=100;     double m=(r+l)/2;     while(r-l>=0.0000001)     {         if(n<m*m)             r=m;         if(n>m*m)             l=m;         m=(r+l)/2;     }     return m; } //-------------01，多重，完全背包------------- void ZOP(int cost,int wei) {     for(int i=v;i>=cost;i--)     {         dp[i]=max(dp[i],dp[i-cost]+wei);     } } void CP(int cost,int wei) {     for(int i=cost;i<=v;i++)     {         dp[i]=max(dp[i],dp[i-cost]+wei);     } } void MP(int cost,int wei,int cnt) {     if(cost*cnt>=v)     {         CP(cost,wei);         return;     }     else      {         int k=1;         while(k<cnt)         {             ZOP(k*cost,k*wei);             cnt-=k;             k<<=1;         }         ZOP(cnt*cost,cnt*wei);     } } //---------------------------------------------