Skip to content

Latest commit

 

History

History
172 lines (140 loc) · 5.21 KB

ACOJ-12330-最短路.md

File metadata and controls

172 lines (140 loc) · 5.21 KB
Raw

title: ACOJ 12330 最短路 categories: DFS tags: [代码,编程] date: 2019-03-17 19:55:00

  • 摘要:这题对我启发颇深啊，以后敲代码前要多想想。

题目

Codeaha

<iframe height=500px src="https://www.acoj.com/problems/12330" width="100%"></iframe> 
给出一张N个点的无向图，问从1到N最多有可以画出多少条互不相交的路径，使得这些路径都是1到N的最短路。
在本题中，路径不相交的定义是：两条路径没有使用同一条边。
输入格式:

第一行包括两个整数n，m，代表点的个数和边的个数。
接下来m行，每行包括三个整数a，b，v，代表从a到b有一条距离为v的无向边。
输出格式:

输出一个数字，代表最多的互不相交的最短路的条数。
限制:

对于40%的数据，n，m<=10。
对于80%的数据，n，m<=100。
对于100%的数据，n，m<=1000，0<=v<=100
样例 1 :

输入:
3 3
1 2 1
1 3 1
2 3 1
输出:
1

思路

  • 看到这一题,首先想到的是SPFA扫出最短路长度，然后就放弃去做下一题了

网络流？？

  • 当我做完其他题目的一半时，想到了使用网络流可能是对算法的不理解吧，这一题用网络流根本无法解得，因为这不是流量问题，遇到需要使用同一条边时，不可能像网络流那样退还之前路径的最小值，简而言之:路是有连续的，两条相反路径不能抵消，流量是没有这个性质的，相反方向的流量是可以抵消的，于是该方案领盒饭。

DFS+增广路

  • 想到这个方法很自然吗！DFS扫出1到N长度为SPFA算出的最短长度。如果以后有边需要使用某一条边的话，使用增广路的思想，让之前使用这一条边的路径重新找媳妇。

直接DFS

  • 上面一种写到一半，忽然意识到不对，我为什么需要增广路呢？假设第k1次DFS顺利完成，使用了N1顶点，那么从N1到重点的路径必定有至少一条是最短路里包含的！！！如果我需要在k2次DFS时使用这一条路径，且没有N1发出的另一条等长度路径，那么增广必定失败，如果有，那么k2次DFS可以直接使用这一路径证毕。
  • 所以，我们只需要不停DFS直到没有新路径产生。

代码

#include <cstdio>
#include <bits/stdc++.h>
#include <ctime>

using namespace std;
int n,m,ans;
int T;
int head[2002],ver[2002],edge[2002],Next[2002],d[2002];
bool use[2002];
bool v[2002];
int tot;
int mem;
vector <int > line[1001];
int linetail;
queue<int > q;

int a,b,vv,len;
void SPFA()//SPFA算法，详见:https://byhablog-1252071452.cos-website.ap-shanghai.myqcloud.com/2019/02/26/algorithmtips000/#SPFA-%E5%8D%95%E6%BA%90
{
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    d[1] = 0;
    v[1] = 1;
    q.push(1);
    while(q.size())
    {
        int x = q.front();
        q.pop();
        v[x] = 0;
        for(int i = head[x]; i != 0; i=Next[i])
        {
            int y = ver[i];
            int z = edge[i];
            if(d[y]>d[x]+z)
            {
                d[y] = d[x] + z;
                if(!v[y])
                {
                    q.push(y);
                    v[y] = 1;
                }
            }
        }
    }
}
void add(int x,int y,int z)//邻接表,详见:https://byhablog-1252071452.cos-website.ap-shanghai.myqcloud.com/2019/02/26/algorithmtips000/#SPFA-%E5%8D%95%E6%BA%90
{
    ver[++tot] = y;
    edge[tot] = z;
    Next[tot] = head[x];
    head[x] = tot;
}
void DFS(int x,int step){
    if(x == n){//如果到了n顶点
        if(step>len){//路径超长
            mem = 2;//状态更改为2
            return ;//返回
        }
        ans++;//路径为最短路
        mem = 1;//状态更改为1，为了把使用的边打标

        return ;
    }
    if(step>=len){//没到n顶点而路径超长一样炸回家,单程机票
        return ;
    }
    for(int i = head[x];i!=0;i=Next[i]){//邻接表扫边

        if(!use[i]){//i号顶点是否被使用,false为没有被使用,true为被使用
            use[i] = true;//先将路径标记为使用
            DFS(ver[i],step+edge[i]);//进行下一步的扫边
            if(mem == 1)//扫到了最短路,不将标记点复原为false
                return ;
            use[i] = false;//路径超长或者路径超长^_^

        }
    }
    return ;
}


int main()
{

    cin>>n>>m;

    for(int i=1; i<=m; i++)//加边入邻接表,注意是无向图，使用scanf而非cin可明显增加速度
    {
        scanf("%d%d%d",&a,&b,&vv);
        add(a,b,vv);
        add(b,a,vv);
    }

    T = clock();//这里是超时保险丝,超时自动炸机
    SPFA();//SPFA扫最短路
    len = d[n];//将最短路存入len中

    while(true){
        if(T<clock()-920)//超时炸机
            break;
        mem = 0;//状态变量
        DFS(1,0);
        if(mem == 0||mem == 2)//0为没有扫到路径，2为路径过长，在这里相当于没有扫到路径，其实可以将上面mem = 2 改为mem = 1或者直接删去,不影响，只是我懒得删除。
           break;
    }
    cout<<ans;
    return 0;
}