牛的旅行https://www.acwing.com/problem/content/1127/ 求两个连通块连接后最大直径 (可能是连接之前的直径,可能是连接之后的最大值) 1.如果能到达 连接两个点的距离 建图 2.建图后floyd 3.取dm
求两个连通块连接后最大直径 (可能是连接之前的直径,可能是连接之后的最大值)
1.如果能到达 连接两个点的距离 建图
2.建图后floyd
3.取dmin
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 155;
const double INF = 1e20;
int n;
PDD q[N];
double d[N][N];
double maxd[N];
char g[N][N];
double get_dist(PDD a, PDD b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;//输入点对的横纵坐标
for (int i = 0; i < n; i ++ ) cin >> g[i];//存领接矩阵
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if (i == j) d[i][j] = 0;//到自己距离为0
else if (g[i][j] == '1') d[i][j] = get_dist(q[i], q[j]);//发现如果能“直接”走到的话,计算点的距离
else d[i][j] = INF;//如果不能走到 距离设置为正无穷
for (int k = 0; k < n; k ++ )
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);//做一遍的佛洛依德 计算“间接”两点的最短路
double r1 = 0;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < n; j ++ )
if (d[i][j] < INF / 2)//说明i走到的j
maxd[i] = max(maxd[i], d[i][j]);//如果走不到 求maxd i存i能走到的点的最大值
r1 = max(r1, maxd[i]);//r1存某个连通块的最大值
}
double r2 = INF;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if (d[i][j] > INF / 2)//如果不能走到
r2 = min(r2, maxd[i] + maxd[j] + get_dist(q[i], q[j]));//计算不能走到的最小值 也就是两个连通块的最小值
printf("%.6lf\n", max(r1, r2));
return 0;
}
排序https://www.acwing.com/problem/content/345/
求传递背包 给出若干按个关系问是否根据这些关系给出对应的顺序
可以top()排序
排序后,排序数组不为n个,则表示有环,矛盾,跳出循环
排序后,排序数组为n个,但是在过程中,有2个或以上的点在队列中,表示拓扑序并不唯一,那么此时并不能确定所有点的顺序,因此进行下一次循环
排序后,排序数组为n个,且在过程中,队列中一直只有一个,拓扑序唯一,输出结果,跳出循环
floyd
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 26;
int n, m;
bool d[N][N];
bool st[N];
void floyd() //通过floyd来逐渐更新每两个点的连通情况
{
for(int k = 0; k < n; k ++)
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
d[i][j] |= d[i][k] & d[k][j];
//if(!d[i][j]) d[i][j] = d[i][k] & d[k][j];是错误的
//如果原来是 i->k k->j 通过这样让i->j 同时如果本来i->j也一定要i->j
}
int check()
{
for(int i = 0; i < n; i ++) //矛盾情况 发现自己能到达自己
if(d[i][i]) return 2;
for(int i = 0; i < n; i ++) //不能确定情况
for(int j = 0; j < i; j ++)
if(!d[i][j] && !d[j][i]) return 0;//发现不能互相到达
return 1;
}
char get_min() //每次取出最小的值 用于输出大小关系
{
for(int i = 0; i < n; i ++)
if(!st[i]) //如果当前这个数没有取出
{
bool flag = true;
for(int j = 0; j < n; j ++)//判断是否最小
if(!st[j] && d[j][i])//如果有点比他更小的 就要推出
{
flag = false;
break;
}
if(flag)
{
st[i] = true;//没有更小的 那就是这个了
return 'A' + i;
}
}
}
int main()
{
while(cin >> n >> m, n || m)
{
memset(d, 0, sizeof d);
int type = 0, t; // t 记录轮次 type记录判断出来与否的标志
for(int i = 1; i <= m; i ++)
{
char str[5];
cin >> str;
int a = str[0] - 'A', b = str[2] - 'A';
//获得两个关系
if(!type)//如果还没确定下来
{
g[a][b] = 1;//a小于b 连接一条边
floyd();//每次连接做一次floyd
type = check();//检查下加入这次后的情况
if(type) t = i;//t找到是哪个关系
}
}
if(!type) puts("Sorted sequence cannot be determined.");
else if(type == 2) printf("Inconsistency found after %d relations.\n", t);
else
{
memset(st, 0, sizeof st);
printf("Sorted sequence determined after %d relations: ", t);
for(int i = 0; i < n; i ++) printf("%c", get_min());
printf(".\n");
}
}
return 0;
}
观光之旅
求最小环
和以前的题不同 这里是去掉某个环的某点 来判断的
因为对于 i-j-k-i 这个环 如果想要去掉 去掉k这个点 剩下的d[i][j]一定是最短的(满足dp) 所以d[i][j]+g[k][j]+g[j][i]
1.本题的思路就是考虑最小环里面节点编号最大的节点为k,且环里面与k相连的两个点为i,j,环的长度为g[i][k]+g[k][j]+d[j][i];
2.则d[j][i]则表示j到i且经过的节点编号小于k,因为在环中k就是最大的,只能经过小于k的节点了;
3.则这与floyd中k次循环开始前的d[i][j]意义相同;
4.那就不妨在floyd的第一重循环就求一下以k为最大节点编号的环的长度,美滋滋