藏宝图 (treas)
背景
Czy 爬上黑红树, 到达了一个奇怪的地方……
题目描述
Czy 发现了一张奇怪的藏宝图. 图上有 n 个点, m 条无向边. 已经标出了图中两两之间距离 dist. 但是 czy 知道, 只有当图刚好又是一颗树的时候, 这张藏宝图才是真的. 如果藏宝图是真的, 那么经过点 x 的边的边权平均数最大的那个 x 是藏着宝物的地方. 请计算这是不是真 的藏宝图, 如果是真的藏宝之处在哪里.
格式
输入数据第一行一个数 T, 表示 T 组数据.
对于每组数据, 第一行一个 n, 表示藏宝图上的点的个数.
接下来 n 行, 每行 n 个数, 表示两两节点之间的距离.
输出一行或两行. 第一行 “Yes” 或 “No”, 表示这是不是真的藏宝图.
若是真的藏宝图, 第二行再输出一个数, 表示哪个点是藏宝之处.
样例输入
2
3
0 7 9
7 0 2
9 2 0
3
0 2 7
2 0 9
7 9 0样例输出
Yes
1
Yes
3样例解释
第一棵树的形状是 1--2--3. 1、2 之间的边权是 7, 2、3 之间是 2.
第二棵树的形状是 2--1--3. 2、1 之间的边权是 2, 1、3 之间是 7.
数据范围
对于 30% 数据,\(n \leq 50\),\(1 \leq 树上的边的长度 \leq 10^9\).
对于 50% 数据,\(n \leq 600\).
对于 100% 数据,\(1 \leq n \leq 2500\), 除 30% 小数据外任意 \(0 \leq dist[i][j] \leq 10^9\),\(T \leq 5\)
Explanation
先生成一个最小生成树, 我们可以证明: 若原图是一棵树, 则其最小生成树必定是其原图. 得到这个结论以后, 我们将原来的完全图 (当然是一个稠密图, 极其稠密的稠密图) 进行一下 生成最小生成树.
显然我们不能用 Kruskal, 因为在稠密图上被 Prim 秒杀; 另外不能用堆优化 Prim, 否则它会被优化到 \(O(n^2 \cdot log(n))\); 所以最后只能用 Prim.
然后有一段很玄学的 \(O(n^2 \cdot log(n))\) 最短路代码写在底下.
最后交题的时候由于是在本地评测, 所以就闹出了一段笑话:
在隔壁的台式机上由于出题人 恶意卡常 (并且出题人强行立 flag 说不用开 long long 但是实际是需要的), 只能跑到 3s 左右. 在我的笔记本上大概 std 需要跑 31s, 然后 就只能强行调时限了.
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
typedef long long lli;
const int maxn = 2600;
const lli infinit = 0x007f7f7f7f7f7f7fll;
class MinimumSpanTree
{
public:
struct edge {
int u, v; lli len;
edge *next;
} *edges[maxn], epool[2 * maxn];
int n, root, ecnt;
void addedge(int u, int v, lli len)
{
edge *p = &epool[++ecnt],
*q = &epool[++ecnt];
p->u = u; p->v = v; p->len = len;
p->next = edges[u]; edges[u] = p;
q->u = v; q->v = u; q->len = len;
q->next = edges[v]; edges[v] = q;
return ;
}
lli dist[maxn][maxn];
lli dis[maxn]; // The distance used in eval() function.
int from[maxn]; // The "from" as in SPFA, relaxed nodes
bool visited[maxn]; // Whether visited or not
void eval(void)
{
// Resetting initial settings
for (int i = 1; i <= n; i++)
visited[i] = false, dis[i] = infinit;
dis[1] = 0;
// Iterate exactly n times with i.
for (int i = 1; i <= n; i++) {
int p = -1;
// Select previously nearest node
for (int j = 1; j <= n; j++)
if (!visited[j])
if (p <= 0 || dis[j] < dis[p])
p = j; // Assign better node
if (p < 0)
break; // Search failed
visited[p] = true;
addedge(from[p], p, dist[from[p]][p]);
// Relaxing edges
for (int j = 1; j <= n; j++)
if (!visited[j] && dist[p][j] < dis[j]) {
dis[j] = dist[p][j];
from[j] = p;
}
continue;
}
return ;
}
void clear(void)
{
memset(edges, 0, sizeof(edges));
memset(epool, 0, sizeof(epool));
memset(dist, 0, sizeof(dist));
memset(from, 0, sizeof(from));
n = 0, ecnt = 0;
return ;
}
} graph;
class ShortestPath
{
public:
struct edge {
int u, v; lli len;
edge *next;
} *edges[maxn], epool[2 * maxn];
int n, ecnt;
void addedge(int u, int v, lli len)
{
edge *p = &epool[++ecnt];
p->u = u; p->v = v; p->len = len;
p->next = edges[u]; edges[u] = p;
return ;
}
bool visited[maxn];
lli dist[maxn][maxn];
lli edge_sum[maxn];
int edge_cnt[maxn];
vector<int> vec; // Vector optimizing shortest path calculation
void dfs(int p)
{
for (edge *ep = edges[p]; ep; ep = ep->next) {
// Already visited
if (visited[ep->v])
continue;
for (unsigned int j = 0; j < vec.size(); j++) {
dist[ep->v][vec[j]] = dist[vec[j]][ep->v] = dist[vec[j]][p] + ep->len;
edge_sum[p] += ep->len;
edge_sum[ep->v] += ep->len;
edge_cnt[p]++;
edge_cnt[ep->v]++;
}
vec.push_back(ep->v);
visited[ep->v] = true;
dfs(ep->v);
}
return ;
}
void eval(void) {
dfs(1); }
void clear(void)
{
memset(edges, 0, sizeof(edges));
memset(epool, 0, sizeof(epool));
memset(visited, 0, sizeof(visited));
memset(dist, 0, sizeof(dist));
memset(edge_sum, 0, sizeof(edge_sum));
memset(edge_cnt, 0, sizeof(edge_cnt));
n = 0, ecnt = 0;
vec.clear();
return ;
}
bool cp_vis[maxn];
void cp_dfs(int p)
{
cp_vis[p] = true;
for (MinimumSpanTree::edge *ep = graph.edges[p]; ep; ep = ep->next)
if (!cp_vis[ep->v]) {
addedge(p, ep->v, ep->len);
cp_dfs(ep->v);
}
return ;
}
void copy_edges(void)
{
memset(cp_vis, 0, sizeof(cp_vis));
cp_dfs(1);
}
} spfa;
int T, n, m;
int select_best(void)
{
int best_val = 0,
best_pos = 1;
for (int i = 1; i <= n; i++) {
if (spfa.edge_cnt[i] <= 0)
continue;
int tmp = spfa.edge_sum[i] / spfa.edge_cnt[i];
if (tmp > best_val) {
best_val = tmp;
best_pos = i;
}
}
return best_pos;
}
int main(int argc, char** argv)
{
scanf("%d", &T);
for (int idx = 1; idx <= T; idx++) {
scanf("%d", &n);
graph.clear();
spfa.clear();
graph.n = spfa.n = n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%lld", &graph.dist[i][j]);
// Evaluating MST, complexity O(n^2)
graph.eval();
// Copying edges data from MST to shortest path
spfa.copy_edges();
// Evaluating SPFA, complexity O(n^2 * logn)
spfa.eval();
// Judging
bool okay = true;
for (int i = 1; i <= n && okay; i++)
for (int j = 1; j <= n && okay; j++)
if (spfa.dist[i][j] > graph.dist[i][j])
okay = false;
printf("%s\n", okay ? "Yes" : "No");
// Print the "Best Place for Treasure Hiding"
if (okay)
printf("%d\n", select_best());
}
return 0;
}