CF666B. World Tour
2024-09-23 16:23:34
CF666B. World Tour
题意:
给定一张边权为 1 的有向图,求四个不同点 A, B, C, D
使得 dis(A, B) + dis(B, C) + dis(C, D) 取最大值,dis表示最短路距离 1 ≤ n ≤ 3000, 1 ≤ m ≤ 5000
我又写了假做法呜呜呜
首先当然\(O(nm)\)预处理两点之间最短路
然后预处理出从每个点开始前3个dis最大的点
假做法:
贪心,枚举A,贪心选择dis较大的BCD,就是3*3*3搜索选出B、C、D
假的原因:
贪心不成立,因为前面会影响后面,可以先差,再优、优
真做法:
再预处理到达每个点的前3个dis最大的点
枚举B、C,再3*3选出A、D,选A、D不会像之前那样互相干扰了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e4+5, inf = 1e9;
int n, m;
struct edge {int v, ne;} e[N];
int cnt, h[N], d[N][N];
inline void ins(int u, int v) {
e[++cnt] = (edge) {v, h[u]}; h[u] = cnt;
}
int q[N], head, tail, vis[N];
#define fir first
#define sec second
pair<int, int> a[N], f[N][5], g[N][5];
void bfs(int s) {
memset(vis, 0, sizeof(vis));
head = tail = 1;
q[tail++] = s; vis[s] = 1;
memset(d[s], 0x3f, sizeof(d[s]));
int *dis = d[s];
dis[s] = 0;
while(head != tail) {
int u = q[head++];
for(int i=h[u]; i; i=e[i].ne) {
int v = e[i].v;
if(vis[v]) continue;
dis[v] = dis[u] + 1;
vis[v] = 1;
q[tail++] = v;
}
}
}
void solve(int s) {
int cnt = 0;
for(int i=1; i<=n; i++) if(i!=s && d[s][i] < inf) a[++cnt] = make_pair(d[s][i], i);
for(int i=cnt+1; i<=3; i++) a[i] = make_pair(0, 0);
sort(a+1, a+cnt+1, greater<pair<int, int> >());
f[s][1] = a[1], f[s][2] = a[2], f[s][3] = a[3];
cnt = 0;
for(int i=1; i<=n; i++) if(i!=s && d[i][s] < inf) a[++cnt] = make_pair(d[i][s], i);
for(int i=cnt+1; i<=3; i++) a[i] = make_pair(0, 0);
sort(a+1, a+cnt+1, greater<pair<int, int> >());
g[s][1] = a[1], g[s][2] = a[2], g[s][3] = a[3];
//if(s == 1) printf("hi %d %d %d\n", a[1].sec, a[2].sec, a[3].sec);
//printf("sssssssssssssssssssssssssssss %d\n", s);
//for(int i=1; i<=3; i++) printf("f %d %d %d\n", i, f[s][i].fir, f[s][i].sec);
}
int ans, li[10];
int main() {
//freopen("in", "r", stdin);
ios::sync_with_stdio(false); cin.tie(); cout.tie();
cin >> n >> m;
for(int i=1; i<=m; i++) {
int u, v;
cin >> u >> v;
if(u != v && !d[u][v]) ins(u, v), d[u][v] = 1;
}
for(int i=1; i<=n; i++) bfs(i);
for(int i=1; i<=n; i++) solve(i);
for(int b=1; b<=n; b++)
for(int c=1; c<=n; c++) if(d[b][c] < inf && c != b) {
int now = d[b][c];
for(int i=1; i<=3; i++) {
pair<int, int> &ra = g[b][i];
int a = ra.sec;
if(a == b || a == c || !ra.fir) continue;
now += ra.fir;
for(int j=1; j<=3; j++) {
pair<int, int> &rd = f[c][j];
int d = rd.sec;
if(d ==a || d == b || d == c || !rd.fir) continue;
now += rd.fir;
if(now > ans) {
ans = now;
li[1] = a; li[2] = b; li[3] = c; li[4] = d;
}
now -= rd.fir;
}
now -= ra.fir;
}
}
for(int i=1; i<=4; i++) cout << li[i] << ' ';
}
最新文章
- 二维码合成,将苹果和安卓(ios和android)合成一个二维码,让用户扫描一个二维码就可以分别下载苹果和安卓的应用
- .Net Core 之 图形验证码 本文介绍.Net Core下用第三方ZKWeb.System.Drawing实现验证码功能。
- myeclipse 破解步骤
- 8.Android之日期DatePicker和时间TimeTicker控件学习
- 如何由新特性跳转到App首页
- 用Python抓网页的注意事项
- SPRING IN ACTION 第4版笔记-第五章BUILDING SPRING WEB APPLICATIONS-005-以path parameters的形式给action传参数(value=“{}”、@PathVariable)
- hadoop2.2原理: 序列化浅析
- C# winform DataTable 批量数据处理 增、删、改 .
- MATLAB垂直搜索图片中的白段
- SQL Server XML数据解析
- SEO的基本概念 和 提交SITEMAP到搜索引擎
- .NET程序员我是如何通过一个产品在2年内买车买房
- linux学习------磁盘性能测试
- 洛谷P2045 K方格取数(算竞进阶习题)
- 打开对话框opendialog
- 在没有go-pear.bat的php中安装pear
- phpexcel 导入超过26列时的解决方案
- 【Android实验】第一个Android程序与Activity生命周期
- matlab gradient 和 prctile
热门文章
- mysql,mycat的demo
- Codeforces Round #404 (Div. 2) D. Anton and School - 2
- CentOS 7下安装vertica记录
- 查询SQL Server执行过的SQL语句
- Power BI行级别安全性(数据权限管理)
- Java基础 -- 连接字符串时,使用+还是StringBuilder
- nginx 配置proxy_pass URL末尾加与不加/(斜线)的区别
- 正则表达式匹配日期,支持闰年,格式为YYYYMMDD
- selenium启动报错“ incorrect JSON status mapping for &#39;unknown error&#39; (500 expected)”
- session前后台交互