Dylan's Blog
0%

Posted on Edited on In

问题描述

说的简单点就是给你一张n个点m条边的有向图和起点S，终点T。求从S出发到T的第K短路。

输入

第一行n，m。 接下来m行，每行描述一条有向边。 最后一行S，T，K三个数

输出

输出第K短路的长度，如果不存在则输出-1。

思路

这就是K短路的模板题吧。用可持久化左偏树维护自然是不会的。

首先可以考虑用优先队列搜索，类似于上一篇博客中的方法。显然这样的时间复杂度是不符合要求的，于是可以用启发式搜索进行优化。

A* 中的估价函数也不难设计，为了确保正确性，估价函数值应该要比真实值要小，于是估价函数可以设计为从该点到T的最短路。

细节

  1. 如果S==T，要K++。 太毒瘤啦
  2. 要注意K短路不存在的情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
#define MAXN 1005
#define MAXE 100005
using namespace std;

struct Node
{
    int x, dis1, dis2; //dis1实际走过距离，dis2估计总距离
    Node(int a, int b, int c)
    {
        x=a; dis1=b; dis2=c;
    }
    friend bool operator < (Node x, Node y)
    {
        return x.dis2>y.dis2; //小根堆 
    }
};

int n, m, a, b, t, dis[MAXN], S, T, K, ans=INF;
bool vis[MAXN];

struct Graph
{
    int cnt, head[MAXN];
    struct Edge {int next, to, dis;} edge[MAXE];

    void addedge(int from, int to, int dis)
    {
        edge[++cnt].next=head[from];
        edge[cnt].to=to;
        edge[cnt].dis=dis;
        head[from]=cnt;
    }

    void spfa()
    {
        memset(dis, 0x3f, sizeof(dis));
        queue<int> q;
        dis[T]=0; vis[T]=true;
        q.push(T);
        while(!q.empty())
        {
            int x=q.front(); q.pop();
            vis[x]=false;
            for(int i=head[x]; i; i=edge[i].next)
            {
                int to=edge[i].to;
                if(dis[to]<dis[x]+edge[i].dis) continue;
                dis[to]=dis[x]+edge[i].dis;
                if(!vis[to]) q.push(to), vis[to]=true;
            }
        } 
    }

    void Astar()
    {
        int tot=0;
        priority_queue<Node> q;

        if(S==T) K++; //注意！！！ 
        q.push(Node(S, 0, dis[S]));
        while(!q.empty())
        {
            Node top=q.top(); q.pop();
            if(top.x==T)
            {
                tot++;
                if(tot==K) {ans=top.dis1; return;}
            }
            for(int i=head[top.x]; i; i=edge[i].next)
            {
                int dis1=top.dis1+edge[i].dis;
                int dis2=dis1+dis[edge[i].to];
                q.push(Node(edge[i].to, dis1, dis2));
            }
        }
    }

} G1, G2;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &a, &b, &t);
        G1.addedge(a, b, t);
        G2.addedge(b, a, t);
    }
    scanf("%d%d%d", &S, &T, &K);
    G2.spfa();
    G1.Astar();
    if(ans==INF) printf("-1\n"); //K短路可能不存在 
    else printf("%d\n", ans);
}

Posted on Edited on In

问题描述

满足如下条件的序列X被称为“Addition Chains”： 1.$X[1]=1$ 2.$X[m]=n$ 3.$X[1]<X[2]<…<X[m-1]<X[m]$ 4.对于每个k(2<=k<=m)都存在两个整数i,j（i,j可以相等），使得$X[k]=X[i]+X[j]$ 给定一个整数n,找出符合条件长度最短的”Addition Chains”（有SPJ，输出符合要求即可)

输入

有多组数据，每组数据一个数n（n<=100)。以n=0结束输入

输出

每组数据一行，输出长度最短的“addition chains”。

思路

迭代加深搜索应该不难想到，这里就讲一下剪枝。

可以开一个vis数组记录某个数值有没有访问过，这样可以避免重复搜索某个数组。

还有另一个剪枝（但是我没有用），枚举i,j时可以从大到小枚举，这样可以优化搜索顺序，使序列中是数尽快逼近n。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include 
#include 
#include 
#define MAXN 105
using namespace std;

int n, m, num[MAXN];
bool vis[MAXN];

bool dfs(int x)
{
    if(x==m)
    {
        if(num[x]==n) return true;
        else return false;
    }
    for(int i=1; i<=x; i++)
    {
        for(int j=i; j<=x; j++)
        {
            int temp=num[i]+num[j];
            if(temp
int main()
{
    while(scanf("%d", &n) && n)
    {
        for(m=1; ; m++)
        {
            memset(num, 0, sizeof(num));
            memset(vis, 0, sizeof(vis));
            num[1]=1;
            if(dfs(1)) break;   
        }
        for(int i=1; i<=m; i++) printf("%d ", num[i]);
        printf("\n");
    }   
}

Posted on Edited on In

问题描述

有N(1<=N<=1000)个城市和M(1<=M<=10000)条道路，构成一张无向图。在每个城市里面都有一个加油站，不同的加油站的价格不一样。通过每一条道路的油耗就是该道路的边权。你需要回答q(q<=100)个问题,在每个问题中，请计算出油箱容量为C(1<=C<=100)的车子，从起点S开到终点T至少要话多少油钱？

输入

第一行两个数字n,m。 接下来一行n个数字描述每个城市的油价。 接下来m行描述每行描述一条道路。 接下来一行一个数字q。 然后q行描述q个问题。

输出

一共q行，每行输出每个问题的油钱。如果不能到达，输出impossible。

思路

这题的主要思想就是优先队列搜索。我们对于每一个问题都进行一次优先队列BFS。对于每一个状态我们储存3个信息：所在城市，当前油量，当前花费。再用用一个二维数组d记录最少花费。

接下来有两中扩展方式，一是在当前城市加1L油，二是到相邻的城市并且消耗油量。我们不断从堆顶取出花费最少的状态，直到T第一次被取出为止。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAXN 1005
#define MAXE 10005
using namespace std;

int n, m, u, v, dis, e, s, c, Q, cnt, head[MAXN], val[MAXN], d[MAXN][110];

struct Node
{
    int city, fuel, cost;
    Node(int x, int y, int z)
    {
        city=x; fuel=y; cost=z;
    }
    friend bool operator < (Node x, Node y)
    {
        return x.cost>y.cost;
    }
};
struct Edge {int next, to, dis;} edge[MAXE*2];

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void bfs(int s, int e, int v)
{
    priority_queue<Node> q;
    memset(d, 0x3f, sizeof(d));
    d[s][0]=0;
    q.push(Node(s, 0, 0));
    while(!q.empty())
    {
        int x=q.top().city, f=q.top().fuel, c=q.top().cost;
        q.pop();
        if(x==e) {printf("%d\n", c); return;}
        if(f<v && d[x][f]+val[x]<d[x][f+1])
        {
            d[x][f+1]=d[x][f]+val[x];
            q.push(Node(x, f+1, d[x][f+1]));
        }
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to, dis=edge[i].dis;
            if(f>=dis && c<d[to][f-dis])
            {
                d[to][f-dis]=c;
                q.push(Node(to, f-dis, d[to][f-dis]));
            }
        }
    }
    printf("impossible\n");
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &val[i]);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &u, &v, &dis);
        addedge(u+1, v+1, dis);
        addedge(v+1, u+1, dis);
    }
    scanf("%d", &Q);
    for(int i=1; i<=Q; i++)
    {
        scanf("%d%d%d", &c, &s, &e);
        bfs(s+1, e+1, c);
    }
}

Posted on Edited on In

问题描述

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入

第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤64。 第二行为N个用空个隔开的正整数，表示N根小木棍的长度。

输出

仅一行，表示要求的原始木棍的最小可能长度。

思路

依然还是爆搜。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAXN 70
using namespace std;

int n, a[MAXN], ans=INF, sum, cnt;
bool vis[MAXN];

bool CMP(int x, int y) {return x>y;}

bool dfs(int num, int len, int last)
{
    if(num>=cnt) return true;
    if(len==ans) return dfs(num+1, 0, 1);
    int fail=0;
    for(int i=last; i<=n; i++)
    {
        if(vis[i] || len+a[i]>ans || fail==a[i]) continue;
        vis[i]=true;
        if(dfs(num, len+a[i], i+1)) return true;
        fail=a[i]; 
        vis[i]=false;
        if(len==0) return false;
    }
    return false; 
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i]>50) n--, i--;
        else sum+=a[i], ans=min(ans, a[i]);
    }

    sort(a+1, a+n+1, CMP);
    for(; ans<=sum; ans++)
    {
        if(sum%ans!=0) continue;
        cnt=sum/ans;
        memset(vis, 0, sizeof(vis));
        if(dfs(1, 0, 1)) break;
    }
    printf("%d\n", ans);
}

Posted on Edited on In

问题描述

需要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。 我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。 令Q = Sπ 。

请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小（除Q外，以上所有数据皆为正整数）。

输入

有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。

输出

仅一行，是一个正整数S（若无解则S = 0）。

思路

一开始什么思路都没有，然后就手玩了一下样例。样例玩了很久才出来，然后发现玩样例的过程就是个搜索的过程。

所以这道题就可以用爆搜去做，爆搜不难写，但剪枝就没那么容易。首先可以预处理出剩下i层最小的蛋糕体积，储存为minv[i]。如果搜索剩下了i层，但剩余的体积小于minv[i]时，就可以剪去这枝。然后，如果剩余体积/最大半径* 2（即为最大侧面积）大于等于已知的最小侧面积时，也可以剪去这枝。

加上这两个以后，就可以从原来TLE8个点变为0ms了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 20005
#define INF 0x3f3f3f3f
using namespace std;

int n, m, ans=INF, temp, minv[MAXN];

void dfs(int vol, int cnt, int num, int r, int h)
{
    if(cnt==0)
    {
        if(vol==0) ans=min(ans, num);
        return;
    }
    if(2*vol/r+num>=ans || vol<minv[cnt]) return;
    for(int i=r; i>=cnt; i--)
    {
        if(cnt==m) num=i*i;
        temp=min(h, (vol-minv[cnt-1])/(i*i));
        for(int j=temp; j>=cnt; j--) dfs(vol-i*i*j, cnt-1, num+2*i*j, i-1, j-1);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) minv[i]=minv[i-1]+i*i*i;
    dfs(n, m, 0, n, sqrt((double)n));
    if(ans==INF) printf("0\n");
    else printf("%d\n", ans);
}