图论周结束了。时间过得真是快啊！一周一周地，就溜走了。

下面写一下这周的收获吧。

最短路问题：

（1）dijkstra算法

          用vector开邻接表形式存储，利用优先队列优化：

#include<queue>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

const int max_d=3000+5;
const int max_dis=99999999;

struct Edge{
    int to,dis;
    Edge(int to,int dis){
        this -> to = to;
        this -> dis = dis;
    }
};
int t;
int n,m,k;
int a,b,c;
int d[max_d];
typedef pair<int,int>P;
vector<Edge>G[max_d];

void dijkstra(){
    fill(d+1,d+1+n,max_dis);             //存储最短路径，初始化为无穷大
    d[n]=0;
    priority_queue<P,vector<P>,greater<P> >q; //最小优先
    while(q.size())   q.pop();               //清空队列
    q.push(P(0,n));
    while(q.size()){
        P p=q.top(); q.pop();
        int v=p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<G[v].size();i++){
            Edge& e=G[v][i];
            if(d[e.to]>d[v]+e.dis){
                d[e.to]=d[v]+e.dis;
                q.push(P(d[e.to],e.to));
            }
        }
    }
}

          以点为基准，对边进行更新，最多更新n-1次。如果其中某一次没有一条边更新了，也就可以跳出了。

        int flag;
        for(int i=1;i<=N-1;i++)
        {
            flag=1;
            for(int j=1;j<=k;j++)
            {
                if(dis[edge[j].e]>dis[edge[j].s]+edge[j].w)
                {
                    dis[edge[j].e]=dis[edge[j].s]+edge[j].w;
                    flag=0;
                }
            }if(flag) break;
        }

        flag=0;
        for(int i=1;i<=k;i++)
        {
            if(dis[edge[i].e]>dis[edge[i].s]+edge[i].w)
            {
                flag=1;break;
            }
        }

#include<map>
#include<queue>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int max_e=10000+5;
const int max_dis=99999999;
const int max_d=100+5;
typedef pair<int,int>P;
struct Edge{
    int to,dis;
    Edge(int to,int dis){
        this -> to = to;
        this -> dis = dis;
    }
};

int n,m;
int a,b,c;
int d[max_d];
int vis[max_d];
vector<Edge>G[max_d];

void spfa(){
    fill(vis,vis+n+1,0);
    fill(d+1,d+1+n,max_dis);
    queue<int>q;
    d[1]=0;
    vis[1]=1;
    q.push(1);
    while(q.size()){
        int p=q.front(); q.pop();
        vis[p]=0;
        for(int i=0;i<G[p].size();i++){
            Edge& e=G[p][i];
            if(d[e.to]>d[p]+e.dis){
                d[e.to]=d[p]+e.dis;
                if(!vis[e.to]){
                    vis[e.to]=1;
                    q.push(e.to);
                }
            }
        }
    }
}

#include<map>
#include<queue>
#include<vector>
#include<string>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int max_e=10000+5;
const int max_dis=99999999;
const int max_d=100+5;
typedef pair<int,int>P;
struct Edge{
    int to,dis;
    Edge(int to,int dis){
        this -> to = to;
        this -> dis = dis;
    }
};

int n,m;
int a,b,c;
int d[max_d];
int vis[max_d];        //记录顶点是否在队列中，SPFA算法可以入队列多次
int sum[max_d];       //记录顶点的入队次数
vector<Edge>G[max_d];

bool spfa(int s){
    fill(vis,vis+n+1,0);
    fill(sum,sum+n+1,0);
    fill(d+1,d+1+n,max_dis);
    queue<int>q;
    d[s]=0;
    sum[s]++;
    vis[s]=1;
    q.push(s);
    while(q.size()){
        int p=q.front(); q.pop();
        vis[p]=0;
        for(int i=0;i<G[p].size();i++){
            Edge& e=G[p][i];
            if(d[e.to]>d[p]+e.dis){
                d[e.to]=d[p]+e.dis;
                if(!vis[e.to]){      //当该点已经在队列中就不要重复入队了
                    vis[e.to]=1;
                    sum[e.to]++;
                    if(sum[e.to]>=n) //当一个点入队次数大于等于n时说明出现了负环
                        return true;
                    q.push(e.to);
                }
            }
        }
    }return false;
}

          请记住这段代码！！！

for(int k=1;k<=m;k++)
    {
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=m;j++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }

        prim算法没有去学，之后一定补回来。学了kruskal算法，感觉还挺好用的。

        首先强调一个有用的东西--并查集。其压缩路径代码很短却很受用：

int father[50002],a,b,m,n,p;
int find(int x)
{
    if(father[x]!=x)
        father[x]=find(father[x]);
/*
x代表例题中的人，father[x]中所存的数代表这一集合中所有人都与一个人有亲戚关系
相当于例题中第一个集合所有的元素都与第一个元素有亲戚关系
搜索时只要找元素所指向的father[x]=x的元素(即父元素)
然后比较两个元素的父元素是否相同就可以判断其关系
*/
    return father[x];
}

       kruskal算法

              简单来说就是选“边”，对给出的边进行从小到大排序，然后每次取最小的边，端点没有关系即可入树，找到m-1条边才算构成 了最小生成树。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int max_e=10000+5;
struct Edge
{
    int u,v;
    int cost;
}e[max_e];
bool cmp(Edge a,Edge b)
{
    return a.cost<b.cost;         //按边从小到大排序
}
int father[105];
int find(int x)               //并查集压缩路径
{
    if(x!=father[x]) father[x]=find(father[x]);
    return father[x];
}

int main()
{
    int N,M;
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        if(N==0) break;
        for(int i=0;i<N;i++)
            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].cost);
        sort(e,e+N,cmp);
        for(int i=1;i<=M;i++)      //初始化
            father[i]=i;
        int ans=0;
        int point=0;
        for(int i=0;i<N;i++)
        {
            int x=find(e[i].u);
            int y=find(e[i].v); 
            if(x!=y){
                ans+=e[i].cost;
                point++;
                father[y]=x;
            }
        }
        if(point<M-1) printf("?\n");   //如果找到的边数量小于M-1说明没有构成最小生成树
        else          printf("%d\n",ans);
    }return 0;
}