Dylan's Blog
0%

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

Posted on Edited on In

问题描述

Farmer John想把牛奶送到T个城镇 (1 <= T <= 25,000)，编号为1-T。这些城镇之间通过R条道路 (1 <= R <= 50,000，编号为1到R) 和P条航线 (1 <= P <= 50,000，编号为1到P) 连接。每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T)，花费为C_i。 对于道路，0 <= C_i <= 10,000;然而航线的花费很神奇，花费C_i可能是负数(-10,000 <= C_i <= 10,000)。道路是双向的，可以从A_i到B_i，也可以从B_i到A_i，花费都是C_i。然而航线与之不同，只可以从A_i到B_i。 如果有一条航线可以从A_i到B_i，那么保证不可能通过一些道路和航线从B_i回到A_i。他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

输入

第1行：四个空格隔开的整数: T, R, P, and S 第2到R+1行：三个空格隔开的整数（表示一条道路）：A_i, B_i 和C_i 第R+2到R+P+1行：三个空格隔开的整数（表示一条航线）：A_i, B_i 和 C_i

输出

第1到T行：从S到达城镇i的最小花费，如果不存在输出”NO PATH”。

思路

最早一看以为是一个裸的SPFA，于是很愉快的花十分钟码完了，结果T了两个点。果然BZOJ没有这么水的题QWQ原来数据构造好了要卡SPFA。

正解的思路是：由于航线是单向且保证了不可能通过一些道路和航线回到本身，所以说这个图由是很多个正边权无向边组成的联通块被一些可能有负权的有向边连接起来。

这样的话就可以把每个联通块视为一个点，可以按照拓扑序在每个联通块内跑Dijkstra最后求出答案。由于一些玄学的错误，这个代码我调了整整一天还没有调出来。最后草率的在SPFA上加了SFL优化A了这题。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define MAXN 25005
#define MAXE 100005
#define INF 0x3f3f3f3f
using namespace std;

struct Edge {int next, to, dis;} edge[MAXE*2];

int t, r, p, s, a, b, c, cnt, head[MAXN], dis[MAXN];
bool vis[MAXN];

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()
{
    deque<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    vis[s]=true; dis[s]=0;
    q.push_back(s);
    while(!q.empty())
    {
        int x=q.front(); q.pop_front();
        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)
            {
                dis[to]=dis[x]+edge[i].dis;
                if(vis[to]) continue;
                vis[to]=true;
                if(dis[to]<dis[q.front()]) q.push_front(to);
                else q.push_back(to);
            }
        }
    }
}

int main()
{
    scanf("%d%d%d%d", &t, &r, &p, &s);
    for(int i=1; i<=r; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        addedge(b, a, c);
    }
    for(int i=1; i<=p; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
    }
    spfa();
    for(int i=1; i<=t; i++)
    {
        if(dis[i]==INF) printf("NO PATH\n");
        else printf("%d\n", dis[i]);
    }
}

Posted on Edited on In

问题描述

给你N个变量，M个不等式(形如x<y)，需要你判断：1.他们是否矛盾 2.若无矛盾，则是否能确定每个变量的关系 3.若能，则求出用前x个不等式就能求出关系x的最小值。

输入

有多组数据，每组数据第一行n,m。当n=0且m=0时输入结束。 下面m行给出m个不等式。

输出

对于每组数据输出下面三句话中的一句： Sorted sequence determined after xxx relations: yyy…y. Sorted sequence cannot be determined. Inconsistency found after xxx relations.

思路

求这些约束关系的当然是用拓扑排序啦。

拓扑排序时如果有两个或以上的点入度为0，则这个序列不能确定，如果没有一个入度为0的点，则这是矛盾的。然后每增加一个不等式时都进行一遍拓扑排序。

考虑输出，我们开一个数组记录这些变量，拓扑排序时按照拓扑序将这些变量加进数组，这样数组内的元素就一定时从大到小的。

细节

  1. 要注意输出格式
  2. 如果成功了，但以后的关系出现矛盾依然认为它成功
  3. 每一组数据要把输入读完

代码

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 30
using namespace std;

int n, m, tag, top, pos, cnt, flag1, flag2, q[MAXN], deg[MAXN], temp[MAXN];
bool f[MAXN][MAXN];
char t[5];

int topo()
{
    top=0; flag2=1;
    for(int i=1; i<=n; i++) temp[i]=deg[i];
    for(int i=1; i<=n; i++)
    {
        cnt=0;
        for(int j=1; j<=n; j++)
            if(temp[j]==0) {cnt++; pos=j;}
        if(cnt==0) return 0;
        if(cnt>1) flag2=-1;
        q[top++]=pos;
        temp[pos]=-1;
        for(int j=1; j<=n; j++)
            if(f[pos][j]==1) temp[j]--;
    }
    return flag2;
}

int main()
{
    scanf("%d%d", &n, &m);
    while(n!=0 && m!=0)
    {
        memset(f, 0, sizeof(f));
        memset(deg, 0, sizeof(deg));
        flag1=false;
        for(int i=1; i<=m; i++)
        {
            scanf("%s", t);
            if(flag1) continue;
            int x=t[0]-'A'+1, y=t[2]-'A'+1;
            f[x][y]=true; deg[y]++;
            tag=topo();
            if(tag==0)
            {
                printf("Inconsistency found after %d relations.\n",i);
                flag1=1;
            }
            if(tag==1)
            {
                printf("Sorted sequence determined after %d relations: ",i);
                for(int j=0; j<n; j++) printf("%c", q[j]+'A'-1);
                printf(".\n");
                flag1=1;
            }
        }
        if(!flag1) printf("Sorted sequence cannot be determined.\n");
        scanf("%d%d", &n, &m);
    }
}