20220722挨揍记录

今天晕乎乎的，感觉啥也没干啊！

有一天，琪琪想乘坐公交车去拜访她的一位朋友。

由于琪琪非常容易晕车，所以她想尽快到达朋友家。

现在给定你一张城市交通路线图，上面包含城市的公交站台以及公交线路的具体分布。

已知城市中共包含 nn 个车站（编号11~nn）以及 mm 条公交线路。

每条公交线路都是 单向的，从一个车站出发直接到达另一个车站，两个车站之间可能存在多条公交线路。

琪琪的朋友住在 ss 号车站附近。

琪琪可以在任何车站选择换乘其它公共汽车。

请找出琪琪到达她的朋友家（附近的公交车站）需要花费的最少时间。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含三个整数 n,m,sn,m,s，分别表示车站数量，公交线路数量以及朋友家附近车站的编号。

接下来 mm 行，每行包含三个整数 p,q,tp,q,t，表示存在一条线路从车站 pp 到达车站 qq，用时为 tt。

接下来一行，包含一个整数 ww，表示琪琪家附近共有 ww 个车站，她可以在这 ww 个车站中选择一个车站作为始发站。

再一行，包含 ww 个整数，表示琪琪家附近的 ww 个车站的编号。

输出格式

每个测试数据输出一个整数作为结果，表示所需花费的最少时间。

如果无法达到朋友家的车站，则输出 -1。

每个结果占一行。

数据范围

n≤1000,m≤20000n≤1000,m≤20000,
1≤s≤n1≤s≤n,
0<w<n0<w<n,
0<t≤10000<t≤1000

输入样例：

5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1

输出样例：

1
-1

这道题目是个反向建图的过程，因为我们如果add(a, b, c)代表的是以a向b建立一条边，如果这样的话，我们无法求出以朋友所在汽车站的最短路，我们只能每次只能分别求出以自己家为原点的最短路，但是如果反过来的话，也就是说以朋友的家作为起点，让朋友来找自己，反向建边，这样的话是不是就是说明可以只跑一次dijkstra就可以解决问题我分别贴上两种代码，第一种是正向建边，会超时第二种就ac了

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1010, M = 40010, INF = 0x3f3f3f3f;

typedef pair<int,int> PII;
int h[N], e[M], ne[M], w[M],  idx;
bool st[N];
int dist[N];
int n, m, S;

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void dijkstra(int start) {
	memset(st, 0, sizeof st);
        memset(dist, 0x3f, sizeof dist);
        dist[start] = 0;
        priority_queue<PII, vector<PII>, greater<PII> > heap;
        heap.push({dist[start], start});
        
        while (heap.size()) {
            auto t = heap.top();
            heap.pop();
            int ver = t.second;
            if (st[ver]) continue;
            st[ver] = true;
            for (int i = h[ver]; ~i; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[ver] + w[i]) {
                    dist[j] = dist[ver] + w[i];
                    heap.push({dist[j], j});
                }
            }
        }
}
int main() {
    while (cin >> n >> m >> S) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
        }
        
        
        int s;
        cin >> s;
        int res = INF;
        while (s --) {
            int a;
            cin >> a;
            dijkstra(a);
            res = min(res, dist[S]);
        }
        if (res == 0x3f3f3f3f) puts("-1");
        else cout << res << endl;
    }    
}

 这是ac的

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1010, M = 40010, INF = 0x3f3f3f3f;

typedef pair<int,int> PII;
int h[N], e[M], ne[M], w[M],  idx;
bool st[N];
int dist[N];
int n, m, S;

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int main() {
    while (cin >> n >> m >> S) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add(b, a, c);
        }
        
        memset(st, 0, sizeof st);
        memset(dist, 0x3f, sizeof dist);
        dist[S] = 0;
        priority_queue<PII, vector<PII>, greater<PII> > heap;
        heap.push({dist[S], S});
        
        while (heap.size()) {
            auto t = heap.top();
            heap.pop();
            int ver = t.second;
            if (st[ver]) continue;
            st[ver] = true;
            for (int i = h[ver]; ~i; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[ver] + w[i]) {
                    dist[j] = dist[ver] + w[i];
                    heap.push({dist[j], j});
                }
            }
        }
        int s;
        cin >> s;
        int res = INF;
        while (s --) {
            int a;
            cin >> a;
            res = min(res, dist[a]);
        }
        if (res == 0x3f3f3f3f) puts("-1");
        else cout << res << endl;
    }    
}

先写这些，我再补充

后续来了，又补充了超级源点的思想，可以将自己连接向这个源点， 将自己可以出发的点加入队列，然后将他们的dist设置为0就好了，我们只需要做一次最短路算法就好了，不需要反向加边。

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1010, M = 40010, INF = 0x3f3f3f3f;

typedef pair<int,int> PII;
int h[N], e[M], ne[M], w[M],  idx;
bool st[N];
int dist[N];
int n, m, S;
int q[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int main() {
    while (cin >> n >> m >> S) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
        }
        int tt = 0, hh = 0;
        memset(st, 0, sizeof st);
        memset(dist, 0x3f, sizeof dist);
        int s;
        cin >> s;
        int res = INF;
        while (s --) {
            int a;
            cin >> a;
            dist[a] = 0;
            st[a] = true;
            q[tt ++] = a;

        }

        while (hh != tt) {
            int u = q[hh ++];
            if (hh == N) hh = 0;
            st[u] = false;

            for (int i = h[u]; ~i; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[u] + w[i]) {
                    dist[j] = dist[u] + w[i];
                    if (!st[j]) {
                        q[tt ++] = j;
                        if (tt == N) tt = 0;
                        st[j] = true;
                    }
                }
            }
        }
        if (dist[S] == 0x3f3f3f3f) puts("-1");
        else printf("%d\n", dist[S]);
    }    

    return 0;
}

继续更新了┗|｀O′|┛ 嗷~~

这是一道flyod的题目，反正大开眼界哈哈哈

1125. 牛的旅行

农民John的农场里有很多牧区，有的路径连接一些特定的牧区。

一片所有连通的牧区称为一个牧场。

但是就目前而言，你能看到至少有两个牧区不连通。

现在，John想在农场里添加一条路径（注意，恰好一条）。

一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是最短的距离）。

考虑如下的两个牧场，每一个牧区都有自己的坐标：

图 1 是有 5 个牧区的牧场，牧区用“*”表示，路径用直线表示。

图 1 所示的牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E，它们之间的最短路径是 A-B-E。

图 2 是另一个牧场。

这两个牧场都在John的农场上。

John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。

注意，如果两条路径中途相交，我们不认为它们是连通的。

只有两条路径在同一个牧区相交，我们才认为它们是连通的。

现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，所有牧场（生成的新牧场和原有牧场）中直径最大的牧场的直径尽可能小。

输出这个直径最小可能值。

输入格式

第 1 行：一个整数 N, 表示牧区数；

第 2 到 N+1 行：每行两个整数 X,Y， 表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。

第 N+2 行到第 2*N+1 行：每行包括 N 个数字 ( 0或1 ) 表示一个对称邻接矩阵。

例如，题目描述中的两个牧场的矩阵描述如下：

  A B C D E F G H 
A 0 1 0 0 0 0 0 0 
B 1 0 1 1 1 0 0 0 
C 0 1 0 0 1 0 0 0 
D 0 1 0 0 1 0 0 0 
E 0 1 1 1 0 0 0 0 
F 0 0 0 0 0 0 1 0 
G 0 0 0 0 0 1 0 1 
H 0 0 0 0 0 0 1 0

输入数据中至少包括两个不连通的牧区。

输出格式

只有一行，包括一个实数，表示所求答案。

数字保留六位小数。

数据范围

1≤N≤1501≤N≤150,
0≤X,Y≤1050≤X,Y≤105

输入样例：

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

输出样例：

22.071068

 首先介绍一下变量：

typedef pair<double,double> PDD;

char map[N][N];  这个是储存原始的地图
double g[N][N]; 这个是用邻接矩阵存储距离的
PDD store[N]; 这个是一开始输入坐标存储坐标的
double max1[N];这个是距离这个点最远的距离是多少

题目的难点，怎么加边

首先我们考虑的是用flyod套用板子，这样的话如果对于i和j两个点，如果他们的距离大于我们设置的INF / 2的话是不是就说明他们之间没有最短路，可以在i和j之间建立一条边，所以我们只需要找到距离i最远的点和距离j最远的点， 得到的数值就是max1[i] + max1[j] + i和j地图上的距离， 这也是我们求得的直径！

我们要找的是最大值最小（真矛盾hhhh

我们先求ans2，代表的是不加边时的直径最大值

然后我们对于所有点进行遍历，如果两个点之间的距离大于INF / 2就去和ans比较一下取最大，

最后和ans2取个最小

另外注意初始化的大小，double，自信点开大点

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
const int N = 200, M = N *N * 2;
const double INF = 1e20;
typedef pair<double,double> PDD;

char map[N][N];
double g[N][N];
PDD store[N];
double max1[N];

double get_dis(PDD a, PDD b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

int main() {
    int n, m;
    cin >> n;
    for (int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;
        store[i] = {x, y};
    }
    
    for (int i = 0; i < n; i++) cin >> map[i];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) map[i][j] = 0;
            else if (map[i][j] == '1') {
                g[i][j] = get_dis(store[i], store[j]);
            } else {
                g[i][j] = INF;
            }
        }  
    }
    for (int k = 0; k < n; k++){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);        
            }
        }
    }
    double ans2 = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] < INF / 2) {
                max1[i] = max(max1[i], g[i][j]);
            }        
        }
        ans2 = max(ans2, max1[i]);
    }
    double ans = INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] > INF / 2) {
                ans = min(ans, max1[i] + max1[j] + get_dis(store[i], store[j]));
            }
        }
    }
    
    printf("%.6lf", max(ans, ans2));
    return 0;
}

再来一题

给定一张 LL 个点、PP 条边的有向图，每个点都有一个权值 f[i]f[i]，每条边都有一个权值 t[i]t[i]。

求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

注意：数据保证至少存在一个环。

输入格式

第一行包含两个整数 LL 和 PP。

接下来 LL 行每行一个整数，表示 f[i]f[i]。

再接下来 PP 行，每行三个整数 a，b，t[i]a，b，t[i]，表示点 aa 和 bb 之间存在一条边，边的权值为 t[i]t[i]。

输出格式

输出一个数表示结果，保留两位小数。

数据范围

2≤L≤10002≤L≤1000,
2≤P≤50002≤P≤5000,
1≤f[i],t[i]≤10001≤f[i],t[i]≤1000

输入样例：

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

输出样例：

6.00

01分数规划问题， 

我主要是不太会用md编写，然后就大体描述一下把，

首先看到分数最大，考虑二分，然后根据给的数据范围，考虑二分的边界，然后对于公式进行转化，最后可以把∑提取出来，这样的话我们就可以把点权值加入边上，保证∑（wf[i] - mid *wt[i]) > 0， 也就是这一条环上的∑（wf[i] - mid *wt[i])为正值，最后也就是求存在正环就可以让左边界变为mid， 最后输出边界即可

//其实我感觉我还不是很通透，但是大致上理解了 

写一下代码吧