Dylan's Blog
0%

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);
}

Posted on Edited on In

问题描述

给你在平面直角坐标中的n个点，以及点的高度。两个点的高度之差代表该边的成本，两点的欧几里得距离代表该边的长度(这个可以看成一个完全图)。你需要找出一个成本之和/长度之和最小的生成树。

输入

有多组数据，每组数据第一行包含n(以n=0结束输入)。 接下来n行，每行有包含3个数，表示一个点的横坐标，纵坐标和高度。

输出

输出长度之和/成本之和的最小值，保留小数点后3位。

思路

看到求其中式子的最值，这就是01分数规划问题，这道题就属于01分数规划中比较水的。

首先二分答案，然后将图上所有边权改为成本-(答案* 该边长度)。然后找一棵最小生成树，若它的边权之和小于0则r=mid，否则l=mid。直到答案符合精度要求。

其实还有一种迭代的方法，比二分优很多。还是同样的思路，只是代码作了一点小的该动。

细节

  1. 变量都要用double
  2. 二分精度要1e-6 然而我不知道为什么

代码

二分的代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 1005
#define eps 1e-6
using namespace std;

struct Graph {double cost, dis, val;} mmp[MAXN][MAXN];

int n, x[MAXN], y[MAXN], z[MAXN];
double dis[MAXN];
bool vis[MAXN];

double cal(int i, int j)
{
    return sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

void init()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<i; j++)
        {
            mmp[i][j].dis=mmp[j][i].dis=cal(i, j);
            mmp[i][j].cost=mmp[j][i].cost=abs((double)z[i]-z[j]);
        }
    }
}

double prim(double mid)
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<i; j++)
            mmp[i][j].val=mmp[j][i].val=mmp[i][j].cost-mid*mmp[i][j].dis;
    for(int i=1; i<=n; i++)
            dis[i]=mmp[1][i].val, vis[i]=0;
    double ans=0; 
    dis[1]=0; vis[1]=1;
    for(int i=1; i<n; i++)
    {
        int x=0;
        for(int j=1; j<=n; j++)
            if(!vis[j] && (x==0 || dis[j]<dis[x])) x=j;
        if(x==0) break;
        vis[x]=1; ans+=dis[x];
        for(int j=1; j<=n; j++)
            if(!vis[j]) dis[j]=min(dis[j], mmp[x][j].val);
    }
    return ans;
}

int main()
{
    while(scanf("%d", &n) && n!=0)
    {
        for(int i=1; i<=n; i++) scanf("%d%d%d", &x[i], &y[i], &z[i]);
        init();
        double l=0, r=1000000;
        while(l+eps<r)
        {
            double mid=(l+r)/2;
            if(prim(mid)>=0) l=mid;
            else r=mid;
        }
        printf("%.3f\n", (l+r)/2);
    } 
}

迭代的代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 1005
#define eps 1e-4
using namespace std;

struct Graph {double cost, dis, val;} mmp[MAXN][MAXN], dis[MAXN];

int n, x[MAXN], y[MAXN], z[MAXN];
bool vis[MAXN];

double cal(int i, int j)
{
    return sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

void init()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<i; j++)
        {
            mmp[i][j].dis=mmp[j][i].dis=cal(i, j);
            mmp[i][j].cost=mmp[j][i].cost=abs((double)z[i]-z[j]);
        }
    }
}

double prim(double mid)
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<i; j++)
            mmp[i][j].val=mmp[j][i].val=mmp[i][j].cost-mid*mmp[i][j].dis;
    for(int i=1; i<=n; i++)
        dis[i]=mmp[1][i], vis[i]=0;
    dis[1].val=0; vis[1]=1;
    double c=0, l=0;
    for(int i=1; i<n; i++)
    {
        int x=0;
        for(int j=1; j<=n; j++)
            if(!vis[j] && (x==0 || dis[j].val<dis[x].val)) x=j;
        if(x==0) break;
        vis[x]=1;
        c+=dis[x].cost; l+=dis[x].dis;
        for(int j=1; j<=n; j++)
            if(!vis[j] && dis[j].val>mmp[x][j].val) dis[j]=mmp[x][j];
    } 
    return c/l;
}

int main()
{
    while(scanf("%d", &n) && n!=0)
    {
        for(int i=1; i<=n; i++) scanf("%d%d%d", &x[i], &y[i], &z[i]);
        init();
        double a=0, b=0;
        while(1)
        {
            a=prim(b);
            if(abs(a-b)<eps) break;
            b=a;
        }
        printf("%.3f\n", a);
    } 
}

Posted on Edited on In

问题描述

给你一张含有n个点m条边的无向图，求出一个最小生成树，满足1号节点的度数不超过给定整数s。

输入

第一行给出一个整数m,表示有m条边。 接下来m行，每一行有两个字符串表示节点以及它们之间的距离。 最后一行给出整数s。

输出

输出一行：Total miles driven: xxx xxx 表示最小生成树的边权之和。

思路

其实这个东西说的高大上一点是度限制生成树,但是本身并不难理解。

首先是用常规的Kruskal建一个最小生成树，然后把这棵生成树去掉1号节点。统计有多少个联通块，联通块个数记为t，然后从1号点和每一个联通块连一条最短的边。这样一来我们就得出了一个一号节点度数为t的最小生成树。

如果t大于s，则不存在题目要求的树（当然本题不包含这种情况）。 如果t等于s，则不需要其他操作，直接输出边权之和就好了。 如果t小于s，则我们需要调整这棵树，使它的边权之和更小。

调整这棵树，我们可以改动s-t条边（或者更少）。考虑从1号节点出发的每一条边，设它的到达节点x，边权为z。如果该边不在生成树中，则我们可以找出从1号点到x号点树上路径的最长边，设该边边权为y（这个我们可以通过一次dfs预处理出来)。那么我们可以找出一个节点x，使它的z-y最大。z-y就是这次调整能够减少的最大边权（把最长边去掉，加上从1出发到达x的这条边)。重复这次操作s-t次，就可以得到题目要求的最小生成树。

细节

  1. 如果上文中的z-y为负数，则以后不进行任何操作，输出答案即可
  2. 树和图要分开来存，进行调整时不要搞混了
  3. 反正代码很难打QWQ，思路一定要清晰

代码

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <iostream>
#define MAXN 35
#define INF 0x3f3f3f3f
using namespace std;

int n=1, m, t, s, z, tree[MAXN][MAXN], graph[MAXN][MAXN], ans;
int f[MAXN], min_dis[MAXN], min_to[MAXN];
string x, y;
map <string, int> mmp;
pair<int, int> edge[MAXN*MAXN], maxe[MAXN];

bool CMP(pair<int, int> x, pair<int, int> y)
{
    return graph[x.first][x.second]<graph[y.first][y.second];
}

void init()
{
    mmp["Park"]=1;
    memset(graph, 0x3f, sizeof(graph));
    memset(tree, -1, sizeof(tree));
    memset(min_dis, 0x3f, sizeof(min_dis));
    for(int i=1; i<MAXN; i++) f[i]=i;
}

int find(int x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

void Kruskal()
{
    for(int i=1; i<=n; i++) f[i]=i;
    sort(edge+1, edge+m+1, CMP);
    for(int i=1; i<=m; i++)
    {
        int x=edge[i].first, y=edge[i].second;
        int fx=find(x), fy=find(y);
        if(fx==fy || x==1 || y==1) continue;
        f[fx]=fy;
        tree[y][x]=tree[x][y]=graph[x][y];
        ans+=graph[x][y];
    }
}

void dfs(int x, int fa)
{
    for(int i=2; i<=n; i++)
    {
        if(i==fa || tree[x][i]==-1) continue;
        int u=maxe[x].first, v=maxe[x].second;
        if(tree[u][v]>tree[x][i]) maxe[i]=make_pair(u, v);
        else maxe[i]=make_pair(x, i);
        dfs(i, x);
    }
}


int main()
{
    ios::sync_with_stdio(false);
    init();
    scanf("%d", &m);
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        if(mmp[x]==0) mmp[x]= ++n;
        if(mmp[y]==0) mmp[y]= ++n;
        graph[mmp[x]][mmp[y]]=z;
        graph[mmp[y]][mmp[x]]=z;
        edge[i]=make_pair(mmp[x], mmp[y]);
    }
    scanf("%d", &s);
    Kruskal();
    for(int i=2; i<=n; i++)
    {
        int x=find(i);
        if(min_dis[x]>graph[1][i])
        {
            min_dis[x]=graph[1][i];
            min_to[x]=i;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(min_dis[i]==INF) continue;
        tree[1][min_to[i]]=min_dis[i];
        tree[min_to[i]][1]=min_dis[i];
        ans+=min_dis[i]; t++;
    }
    for(int i=t+1; i<=s; i++)
    {
        int minn=INF, to, u, v;
        memset(maxe, 0, sizeof(maxe));
        dfs(1, -1);
        for(int j=2; j<=n; j++)
        {
            int x=maxe[j].first, y=maxe[j].second;
            if(minn<graph[1][j]-tree[x][y]) continue;
            minn=graph[1][j]-tree[x][y];
            to=j; u=x, v=y;
        }
        if(minn>=0) break;
        tree[1][to]=tree[to][1]=graph[1][to];
        tree[u][v]=tree[v][u]=-1;
        ans+=minn;
    }
    printf("Total miles driven: %d\n", ans);
}