Dylan's Blog
0%

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

Posted on Edited on In

问题描述

大意就是给你一个无向图，求出它的最小环。 并输出最小环上的点。（会有SPJ）

输出

第一行n(n<=100), m(m<=10000)。表示有n个点，m条边。 接下来m行，每一行描述一条边。

输出

输出最小环上的所有节点

思路

求最小环是用Floyd的方法。

我们按顺序枚举所有点，再枚举与该点相邻的点对。枚举点对时，我们可以不需要考虑编号比该点大的点，因为编号比它大的点在后面会被枚举到，会包含这种情况。环的长度就是该点到点对的距离与点对之间的距离之和。

接下来考虑输出环上的点。记录路径感觉很难，于是膜了一下书上的做法。每进行一次松弛操作时就记录一下。环上的点就是点对之间的最短路径上的点和该点对。可以递归下去找最短路径上的点，有点像记录DP方案。(似乎有点难讲清楚，代码还是比较好懂的)。

细节

  1. 小心有重边。
  2. 枚举完点对之后不要忘记Floyd更新点之间的距离
  3. 更新ans时一点要开longlong (代码38行)
  4. 记录路径时递归不要弄错了
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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define MAXN 105
#define INF 0x3f3f3f3f
using namespace std;

int n, m, x, y, z, ans=INF, mmp[MAXN][MAXN], dis[MAXN][MAXN], f[MAXN][MAXN];
vector<int> path;

void find(int i, int j)
{
    if(!f[i][j]) return;
    find(i, f[i][j]);
    path.push_back(f[i][j]);
    find(f[i][j], j);
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(mmp, 0x3f, sizeof(mmp));
    memset(dis, 0x3f, sizeof(dis));
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        if(mmp[x][y]<z) continue;
        mmp[x][y]=mmp[y][x]=z;
        dis[x][y]=dis[y][x]=z;
    }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<k; i++)
            for(int j=i+1; j<k; j++)
            {
                if(ans>(long long)dis[i][j]+mmp[i][k]+mmp[k][j])
                {
                    path.clear();
                    path.push_back(i);
                    find(i, j);
                    path.push_back(j);
                    path.push_back(k);
                    ans=dis[i][j]+mmp[i][k]+mmp[k][j];
                }
            }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                if(dis[i][j]>dis[i][k]+dis[k][j])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                    f[i][j]=k;
                }
            }
    }
    if(ans==INF) printf("No solution.");
    else for(int i=0; i<path.size(); i++) printf("%d ", path[i]);
}