【复习】算法模版<二>

从现在就开始复习算法，都忘干干静静了。

一、最短路问题：

1.dijstra无优化版

 1 #include<iostream>
 3 #define INF 0x7f
 4 #define maxn 10010
 5 #define maxm 50010
 6 using namespace std;
 7 int num,k,minl,n,m,s;
 8 int head[maxn],dis[maxn],v[maxn];
 9 struct Edge{
10     int next;
11     int to;
12     int dis;
13 }edge[maxm];
14 void add_edge(int u,int v,int w)
15 {
16        num++;
17        edge[num].next=head[u];
18        edge[num].to=v;
19        edge[num].dis=w;
20        head[u]=num;
21 }
22 void dijstra(int v0)
23 {
24     for(int i=1;i<=n;i++) dis[i]=INF;   //初始化最大值，因为判断时所需。自行理解。
25     dis[v0]=0;                         //起点到起点的距离为零
26     for(int i=1;i<=n;i++)
27     {
28         minl=INF;                      //找小值初始化一个大的数
29         k=0;                           //初始化（每一个循环要从新找）
30         for(int j=1;j<=n;j++)
31         {
32             if(v[j]==0 && dis[j]<minl)  //判断是否找过该点并且是最小值
33              {
34                  minl=dis[j];
35                  k=j;                   //赋值
36              }
37         }
38         v[k]=1;                      //该点查找完毕
39         for(int i=head[k];i!=0;i=edge[i].next)  //邻接表读取
40         {
41             int a=edge[i].to;
42             if(v[a]==0 && minl+edge[i].dis<dis[a]) dis[a]=minl+edge[i].dis; //赋值
43         }
44     }
45 }
46 int main()
47 {
48         cin>>n>>m>>s;       //读取点数，边数，起点。
49     for(int i=1;i<=m;i++)
50     {
51         int u,v,w;
52         cin>>u>>v>>w;
53         add_edge(u,v,w);
54     }
55     dijstra(s);
56     for(int i=1;i<=n;i++)
57     cout<<dis[i]<<" ";   //输出起点到各个点的最小值
58     return 0;
59 }

测试数据：

输入：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出：0 2 4 3

算法理解：无优化版的算法比较好理解，首先是邻接表储存图，关于邻接表存图可以通过输入数据进行理解，或者查看本人算法模板里有介绍。然后算法首先，确定起点。开始查找与起点有关联的点，从起点到该点的距离进行判断，小于dis数组里，就讲dis数组赋值小的值，搜完了，起点抛弃，从离下一个点最近的点开始搜，仍旧跟这个套路，最后每一个点到起点的最小值都可以算出来，说的可能不清楚。（注：dis数组的意义表示为从起点到i点的距离的最小值）

请看下图:

代码测试可用。

2.dijstra+堆优化版

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #define maxn 10010
 5 #define maxm 500010
 6 const int INF=0x7f;
 7 using namespace std;
 8 int n,m,s,num;
 9 int head[maxn],dis[maxn],vis[maxn];
10 struct Edge
11 {
12     int next;
13     int to;
14     int dis;
15 }edge[maxm];
16 struct Node{
17     int d,id;
18     Node(){}
19     Node(int d,int id):d(d),id(id){}
20     bool operator < (const Node& sph)const {         //重载 方便堆
21           return d>sph.d;
22     }
23 };
24 void add_edge(int u,int v,int w)
25 {
26     num++;
27     edge[num].next=head[u];
28     edge[num].to=v;
29     edge[num].dis=w;
30     head[u]=num;
31 }
32 void dijstra(int v0)
33 {
34     for(int i=1;i<=n;i++) dis[i]=INF;
35     dis[v0]=0;
36     priority_queue<Node>q;
37     q.push(Node(0,v0));
38     while(!q.empty())
39     {
40         Node u=q.top();
41         q.pop();
42         if(vis[u.id]) continue;  //若某点已经更新到最优则跳过
43         vis[u.id]=1;
44         for(int i=head[u.id];i;i=edge[i].next)
45         {
46             int v=edge[i].to;
47             int w=edge[i].dis;
48             if(dis[v]>w+u.d) 
49               {
50                 dis[v]=w+u.d;
51                 q.push(Node(dis[v],v));
52               }    
53         }
54     }
55 }
56 int main()
57 {
58     cin>>n>>m>>s;
59     for(int i=1;i<=m;i++)
60     {
61         int u,v,w;
62         cin>>u>>v>>w;
63         add_edge(u,v,w);
64     }
65     dijstra(s);
66     for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
67     return 0;
68 }

测试数据：

输入：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出：0 2 4 3

关于算法的理解呢其实总时间的复杂度是每一个点查找最短距离并且更新每一个点是松弛的时间复杂度的总和。对于一个无向图G(V,E)来说，找最短距离的最短时间复杂度是n^2/2，有m条边那么更新时间复杂度是2*m。那么复杂度总和是可以知道的，也就是说我们需要优化找最短距离那一部分。最简单的优化不过就是用二分查找（logN）代替线性查找（n），用二分查找代表是堆呀。所以就出现了堆+dijstra优化。运用到c++STL库函数priority_queue()优先队列。具体实现请看代码。堆优化那块背过好了，反正noip2016day1t2一个lca题用了dijstra做了。骗了40分。

代码已实现
3.SPFA算法
 1 #include<iostream>
 2 #include<cstdio>
 3 #define maxn 10010
 4 #define maxm 500010
 5 const int INF=0x7f;
 6 using namespace std;
 7 int n,m,s,num,h,t;
 8 int q[maxn],dis[maxn],inq[maxn],head[maxn];
 9 struct Edge
10 {
11     int next;
12     int to;
13     int dis;
14 }edge[maxm];
15 void add_edge(int u,int v,int w)
16 {
17     num++;
18     edge[num].next=head[u];
19     edge[num].to=v;
20     edge[num].dis=w;
21     head[u]=num;
22 }
23 inline void lop(int &x){x++; if(x==maxn) x=1;} 
24 void spfa(int v0)
25 {
26     for(int i=1;i<=n;i++) dis[i]=INF;
27     dis[v0]=0;
28     h=t=1;
29     q[t++]=v0;
30     inq[v0]=1;
31     while(h!=t)
32     {
33         int u=q[h];
34         inq[u]=0;
35         lop(h);
36         for(int i=head[u];i;i=edge[i].next)
37         {
38             int v=edge[i].to;
39             int w=edge[i].dis;
40             if(dis[v]>w+dis[u]) {
41                 dis[v]=w+dis[u];
42                 if(!inq[v]){
43                     inq[v]=1;
44                     q[t]=v;
45                     lop(t);
46                 }
47             }
48         }
49     }
50 }
51 int main()
52 {
53         cin>>n>>m>>s;
54     for(int i=1;i<=m;i++)
55     {
56         int u,v,w;
57         cin>>u>>v>>w;
58         add_edge(u,v,w);
59     }
60     spfa(s);
61     for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
62     return 0;
63 }


测试数据：


输入：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出：0 2 4 3


算法理解：dis数组储存最短路数据，然后邻接表存图。原理呢就是，运用动态逼近法。建个队列q，然后从起点加，找松弛的点，如果没有入队列的或者排除队列的，就进行入队，然后把该点排出去，从下一个继续，知道没有点入队，则算法结束。不过spfa可以处理负边，贼好用的算法。时间复杂度是（km），不过许多比赛都是会卡常数k的。但大多数是不会的。对于我来说，我一般只有遇到负值才用spfa，平常都用dijstra堆优化的。
看不懂的可以看看这个写的：http://www.360doc.com/content/13/1208/22/14357424_335569176.shtml
我想大家应该看不懂我写的。。。

代码测试通过。

4.Floyd-Warshall算法




 1 #include<iostream>
 2 #define maxn 10010
 3 #define INF 0x7f
 4 using namespace std;
 5 int map[maxn][maxn];
 6 int n,m,s;
 7 int main()
 8 {
 9     cin>>n>>m>>s;
10     for(int i=1;i<=n;i++)
11     {
12         map[i][i]=0;
13     }
14     for(int i=1;i<=m;i++)
15     {
16         int u,v,w;
17         cin>>u>>v>>map[u][v];
18         map[v][u]=INF;
19     }
20     for(int k=1;k<=n;k++)
21     for(int i=1;i<=n;i++)
22     for(int j=1;j<=n;j++)
23     {
24         if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j];
25     }
26     cout<<"1->1="<<map[1][1]<<endl;
27     for(int i=1;i<=n;i++)
28     for(int j=1;j<=n;j++)
29     {
30         if(map[i][j]!=INF && map[i][j]!=0) cout<<i<<"->"<<j<<"="<<map[i][j]<<endl;
31     }
32     return 0;
33 }






 算法原理：就是图表用一个二维数组进行储存，然后储存的是从i点到j点的最短路值，并且用i到k，再从k到j来进行更新，选择最短路。


5.kruskal算法：




 1 #include<iostream>
 2 #include<algorithm>
 3 #define maxn 10010
 4 #define maxm 500010
 5 using namespace std;
 6 int n,m,k,sum;
 7 int pre[maxn];
 8 struct point{
 9     int x;
10     int y;
11     int w;
12 }a[maxm];
13 int find(int x)
14 {
15     if(pre[x]!=x) pre[x]=find(pre[x]);
16     return pre[x];
17 }
18 int unionn(int x,int y)
19 {
20     x=find(x);
21     y=find(y);
22     if(x!=y) pre[x]=y;
23 }
24 int cmp(const point &a,const point &b)
25 {
26     if(a.w<b.w) return 1;
27     else return 0;
28 }
29 int main()
30 {
31     cin>>n>>m;
32     for(int i=1;i<=m;i++)
33     {
34         cin>>a[i].x;
35         cin>>a[i].y;
36         cin>>a[i].w;
37     }
38     for(int i=1;i<=n;i++) pre[i]=i;
39     sort(a+1,a+1+m,cmp);
40     for(int i=1;i<=m;i++)
41     {
42         if(find(pre[a[i].x])!=find(a[i].y))
43         {
44             unionn(a[i].x,a[i].y);
45             sum+=a[i].w;
46             k++;
47         }
48         if(k==n-1) break;
49     }
50     cout<<sum<<endl;
51     return 0;
52 } 




测试数据：


输入：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出：
7


算法原理：最小生成树算法，贼好理解，恩，运用并查集+stl排序，一种贪心思想的利用，当时看算法的时候第一个一次性看明白的算法。关于并查集的思想学一下，很好用的。当时我去年看的浙江一金牌大牛博客现在没链接了。就是先把边值最小的排在前面。然后从小的开始进行合并，如果合并就跳过，没合并就总值加上。待k==n-1的时候就搞定了。因为n个点最少有n-1条边……还有一种算法叫prim算法也是最小生成树的，不过我放弃了，因为没卵用。


代码测试通过


 6.KMP




 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #define maxn 1000010
 7 #define maxm 10010
 8 using namespace std;
 9 char a[maxn],b[maxm];
10 int next[100100];
11 int ans[100100];
12 int lena,lenb,k;
13 int GetNext()
14 {
15     int t=0;
16     next[0]=-1;
17     for(int i=1;i<lenb;++i)
18     {
19         t=next[i-1];
20         while(b[t+1]!=b[i] && t>=0)
21           t=next[t];
22         if(b[t+1]==b[i])
23           next[i]=t+1;
24         else
25           next[i]=-1;
26     }
27 }
28 int KMP()
29 {
30     GetNext();
31     int i=0,j=0;
32     while(j<lena)
33     {
34         if(b[i]==a[j])
35         {
36             ++i;
37             ++j;
38             if(i==lenb)
39             {
40                 ans[k++]=j-lenb+1;
41                 i=next[i-1]+1;
42             }
43         }
44             else
45             {
46                 if(i==0) j++;
47                 else i=next[i-1]+1;
48             }
49     }
50     
51 }
52 int main()
53 {
54     scanf("%s%s",a,b);
55     lena=strlen(a);
56     lenb=strlen(b);
57     KMP();
58     for(int i=0;i<k;i++)
59      cout<<ans[i]<<endl;
60     for(int i=0;i<lenb;i++)
61      cout<<next[i]+1<<" ";
62      cout<<endl;
63      return 0;
64     
65 }




7.Sunday算法




 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #define maxn 1000010
 7 #define maxm 10010
 8 using namespace std;
 9 char a[maxn],b[maxm];
10 int n[100100];
11 int ans[100100];
12 int movelength[256];
13 int lena,lenb,k;
14 /*int GetNext()
15 {
16     int t=0;
17     n[0]=-1;
18     for(int i=1;i<lenb;++i)
19     {
20         t=n[i-1];
21         while(b[t+1]!=b[i] && t>=0)
22           t=n[t];
23         if(b[t+1]==b[i])
24           n[i]=t+1;
25         else
26           n[i]=-1;
27     }
28 }*/
29 int getlength()
30 {
31     for(int i=0;i<256;i++) movelength[i]=lenb+1;
32     for(int i=0;b[i];++i) movelength[b[i]]=lenb-i;
33 }
34 int sunday()
35 {
36     int i=0;
37     getlength();
38   //  GetNext();
39     while(i<lena)
40     {
41         int j=0;
42         for(; j<lenb && (i+j)<lena && a[i+j]==b[j]; ++j ) ;
43         if(j>=lenb) 
44         {
45             ans[k]=i;
46             k++;
47         }
48         if(i+lenb>lena) return -1;
49         i+=movelength[a[i+lenb]];
50     }
51     return -1;
52 }
53 int main()
54 {
55     scanf("%s%s",a,b);
56     lena=strlen(a);
57     lenb=strlen(b);
58     sunday();
59    // for(int i=0;i<lenb;i++) cout<<n[i]+1<<" ";
60    // cout<<endl;
61     for(int i=0;i<lenb;i++) cout<<movelength[i]<<" ";
62     cout<<endl;
63     for(int i=0;i<k;i++) cout<<ans[i]+1<<" "; 
64     return 0;
65 }





8.HASH系列


首先是字符串hash 原理是求字符串hash的key值


以下四个模板分别是：自然溢出、单hash、双hash、模10 ^18次方的素数值hash。




 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 typedef long long ll;
 7 ll prime=131;
 8 char ch[10010];
 9 ll a[10010];
10 ll sum=1;
11 int n;
12 ll sphhash(char ch1[])
13 {
14     int len=strlen(ch1);
15     ll ans=0;
16     for(int i=0;i<len;i++)
17         ans=ans*prime+(ll)ch1[i];
18     return ans&0x7fffffff;
19 }
20 int main()
21 {
22     cin>>n;
23     for(int i=1;i<=n;i++)
24     {
25         scanf("%s",ch);
26         a[i]=sphhash(ch);
27     }
28     sort(a+1,a+1+n);
29     for(int i=2;i<=n;i++)
30          if(a[i]!=a[i-1]) sum++;
31      cout<<sum<<endl;
32      return 0;
33 }






 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 typedef long long ll;
 7 ll prime=131;
 8 ll mofashu=19260817;
 9 char ch[10010];
10 ll a[10010];
11 ll sum=1;
12 int n;
13 ll sphhash(char c[])
14 {
15     ll ans=0;
16     int len=strlen(c);
17     for(int i=0;i<len;i++)
18         ans=(ans*prime+(ll)c[i])%mofashu;
19     return ans;
20 }
21 int main()
22 {
23     cin>>n;
24     for(int i=1;i<=n;i++)
25     {
26         scanf("%s",ch);
27         a[i]=sphhash(ch);
28     }
29     sort(a+1,a+1+n);
30     for(int i=2;i<=n;i++)
31          if(a[i]!=a[i-1]) sum++;
32      cout<<sum<<endl;
33      return 0;
34 }






 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 typedef unsigned long long ll;
 7 ll prime=131;
 8 ll mofashu1=19260817;
 9 ll mofashu2=19660813;
10 char ch[10010];
11 ll sum=1;
12 int n;
13 struct data{
14   ll x;
15   ll y;    
16 }a[10010];
17 ll sphhash1(char c[])
18 {
19     ll ans=0;
20     int len=strlen(c);
21     for(int i=0;i<len;i++)
22       ans=(ans*prime+(ll)c[i])%mofashu1;
23     return ans;
24 }
25 ll sphhash2(char c[])
26 {
27     ll ans=0;
28     int len=strlen(c);
29     for(int i=0;i<len;i++)
30       ans=(ans*prime+(ll)c[i])%mofashu2;
31     return ans;
32 }
33 int cmp(data a,data b)
34 {
35     return a.x<b.x;
36 }
37 int main()
38 {
39     cin>>n;
40     for(int i=1;i<=n;i++)
41      {
42          scanf("%s",ch);
43          a[i].x=sphhash1(ch);
44          a[i].y=sphhash2(ch);
45      }
46     sort(a+1,a+1+n,cmp);
47     for(int i=2;i<=n;i++)
48         if(a[i].x!=a[i-1].x || a[i].y!=a[i-1].y) sum++;
49         cout<<sum<<endl;
50         return 0;
51 }






 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 typedef unsigned long long ll;
 7 int n; 
 8 char s[10010];
 9 ll a[10010];
10 ll prime=131;
11 ll mofashu=212370440130137957ll;
12 ll sum=1;
13 ll sphhash(char c[])
14 {
15     ll ans=0;
16     int len=strlen(c);
17     for(int i=0;i<len;i++)
18      ans=(ans*prime+(ll)c[i])%mofashu;
19      return ans;
20 }
21 int main()
22 {
23     cin>>n;
24     for(int i=1;i<=n;i++)
25     {
26         scanf("%s",s);
27         a[i]=sphhash(s);
28     }
29     sort(a+1,a+n+1);
30     for(int i=2;i<=n;i++)
31      if(a[i]!=a[i-1]) sum++;
32      cout<<sum<<endl;
33      return 0;
34 }




关于素数求法可以直接去看上面的筛素数来求。


9.STL模板




  1 #include<iostream>
  2 #include<string>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<map>
  6 #include<set>
  7 #include<vector>
  8 #include<algorithm>
  9 #include<queue>
 10 using namespace std;
 11 int intdata1,intdata2;
 12 set<int>a;
 13 map<string,int>b;
 14 map<string,int>c;  //按照key值排序 利用make_pair() 
 15 map<string,int>d;  //按照value值排序 
 16 vector<int>f;
 17 priority_queue<int>g;
 18 int mapcmp(const pair<string, int>& x, const pair<string, int>& y)    
 19 {    
 20     return x.second < y.second;    
 21 }    
 22 
 23 void mapvaluecmp(map<string,int>& tmap,vector<pair<string,int> >& tvec)
 24 {
 25     for (map<string, int>::iterator curr = tmap.begin(); curr != tmap.end(); curr++)     
 26         tvec.push_back(make_pair(curr->first, curr->second));      
 27      
 28     sort(tvec.begin(), tvec.end(), mapcmp);
 29 }
 30 
 31 void useset()
 32 {
 33     cin>>intdata1;
 34     cin>>intdata2;
 35     set<int>::iterator it=a.begin(); //迭代器 
 36 
 37     a.insert(intdata1); //插入 
 38     a.insert(intdata2);
 39 
 40     int setsize=a.size();//大小
 41     cout<<setsize<<endl; 
 42 
 43     if(a.count(intdata1)) cout<<"intdata1 在里面."<<endl; //是否存在 
 44 
 45     it=a.find(intdata2); //查找返回迭代器值  没有则返回后一个值 
 46     if(it!=a.end()) cout<<*it<<endl;
 47     else cout<<"NOT FOUND"<<endl;
 48     it=a.begin();
 49 
 50     for(it;it!=a.end();++it)  //正序遍历 
 51         cout<<(*it)<<" ";
 52     cout<<endl;
 53 
 54     set<int>::reverse_iterator rit;
 55     for(rit=a.rbegin();rit!=a.rend();rit++) //反向遍历 
 56      cout<<(*rit)<<" ";
 57      cout<<endl;
 58 
 59     a.erase(intdata2);  //删除 
 60     
 61     a.clear(); //清空 
 62 
 63     if(a.empty()) //判断是否为空 
 64        cout<<"YES"<<endl;
 65     else cout<<"NO"<<endl;
 66 }
 67 void usemap()
 68 {
 69 
 70     b.insert(pair<string,int>("Srpihot*",5)); //插入 
 71     b["Heagst*"]=5;
 72     cout<<b["Srpihot*"]<<endl;
 73      
 74    
 75 
 76     int mapsize=b.size();  //大小 
 77     cout<<mapsize<<endl;
 78     
 79     if(b.count("Srpihot*")) //判断是否存在 
 80      cout<<"YES"<<endl;
 81     else
 82      cout<<"NO"<<endl;
 83          
 84          map<string,int>::iterator it;  //正序遍历 
 85         for(it=b.begin();it!=b.end();it++) cout<<it->first<<" "<<it->second<<endl;
 86     
 87     map<string,int>::reverse_iterator rit;
 88     for(rit=b.rbegin();rit!=b.rend();rit++) //反向遍历 
 89      cout<<rit->first<<" "<<rit->second<<endl;
 90      
 91      b.erase("Srpihot*");  //删除 
 92      
 93      b.clear();  //清空 
 94      
 95      if(b.empty()) //判断是否为空 
 96        cout<<"YES"<<endl;
 97     else cout<<"NO"<<endl;
 98 }
 99 void sortmap()
100 {
101     c.insert(make_pair("Srpihot*",5));
102        c.insert(make_pair("Heagst*",10));
103        
104     map<string,int>::iterator itc;  //c遍历 
105     for(itc=c.begin();itc!=c.end();itc++) cout<<itc->first<<" "<<itc->second<<endl;
106 
107     d.insert(make_pair("Srpihot*",5));
108        d.insert(make_pair("Heagst*",10));
109        
110        vector<pair<string,int> >e;
111        mapvaluecmp(d,e);
112        for(int i=0;i<e.size();i++)
113         cout<<e[i].first<<" "<<e[i].second<<endl;
114        
115     
116 }
117 void usevector()
118 {
119     f.push_back(1);  //插入 
120     f.push_back(3);
121     
122     for(int i=0;i<f.size();i++)  //大小及输出 
123      cout<<f[i]<<" ";
124      cout<<endl;
125 
126     f.erase(f.begin(),f.end()); //删除 
127     f.clear();  //清空 
128     if(f.empty()) //判断是否为空 
129        cout<<"YES"<<endl;
130     else cout<<"NO"<<endl;
131 }
132 void usequeue()
133 {
134     g.push(3); //插入 
135     g.push(1);
136     int queuesize=g.size();//大小 
137     cout<<g.top()<<endl;  //把栈顶元素排出 
138     g.pop();  //出栈 
139     cout<<g.top()<<endl;
140 //    g.clear();  //清空 
141     if(g.empty()) //判断是否为空 
142        cout<<"YES"<<endl;
143     else cout<<"NO"<<endl;
144 }
145 int main()
146 {
147 
148     useset();
149     usemap();
150     sortmap();
151     usevector();
152     usequeue();
153 }




10.LCA(tarjan)




 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define maxn 500010
 5 #define maxm 1000010
 6 using namespace std;
 7 int head[maxn],ahead[maxn],pre[maxn],ans[maxn];
 8 bool vis[maxn];
 9 int n,m,s,num,cnt,k,xx,yy;
10 struct edge{
11     int next;
12     int to;
13 }a[maxm];
14 struct tree{
15     int x;
16     int y;
17     int point;
18 }b[maxm];
19 inline int read()
20 {
21     int sum=0;int f=1;
22     char cc=getchar();
23     while(cc<'0' || cc>'9'){if(cc=='-')f=-1;cc=getchar();}
24     while(cc>='0' && cc<='9'){sum=sum*10+cc-'0';cc=getchar();}
25     return f*sum;
26 }
27 void add_edge(int u,int v)
28 {
29     num++;
30     a[num].next=head[u];
31     a[num].to=v;
32     head[u]=num;
33 }
34 void add_ask(int u,int v,int w)
35 {
36     cnt++;
37     b[cnt].x=ahead[u];
38     b[cnt].y=v;
39     b[cnt].point=w;
40     ahead[u]=cnt;
41 }
42 int find(int x)
43 {
44     if(pre[x]!=x) pre[x]=find(pre[x]);
45     return pre[x];
46 }
47 void unionn(int x,int y)
48 {
49     x=find(x);
50     y=find(y);
51     if(x!=y) pre[x]=y;
52 }
53 void tarjan(int v0)
54 {
55     vis[v0]=true;
56     for(int i=ahead[v0];i;i=b[i].x)
57       if(vis[b[i].y]) 
58        ans[b[i].point]=find(b[i].y);
59     for(int i=head[v0];i;i=a[i].next)
60       if(!vis[a[i].to])
61         {
62             tarjan(a[i].to);
63             unionn(a[i].to,v0);
64         }
65 }
66 int main()
67 {
68     n=read();
69     m=read();
70     s=read();
71     for(int i=1;i<=n;i++) pre[i]=i;
72     for(int i=1;i<=n-1;i++) 
73     {
74          xx=read();
75          yy=read();
76          add_edge(xx,yy);         
77          add_edge(yy,xx);
78     }
79     for(int i=1;i<=m;i++)
80     {
81          xx=read();
82          yy=read();
83          add_ask(xx,yy,i);
84          add_ask(yy,xx,i);
85     }
86          tarjan(s);
87      for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
88     return 0;
89 }





11.最短路计数




 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 #define maxn 1000010
 6 #define maxm 2000010
 7 #define INF 0x7f
 8 using namespace std;
 9 int num,n,m;
10 const int mofashu=100003;
11 int xx,yy;
12 int dis[maxn],vis[maxn],head[maxn],ans[maxn];
13 struct edge{
14     int next;
15     int to;
16     int dis;
17 }e[maxm];
18 struct Node{
19     int id,d;
20     Node(){}
21     Node(int d,int id):d(d),id(id){}
22     bool operator < (const Node& sph)const {return d>sph.d;}
23 };
24 inline int read()
25 {
26     int f=1;
27     int sum=0;
28     char c=getchar();
29     while(c>'9' || c<'0'){if(c=='-') f=-1;c=getchar();}
30     while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}
31     return sum*f;
32 }
33 void add_edge(int u,int v,int w)
34 {
35     num++;
36     e[num].next=head[u];
37     e[num].to=v;
38     e[num].dis=w;
39     head[u]=num;
40 }
41 void dijstra(int s)
42 {
43     for(int i=1;i<=n;i++) dis[i]=INF;
44     dis[s]=0;
45     ans[s]=1;
46     priority_queue<Node>q;
47     q.push(Node(0,s));
48     while(!q.empty())
49     {
50         Node u=q.top();
51         q.pop();
52         if(vis[u.id]) continue;
53         vis[u.id]=1;
54         for(int i=head[u.id];i;i=e[i].next)
55         {
56             int v=e[i].to;
57             int w=e[i].dis;
58             if(dis[v]==u.d+w) ans[v]=(ans[u.id]+ans[v])%mofashu;
59             if(dis[v]>u.d+w)
60             {
61                 dis[v]=e[i].dis+u.d;
62                 ans[v]=ans[u.id];
63                 q.push(Node(dis[v],v));
64              } 
65             
66         }
67     }
68 }
69 int main()
70 {
71     n=read();
72     m=read();
73     for(int i=1;i<=m;i++)
74     {
75         xx=read();
76         yy=read();
77         add_edge(xx,yy,1);
78         add_edge(yy,xx,1);
79     }
80     dijstra(1);
81     for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
82     return 0;
83 }




dijstra + 堆


11.未完待续……


（待整理及要学的：BFS DFS 二分图匹配 匈牙利算法 欧拉回路 拓扑排序 割点 tarjan 二分图染色 最小环 传递闭包 判负环等 不过先写点其他基础算法吧）





        

	      

	    

	  

	  

	    
      
        【推广】
        免费学中医，健康全家人
      
	  

    

    

          原文地址：https://www.cnblogs.com/srpihot/p/6847342.html