各种模板（part 2）

堆：

 1 using namespace dui //堆
 2 {
 3     #include<queue> //需要的库
 4     priority_queue < int > Q; //定义一个Q的大根堆,top（）为较大的
 5     priority_queue < int,vector < int >,greater< int > > q; //定义一个q的小根堆。top()为较小的
 6     q.empty() //判断队空
 7     q.push(x) //将x放入队列
 8     q.pop() //将队头删除
 9     q.size() //返回堆中元素个数
10     q.top() //返回队头
11     
12     //在结构体中自己定义优先级
13     struct node
14     {
15         int id,v;
16         friend bool operator < (node n1, node n2)
17         {
18             return n1.v>n2.v; //要满足的条件
19         }
20     }f[maxn];
21     priority_queue<node>q;
22 }

View Code

图论：

图的建立+遍历

 1 using namespace tu //图
 2 {
 3     int len=0,linkk[maxn];
 4     struct node //邻接表
 5     {
 6         int x,y,v;
 7     }e[maxn];
 8     init(int xx,int yy,int vv)
 9     {
10         e[++len].y=linkk[xx];linkk[xx]=len;
11         e[len].x=yy;e[len].v=vv;
12     }
13     
14     struct node    // 边表
15     {
16         int x,y;
17     }e[maxn];
18     
19     void dfs(int k) //邻接矩阵的dfs
20     {
21         for(int i=1;i<=n;i++)
22         {
23             if((a[k][i])&&(!f[i]))
24             {
25                 f[i]=1;
26                 dfs(i);
27             }
28         }
29     }
30     
31     void dfs(int k) //邻接表的dfs
32     {
33         for(int i=linkk[k];i;i=e[i].y)
34         {
35             if(!f[e[i].x])
36             {
37                 f[e[i].x]=1;
38                 dfs(e[i].x);
39             }
40         }
41     }
42 }

View Code

floyed+dijkstra（最短路，邻接矩阵）

 1 void floyed()    //神算法,,邻接矩阵
 2     {
 3         for(int k=1;k<=n;k++)
 4             for(int i=1;i<=n;i++)
 5                 for(int j=1;j<=n;j++)
 6                     dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
 7     }
 8     
 9     void dijkstra(int st)    //邻接矩阵
10     {
11         for(int i=1;i<=n;i++)
12             dis[i]=a[st][i];
13         memset(vis,0,sizeof(vis));
14         vis[st]=1;dis[st]=0;
15         for(int i=1;i<=n;i++)
16         {
17             int minn=999999;
18             int k=0;
19             for(int j=1;j<=n;j++)
20             {
21                 if((!vis[j])&&(dis[j]<minn))
22                 {
23                     minn=dis[j];
24                     k=j;
25                 }
26             }
27             if(k==0)    return;
28             vis[k]=1;
29             for(int j=1;j<=n;j++)
30             {
31                 if(!vis[j]&&(dis[k]+a[k][j]<dis[j]))
32                 {
33                     dis[j]=dis[k]+a[k][j];
34                 }
35             }
36         }
37     }

View Code

bellman-ford（最短路，判负环，边表）

 1 int bellman-ford(int st) //边表
 2     {
 3         memset(dis,10,sizeof(dis));
 4         dis[st]=0;
 5         bool rel=0;
 6         for(int i=1;i<=n;i++)
 7         {
 8             rel=0;
 9             for(int j=1;j<=len;j++)
10             {
11                 if(dis[e[j].x]+a[j].v<dis[a[j].y])
12                 {
13                     dis[a[j].y]=dis[e[j].x]+a[j].v;
14                     rel=1;
15                 }
16             }
17             if(!rel)
18                 return 0; //没有松弛，结束
19         }
20         return 1; //迭代n次，又负环
21     }

View Code

SPFFA（最短路，邻接表）

 1 void SPFA(int st) //邻接表
 2     {
 3         memset(dis,10,sizeof(dis));
 4         memset(vis,0,sizeof(vis));
 5         int q[maxn],head=0,tail=1;
 6         dis[st]=0;vis[st]=1;q[1]=sr;
 7         while(head<=tail)
 8         {
 9             int tn=q[++head];via[tn]=0;
10             int te=linkk[tn];
11             for(int i=te;i;i=e[i].y)
12             {
13                 int tmp=e[i].x;
14                 if(dis[tmp]>dis[tn]+e[i].v)
15                 {
16                     dis[tmp]=dis[tn]+e[i].v;
17                     if(!vis[tmp])
18                     {
19                         q[++tail]=tmp;
20                         vis[tmp]=1;
21                     }
22                 }
23             }
24         }
25     }

View Code

prim（最小生成树，邻接矩阵）

 1 void prim(int st) //最小生成树,邻接矩阵
 2     {
 3         memset(dis,10,sizeof(dis));
 4         memset(vis,0,sizeof(vis));
 5         vis[st]=1;sum=0;
 6         for(int i=1;i<n;i++)
 7         {
 8             int minn=a[0][0],c=0;
 9             for(int j=1;j<=n;j++)
10             {
11                 if(!vis[j]&&dis[j]<minn)
12                 {
13                     minn=dis[j];
14                     c=j;
15                 }
16             }
17             vis[c]=1;
18             sum+=minn;
19             for(int j=1;j<=n;j++)
20             {
21                 if(a[c][j]<dis[j]&&!vis[j])
22                     dis[j]=a[c][j];
23             }
24         }
25     }

View Code

kruskal（最小生成树，边表）

 1 kruskal //边表+并查集
 2     {
 3         struct node // 边表
 4         {
 5             int x,y;
 6         }e[maxn];
 7         int getfa(int k)
 8         {
 9             if(fa[k]==k) return k;
10             fa[k]=getfa(fa[k]);
11             return fa[k];
12         }
13         void meg(int x,int y)
14         {
15             int fx=getfa(x);
16             int fy=getfa(y);
17             fa[fx]=fy;
18         }
19         bool jud(int x,int y)
20         {
21             int fx=getfa(x);
22             int fy=getfa(y);
23             return fx==fy;
24         }
25         bool mys(node a,node b)
26         {
27             return a.v<b.v;
28         }
29         void kruskal()
30         {
31             for(int i=1;i<=n;i++)
32                 fa[i]=i;
33             sort(e+1,e+1+m,mys);
34             int cal=0;
35             for(int i=1;i<=len;i++)
36             {
37                 int fx=getfa(e[i].x);
38                 int fy=getfa(e[i].y);
39                 if(fx!=fy)
40                 {
41                     meg(fx,fy);
42                     if(++cal==n-1);
43                     return ;
44                 }
45             }
46         }
47     }

View Code