1.topology:

 #include <fstream>

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 using namespace std;

 #define EPS 1e-6

 #define ll long long

 #define INF 0x7fffffff

 const int N=;

 const int N2=;

 int fir[N],next_[N2],u[N2],v[N2];

 int du[N];

 int n,m;

 void Topology();

 int main(){

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)   fir[i]=-,du[i]=;

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

         scanf("%d%d",&u[i],&v[i]);

         next_[i]=fir[u[i]];

         fir[u[i]]=i;

         du[v[i]]++;

     }

     Topology();

     return ;

 }

 void Topology(){

     int top=-;

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

         if(du[i]==)    du[i]=top,top=i;

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

         if(top==-){

             cout<<"A cycle exists in the graph!"<<endl;

             return;

         }else{

             int j=top;

             top=du[top];

             cout<<j<<endl;

             for(int k=fir[j];k!=-;k=next_[k]){

                 if(--du[v[k]]==)

                     du[v[k]]=top,top=v[k];

             }

         }

     }

 }

2.dijkstra:

 #include <fstream>

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 using namespace std;

 #define INF 0x7fffffff

 const int N=;

 const int N2=;

 int node_num,edge_num,start_node,final_node;

 int node_first[N],node_next[N2],node_begin[N2],node_end[N2],node_value[N2];

 int dis[N],node_fa[N],road[N],road_len;

 bool b[N];

 void TheBegin();//初始化

 void Work();//存储无向图

 void Dijkstra();//核心算法

 void Road();//输出最短路径

 int main(){

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     scanf("%d%d%d%d",&node_num,&edge_num,&start_node,&final_node);

     TheBegin();

     Work();

     Dijkstra();

     Road();

     return ;

 }

 void TheBegin(){

     for(int i=;i<=node_num;i++){

         node_first[i]=-;

         dis[i]=INF;

     }

 }

 void Work(){

     for(int i=;i<=edge_num;i++){

         scanf("%d%d%d",&node_begin[i],&node_end[i],&node_value[i]);

         node_next[i]=node_first[node_begin[i]];

         node_first[node_begin[i]]=i;

         node_begin[i+edge_num]=node_end[i];

         node_end[i+edge_num]=node_begin[i];

         node_value[i+edge_num]=node_value[i];

         node_next[i+edge_num]=node_first[node_begin[i+edge_num]];

         node_first[node_begin[i+edge_num]]=i+edge_num;

     }

 }

 void Dijkstra(){

     dis[start_node]=;

     for(int k=;k<=node_num;k++){

         int x,m=INF;

         for(int i=;i<=node_num;i++)

             if(!b[i]&&dis[i]<m) m=dis[x=i];

         b[x]=;

         for(int i=node_first[x];i!=-;i=node_next[i]){

             if(!b[node_end[i]]&&dis[node_end[i]]>dis[x]+node_value[i]){

                 dis[node_end[i]]=dis[x]+node_value[i];

                 node_fa[node_end[i]]=x;

             }

         }

     }

     printf("%d\n",dis[final_node]);

 }

 void Road(){

     for(int i=final_node;i!=start_node;i=node_fa[i])    road[road_len++]=i;

     printf("the shortest road is:%d",start_node);

     for(int i=road_len-;i>=;i--)  printf("-->%d",road[i]);

     puts("");

 }

3.dijkstra堆优化:

 #include <fstream>

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <queue>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 using namespace std;

 #define INF 0x7fffffff

 const int N=;

 const int N2=;

 int node_num,edge_num,start_node,final_node;

 int node_first[N],node_next[N2],node_begin[N2],node_end[N2],node_value[N2];

 int dis[N],node_fa[N],road[N],road_len;

 bool b[N];

 typedef pair<int,int> pii;

 priority_queue<pii,vector<pii>,greater<pii> >pq;

 void TheBegin();//初始化

 void Work();//存储无向图

 void Dijkstra();//核心算法

 void Road();//输出最短路径

 int main(){

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     scanf("%d%d%d%d",&node_num,&edge_num,&start_node,&final_node);

     TheBegin();

     Work();

     Dijkstra();

     Road();

     return ;

 }

 void TheBegin(){

     for(int i=;i<=node_num;i++){

         node_first[i]=-;

         dis[i]=INF;

     }

 }

 void Work(){

     for(int i=;i<=edge_num;i++){

         scanf("%d%d%d",&node_begin[i],&node_end[i],&node_value[i]);

         node_next[i]=node_first[node_begin[i]];

         node_first[node_begin[i]]=i;

         node_begin[i+edge_num]=node_end[i];

         node_end[i+edge_num]=node_begin[i];

         node_value[i+edge_num]=node_value[i];

         node_next[i+edge_num]=node_first[node_begin[i+edge_num]];

         node_first[node_begin[i+edge_num]]=i+edge_num;

     }

 }

 void Dijkstra(){

     dis[start_node]=;

     pq.push(make_pair(dis[start_node],start_node));

     while(!pq.empty()){

         pii tmp=pq.top();

         pq.pop();

         int x=tmp.second;

         if(b[x])    continue;

         b[x]=;

         for(int i=node_first[x];i!=-;i=node_next[i]){

             if(!b[node_end[i]]&&dis[node_end[i]]>dis[x]+node_value[i]){

                 dis[node_end[i]]=dis[x]+node_value[i];

                 pq.push(make_pair(dis[node_end[i]],node_end[i]));//队列里可能会加入重复元素

                 node_fa[node_end[i]]=x;

             }

         }

     }

     printf("%d\n",dis[final_node]);

 }

 void Road(){

     for(int i=final_node;i!=start_node;i=node_fa[i])    road[road_len++]=i;

     printf("the shortest road is:%d",start_node);

     for(int i=road_len-;i>=;i--)  printf("-->%d",road[i]);

     puts("");

 }

4.spfa:

 #include <fstream>

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <queue>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 using namespace std;

 #define INF 0x7fffffff

 const int N=;

 const int N2=;

 int node_num,edge_num,start_node,final_node;

 int node_first[N],node_next[N2],node_begin[N2],node_end[N2],node_value[N2];

 int dis[N],node_fa[N],road[N],road_len;

 bool b[N];

 queue<int> q;

 void TheBegin();//初始化

 void Work();//存储无向图

 void Spfa();//核心算法

 void Road();//输出最短路径

 int main(){

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     scanf("%d%d%d%d",&node_num,&edge_num,&start_node,&final_node);

     TheBegin();

     Work();

     Spfa();

     Road();

     return ;

 }

 void TheBegin(){

     for(int i=;i<=node_num;i++){

         node_first[i]=-;

         dis[i]=INF;

     }

 }

 void Work(){

     for(int i=;i<=edge_num;i++){

         scanf("%d%d%d",&node_begin[i],&node_end[i],&node_value[i]);

         node_next[i]=node_first[node_begin[i]];

         node_first[node_begin[i]]=i;

         node_begin[i+edge_num]=node_end[i];

         node_end[i+edge_num]=node_begin[i];

         node_value[i+edge_num]=node_value[i];

         node_next[i+edge_num]=node_first[node_begin[i+edge_num]];

         node_first[node_begin[i+edge_num]]=i+edge_num;

     }

 }

 void Spfa(){

     dis[start_node]=;

     q.push(start_node);

     while(!q.empty()){

         int x=q.front();

         q.pop();

         b[x]=;

         for(int i=node_first[x];i!=-;i=node_next[i]){

             if(dis[node_end[i]]>dis[x]+node_value[i]){

                 dis[node_end[i]]=dis[x]+node_value[i];

                 node_fa[node_end[i]]=x;

                 if(!b[node_end[i]]){

                     q.push(node_end[i]);

                     b[node_end[i]]=;

                 }

             }

         }

     }

     printf("%d\n",dis[final_node]);

 }

 void Road(){

     for(int i=final_node;i!=start_node;i=node_fa[i])    road[road_len++]=i;

     printf("the shortest road is:%d",start_node);

     for(int i=road_len-;i>=;i--)  printf("-->%d",road[i]);

     puts("");

 }

5.floyd:

 #include <fstream>

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 using namespace std;

 #define INF 0x7fffffff

 const int N=;

 const int N2=;

 int node_num,edge_num,ans_num;

 int dp[N][N];

 int main()

 {

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     int u,v,w;

     scanf("%d%d",&node_num,&edge_num);

     for(int i=;i<=node_num;i++)

         for(int j=;j<=node_num;j++)

             dp[i][j]=(i==j?:INF);

     for(int i=;i<=edge_num;i++)

     {

         scanf("%d%d%d",&u,&v,&w);

         dp[u][v]=w;

         dp[v][u]=w;

     }

     for(int k=;k<=node_num;k++)

         for(int i=;i<=node_num;i++)

             for(int j=;j<=node_num;j++)

                 if(dp[i][k]!=INF&&dp[k][j]!=INF)    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

     scanf("%d",&ans_num);

     for(int i=;i<=ans_num;i++)

     {

         scanf("%d%d",&u,&v);

         printf("%d->%d: %d\n",u,v,dp[u][v]);

     }

     return ;

 }

6.kruskal(并查集):

 #include <fstream>

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 using namespace std;

 #define EPS 1e-6

 #define ll long long

 #define INF 0x7fffffff

 const int N=;

 const int N2=;

 int node_num,edge_num;

 int node_u[N2],node_v[N2],node_w[N2],p[N],r[N2];

 inline int cmp(const int &a,const int &b)  { return node_w[a]<node_w[b]; }

 inline int find(int x) { return p[x]==x?x:p[x]=find(p[x]); }

 int Kruskal();

 int main(){

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     scanf("%d%d",&node_num,&edge_num);

     for(int i=;i<=edge_num;i++)

         scanf("%d%d%d",&node_u[i],&node_v[i],&node_w[i]);

     printf("%d\n",Kruskal());

     return ;

 }

 int Kruskal(){

     int ans=;

     for(int i=;i<=node_num;i++)   p[i]=i;

     for(int i=;i<=edge_num;i++)   r[i]=i;

     sort(&r[],&r[edge_num+],cmp);

     for(int i=;i<=edge_num;i++){

         int e=r[i];

         int x=find(node_u[e]);

         int y=find(node_v[e]);

         if(x!=y)    ans+=node_w[e],p[x]=y;

     }

     return ans;

 }

7.prim:

 #include <fstream>

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 using namespace std;

 #define EPS 1e-6

 #define ll long long

 #define INF 0x7fffffff

 const int N=;

 int a[N][N],distance_[N],node_num,edge_num;

 bool choose[N];

 int Prim();

 int main(){

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     int u,v,w;

     scanf("%d%d",&node_num,&edge_num);

     for(int i=;i<=node_num;i++)

         for(int j=;j<=node_num;j++)

             a[i][j]=(i==j?:INF);

     for(int i=;i<=edge_num;i++){

         scanf("%d%d%d",&u,&v,&w);

         a[u][v]=w;

         a[v][u]=w;

     }

     printf("%d\n",Prim());

     return ;

 }

 int Prim(){

     int ans=;

     for(int i=;i<=node_num;i++)   choose[i]=,distance_[i]=INF;

     distance_[]=;

     for(int i=;i<=node_num;i++){

         int x=-;

         for(int j=;j<=node_num;j++)

             if(!choose[j])

                 if(x==-)    x=j;

                 else if(distance_[j]<distance_[x])    x=j;

         choose[x]=;

         ans+=distance_[x];

         for(int j=;j<=node_num;j++)

             if(!choose[j]&&a[x][j]!=INF){

                 distance_[j]=min(distance_[j],a[x][j]);

             }

     }

     return ans;

 }

8.prim堆优化:

 #include <fstream>

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 #include <queue>

 using namespace std;

 #define EPS 1e-6

 #define ll long long

 #define INF 0x7fffffff

 const int N=;

 const int N2=;

 int distance_[N],node_num,edge_num;

 int node_first[N],node_next[N2],node_u[N2],node_v[N2],node_w[N2];

 bool choose[N];

 struct cmp{

     bool operator()(const int &a,const int &b) const{

         return distance_[a]>distance_[b];

     }

 };

 priority_queue<int,vector<int>,cmp> pq;

 int prim();

 int main(){

     //freopen("D:\\input.in","r",stdin);

     //freopen("D:\\output.out","w",stdout);

     scanf("%d%d",&node_num,&edge_num);

     for(int i=;i<=node_num;i++)

         node_first[i]=-;

     for(int i=;i<=edge_num;i++){

         scanf("%d%d%d",&node_u[i],&node_v[i],&node_w[i]);

         node_next[i]=node_first[node_u[i]];

         node_first[node_u[i]]=i;

         node_u[i+edge_num]=node_v[i];

         node_v[i+edge_num]=node_u[i];

         node_w[i+edge_num]=node_w[i];

         node_next[i+edge_num]=node_first[node_u[i+edge_num]];

         node_first[node_u[i+edge_num]]=i+edge_num;

     }

     printf("%d\n",prim());

     return ;

 }

 int prim(){

     int ans=;

     for(int i=;i<=node_num;i++)   choose[i]=,distance_[i]=INF;

     distance_[]=;

     pq.push();

     while(!pq.empty()){

         int x=pq.top();

         pq.pop();

         if(choose[x])   continue;

         choose[x]=;

         ans+=distance_[x];

         for(int i=node_first[x];i!=-;i=node_next[i])

             if(!choose[node_v[i]]){

                 if(distance_[node_v[i]]>node_w[i]){

                     distance_[node_v[i]]=node_w[i];

                     pq.push(node_v[i]);

                 }

             }

     }

     return ans;

 }

最新文章

  1. 用机器名访问和用Localhost访问时在IE中的区别（备忘）
  2. Link To Sql简单
  3. 【原】iOS动态性(一)：动态添加属性的方法——关联(e.g. 向Category添加属性)
  4. ubuntu系统 用户进入后命令行只有一个“$” 美元符号
  5. C#5.0 .net 4.5示例
  6. ASP.NET的SEO：HTTP报头状态码---内容重定向
  7. 线段树总结 （转载 里面有扫描线类 还有NotOnlySuccess线段树大神的地址）
  8. 闲置的eSATA接口，会影响Windows 7的启动速度
  9. ilter()和find()的区别
  10. 三类，23种设计模式，速记理解法！PHP
  11. NOTIFYICONDATA结构
  12. java中三种常见内存溢出错误的处理方法
  13. 【TestDirector】常见问题分析
  14. 【SpringMVC】【EasyUI】关于使用EasyUIForm上传文件，返回JsonIE提示下载文件的解决办法！
  15. Python 继承和组合 接口
  16. LeetCode 74. Search a 2D Matrix（搜索二维矩阵）
  17. ●BOZJ 2229 [Zjoi2011]最小割
  18. “百度杯”CTF比赛 九月场---123
  19. SAS数据集推送到sql server 数据库 实现代码段
  20. 25.纯 CSS 创作一个慧星拖尾效果的 loader 动画

热门文章

  1. maven学习（6）-Maven依赖范围
  2. DDA画线算法
  3. FiddlerCoreAPI 使用简介
  4. php multicast多播实现详解
  5. Redis等缓存数据库为什么访问会比较快？
  6. 第12章 网络基础（1）_网络分层和TCP/IP协议族
  7. 自定义ExtJS插件
  8. django的用户认证组件
  9. 中国移动基于ARM/x86服务器的Ceph性能对比
  10. Windows Storage Stack