c++算法模板(三)

 

<7>最小环问题

ans为最小环的最优值:

for(int k=1;k<=n;k++)

           for(int i=1;i<k;i++)

            for(int j=i+1;j<k;i++)

           ans=min(ans,dis[i][k]+dis[k][j]+dis[i][j]);

          for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

              dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

<8>并查集

“并”:void unionn (int x,int y)

{

         x=find(x);

         y=find(y);

         if(x!=y) 

         pre[x]=y; 

}

 “查”:int find (int x)

{

         if(pre[x]!=x)                  //路径压缩算法,如果不需要可以这样写

           pre[x]=find(pre[x]);       //if(x!=y) return find(pre[x]);

         return pre[x];               //else return x;

}

“集”:bool judge(int x,int y)  //判断是否连通,可以直接写在代码里不用另写函数。

{

         x=find(x);             

         y=find(y);

         if(x==y) return true;

         else return false;

 }

<9>MST(最小生成树)

1.      prim算法

 #include<iostream>

#include<cstring>

#define maxn 5010

#define maxm 200010

using namespace std;

int map[maxn][maxn];

int e[maxm];

int v[maxn];

int n,x,y,w,m;

int main()

{

memset(e,0x7f,sizeof(e));

cin>>n>>m;

for(int i=1;i<=m;i++)

{

           cin>>x>>y>>w;

           map[x][y]=map[y][x]=w;

}

e[1]=0;

for(int i=1;i<=n;i++)

{

           int k=0;

           for(int j=1;j<=n;j++)

            if((v[j]==0) && (e[j]<e[k]))

              k=j;

           v[k]=1;

           for(int j=1;j<=n;j++)

            if((v[j]==0) && (map[k][j]<e[j]))

              e[j]=map[k][j];

}

int sum=0;

for(int i=1;i<=n;i++)

 sum+=e[i];

cout<<sum<<endl;

return 0;

}

2.      kruskal算法

#include<iostream>

#include<algorithm>

#define maxn 5010

#define maxm 200010

using namespace std;

int n,k,m,sum,pre[maxn];

int find (int x);

struct point

{

         int x;

         int y;

         int v;

}a[maxm];

void unionn (int x,int y)

{

         x=find(x);

         y=find(y);

         if(x!=y) 

         pre[x]=y; 

}

int find (int x)

{

         if(pre[x]!=x)          

           pre[x]=find(pre[x]);  

         return pre[x];     

}

int cmp(const point &a,const point &b)

{

         if(a.v<b.v)return 1;

         else return 0;

}

int main()

{

         cin>>n>>m;

         for(int i=1;i<=m;i++)

         {

                   cin>>a[i].x;

                   cin>>a[i].y;

                   cin>>a[i].v;

         }

         for(int i=1;i<=n;i++)

           pre[i]=i;

         sort(a+1,a+1+m,cmp);

         for(int i=1;i<=m;i++)

         {

                   if(find(a[i].x)!=find(a[i].y))

                   {

                            unionn(a[i].x,a[i].y);

                            sum+=a[i].v;

                            k++;

                   }

                   if(k==n-1) break;

         }

         cout<<sum<<endl;

         return 0;

}

<10>拓扑排序

#include<iostream>

using namespace std;

int a[101][101],c[101],r[101],ans[101];

int i,j,tot,temp,num,n,m;

int main()

{

         cin>>n;

         for(int i=1;i<=n;i++)

         {

                   do

                   {

                            cin>>j;

                            if(j!=0)

                            {

                                     c[i]++;

                                     a[i][c[i]]=j;

                                     r[j]++;

                            }

                   }while(j!=0);

         }

         for(int i=1;i<=n;i++)

          if(r[i]==0)

           ans[++tot]=i;

         do

         {

                   temp=ans[tot];

                   cout<<temp<<" ";

                   tot--;

                   num++;

                   for(int i=1;i<=c[temp];i++)

                   {

                            r[a[temp][i]]--;

                            if(r[a[temp][i]]==0)

                             ans[++tot]=a[temp][i];

                   }

         }while(num!=n);

         return 0;

}

<11>关键路径

1.      求出每个点的最早发生的时间,正序求得

Earliest[1n]=max(Earliest[1n+map[pre][ 1n])

2.      求出每个点最迟发生的时间,逆序求得

Last[n1]=min(Last[n1]-map[n1][pre])

3.      最迟-最早的的余量如果为0,则此点为关键点,项连得路径叫做关键路径。

1.      数论

 <1>辗转相除法

 a / b = b / a%b

int gcd (int a,int b)

{

      if(b==0)

      return a;

      else

      gcd(b,a%b);

 }

也可以用来求最小公倍数,lcm=a/gcd(a,b)*b。先除后乘的原因是为了避免乘法溢出。

2.唯一分解定理:一个数可以分成若干个素数相乘的形式。

3.      素数定理:π(x)~x/lnx.求出有多少个小于x的素数。

4.      Eratosthenes筛素数

 Int m=sqrt(n+0.5);

 Forint i=1;i<=n;i++

  If(vis[i]==0)

   For(int j=i*i;j<=n;j++)

Vis[j]=1;

还要确定1不是素数,2是素数。如果标记为1i不为素数,如果未标记则为素数。

5.      扩展欧几里得算法

 Void gcd (int a,int b,int &d,int &x,int &y)

{

  If(b==0)  {d=a; x=1; y=0;}

  Else { gcd(b,a%b,y,x);

        Y-=x*(a/b);

       }

}

求出一组解来,其他部分可写为(x0+kb’,y0-ka’),a’=a/gcd(a,b),b’=b/gcd(a,b);k是整数。

G=gcd(g/b)  ax+bx=c c不为g的倍数是,则此方程无整数解。

6.      幂取模

 a^n %m 的值:

 Int mod (int a,int b,int m)

{

If(n==0) return 1;

 Int x=mod(a,n/2,m);

 Long long ans=(long long)x*x %m;

If(n%2==1) ans=ans*a % m;

Return (int) ans;

}

7.      同余与模运算:

  (a+b)%n=((a %n)+(b%n))%n

  (a-b)%n=((a%n)-(b%n)+n)%n

  ab%n=(a%n)(b%n)%n

8.      杨辉三角:

                      1

                   1    1

                  1   2   1

               1    3    3   1

             1    4   6    4    1

           1   5    10  10   5    1  

         1   6   15    20  15   6    1

 

C[i]=c[i+1]*(n-i+1)/i;

C[i]=n!/i!(n-1)!;