ACM恢复训练（一）最短路

好久没有写博客了，今天配好了sublime，打算正式启航吧

找到了之前的自己的CSP复习模板，QQ邮箱真是个神奇的地方，什么邮件附件都能找回

自认为自己不是个创新型人才，所以需要不断学习来渴望上天一点恩赐QAQ

不贫了，第一个选择复习的是图论-最短路

一、dijstra算法（nlogn)

重新再来复习这个算法，其基本思想还是不太难理解的

重点是一个dp的思想，转移状态dis[from]->dis[to]的变化

肯定用if语句进行判断

建边就是常规操作，然后从队列里面找到优先级高的

就是队列里面当下已经访问的点中距离最小的，开始遍历他的出边

直到队列中不再有点

#include<bits/stdc++.h>
using namespace std;
#define I inline
#define INF 0x7f7f7f7f
const  int N=4e5+7;
int cnt,m,n,ans,F;
int head[N],dis[N];
struct edge{
    int dist,nx,to;
} e[N];
struct node{
    int pos,dist;
    bool operator<(const node &x) const{
        return dist>x.dist;
    }
};
bool vis[N];
priority_queue<node> que;


void dij(int pos){
    for (int i=1;i<=N;i++) dis[i]=INF;
    que.push((node){pos,0});dis[pos]=0;
    while (!que.empty()){
        node tmp=que.top();que.pop();
        int x=tmp.pos;
        if (vis[x]) continue; vis[x]=true;
        for (int i=head[x];i;i=e[i].nx){
            int y=e[i].to;
            if (dis[y]>dis[x]+e[i].dist) {
                dis[y]=dis[x]+e[i].dist;
                if (!vis[y]) que.push((node){y,dis[y]});
            }
        }
    }
}
void add_edge(int x,int y,int dis){
    cnt++;e[cnt].nx=head[x],e[cnt].to=y,e[cnt].dist=dis;head[x]=cnt;
}



int main(){
    scanf("%d%d%d",&n,&m,&F);
    while (m--){
        int s,t,u;scanf("%d%d%d",&s,&t,&u);
        add_edge(s,t,u);
    }
    dij(F);
    for (int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    return 0;
}

二、SPFA算法（VE）

SPFA算法就是对bellman-Ford算法的队列优化

既然我们对于每个能到达的边都要松弛那么我们可以判断是否在队列里面

来减少操作的次数，虽然没有dij那么强大的算法复杂度但是可以用来判断负权回路

这也着实是其一大特点

#include<bits/stdc++.h>
using namespace std;
const int INF=0x7f7f7f7f;
const int N=1e5+7;
int dis[N],head[N];
struct edge{
    int nx,to,dist;
} e[N<<1];
int m,n,cnt,ans;
queue<int> que;
bool inque[N];

void add_edge(int x,int y,int dis){
    cnt++;e[cnt].dist=dis;e[cnt].nx=head[x];e[cnt].to=y;head[x]=cnt;
}
void SPFA(int pos){
    for (int i=1;i<=n;i++){
        dis[i]=INF;inque[i]=false;
    }
    que.push(pos);inque[pos]=true;dis[pos]=0;
    while (!que.empty()){
        int x=que.front();inque[x]=false;que.pop();
        for (int i=head[x];i;i=e[i].nx){
            int y=e[i].to;
            if (dis[y]>dis[x]+e[i].dist){
                dis[y]=dis[x]+e[i].dist;
                if (!inque[y]) {inque[y]=true;que.push(y);}
            }
        }
    }
}

int main(){
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
    }
    SPFA(1);
    for (int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}

 三、差分约束算法

主要是用来解决一群不等式同时成立的问题的情况的
例如说：
x1-x2<=c1 这样的话需要x1->x2连一条权值为-c1的边

原理来自于dis[x]<=dis[y]+w；这样的最长路不等式

几种情况：
1.如果图上存在负环（求最短路），则说明无法满足所有不等式成立的情况
2.求出最短路后，则是原来不等式的对应的一个解x[i]=dis[i]并且这个解是最小解且大于零

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;

int m,n,cnt;
int head[N],dis[N],in[N];
bool vis[N];
struct edge{
    int nx,to,dis;
} e[N];

void add_edge(int x,int y,int dis){
    cnt++;e[cnt].nx=head[x];e[cnt].to=y;e[cnt].dis=dis;head[x]=cnt;
}
bool SPFA(int pos){
    for (int i=0;i<=n;i++) {dis[i]=-1;vis[i]=false;}
    queue<int> que;que.push(pos);vis[pos]=true;dis[pos]=0;in[pos]=1;
    while (!que.empty()){
        int x=que.front();que.pop();vis[x]=false;
        for (int i=head[x];i;i=e[i].nx){
            int y=e[i].to;
            if (dis[y]<dis[x]+e[i].dis){
                dis[y]=dis[x]+e[i].dis;
                if (!vis[y]){
                    vis[y]=true;que.push(y);
                    in[y]++;
                    if (in[y]>n) return false;
                }
            }
        }
    }
    return true;
}

int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,-z);
    }
    for (int i=1;i<=n;i++) add_edge(0,i,0);
    if (!SPFA(0)) {printf("NO");return 0;}
    for (int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}