当前位置:网站首页>Summer training camp-week2 graph theory
Summer training camp-week2 graph theory
2022-08-02 13:13:00 【Crayon Xiaojin QAQ】
暑假集训-week2图论
A - Desert King
最优比例生成树+01规划
怎么说,,,,,
现学的,A bit out of range
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
// https://vjudge.net/contest/506494#problem/A
// 最优比例生成树+01分数规划+prim算法+实数二分
int n;
struct node
{
double x;
double y;
double h;
} point[10010];
double graph[10010][10010]; //原图,represents the distance between points
double cost[10010][10010]; //表示代价,即高度
bool visit[10010];
double dis[10010];
double prim(double tar)
{
double ans = 0;
memset(visit, 0, sizeof(visit));
for (int i = 1; i <= n; i++) //The outer loop must ben!因为ansAdd all distances!
dis[i] = 0x3f3f3f3f;
dis[1] = 0;
for (int i = 1; i <= n; i++)
{
int x = -1;
for (int j = 1; j <= n; j++)
{
if (!visit[j] && (x == -1 || dis[j] < dis[x]))
x = j;
}
visit[x] = 1;
ans += dis[x]; //Total distance update
for (int j = 1; j <= n; j++)
if (x != j)
dis[j] = min(dis[j], cost[x][j] - tar * graph[x][j]);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
while (cin >> n)
{
if (n == 0)
break;
for (int i = 1; i <= n; i++)
{
cin >> point[i].x >> point[i].y >> point[i].h;
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
graph[i][j] = graph[j][i] = sqrt((point[i].x - point[j].x) * (point[i].x - point[j].x) + (point[i].y - point[j].y) * (point[i].y - point[j].y)); //距离差
cost[i][j] = cost[j][i] = fabs(point[i].h - point[j].h); //高度差
}
double l = 0, r = 1e5;
while (r - l > 1e-5)
{
double mid = (l + r) / 2;
if (prim(mid) >= 0)
{
l = mid;
}
else
{
r = mid;
}
}
printf("%.3f\n", r);
}
return 0;
}
P - 最小生成树
克鲁斯卡尔算法
#include <bits/stdc++.h>
using namespace std;
struct node
{
int s;
int e;
int cost;
} path[200020];
int fa[5010];
int n, m;
bool cmp(node a, node b)
{
return a.cost < b.cost;
}
int find(int x)
{
if (fa[x] != x)
return fa[x] = find(fa[x]);
else
return fa[x];
}
void connect(int x, int y)
{
fa[find(x)] = fa[find(y)];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= m; i++)
{
cin >> path[i].s >> path[i].e >> path[i].cost;
}
sort(path + 1, path + 1 + m, cmp);
int cnt = 0;
long long ans = 0;
for (int i = 1; i <= m; i++)
{
int s = path[i].s;
int e = path[i].e;
if (find(s) != find(e))
{
ans += path[i].cost;
connect(s, e);
cnt++;
}
if (cnt == n - 1)
{
cout << ans << endl;
return 0;
}
}
cout << "orz" << endl;
return 0;
}
Q - 单源最短路径(标准版)
#include <bits/stdc++.h>
using namespace std;
// 迪杰斯特拉(堆优化)
// https://www.luogu.com.cn/problem/P4779#submit
const int maxn = 100010, maxn2 = 500010;
int head[maxn], dis[maxn], cnt;
bool visit[maxn];
int n, m, s;
struct edge
{
int to, dis, next;
} e[maxn2];
void add(int u, int v, int d)
{
cnt++;
e[cnt].dis = d;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
struct node
{
int dis;
int pos;
bool operator<(const node &x) const
{
return x.dis < dis;
}
};
priority_queue<node> q;
int main()
{
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n; ++i)
dis[i] = 0x7fffffff;
for (int i = 1; i <= m; i++)
{
register int u, v, d;
scanf("%d%d%d", &u, &v, &d);
add(u, v, d);
}
dis[s] = 0;
q.push((node){
0, s});
while (!q.empty())
{
node tmp = q.top();
q.pop();
int x = tmp.pos, d = tmp.dis;
if (visit[x])
continue;
visit[x] = 1;
for (int i = head[x]; i; i = e[i].next)
{
int y = e[i].to;
if (dis[y] > dis[x] + e[i].dis)
{
dis[y] = dis[x] + e[i].dis;
if (!visit[y])
{
q.push((node){
dis[y], y});
}
}
}
}
for (int i = 1; i <= n; i++)
printf("%d ", dis[i]);
return 0;
}
R - 最近公共祖先(LCA)
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010
// LCA问题
// https://www.luogu.com.cn/problem/P3379
int cnt, n, m, s;
int to[maxn], Next[maxn], head[maxn];
int d[maxn], f[maxn][20];
int t;
queue<int> q;
void add(int s, int e) //加边
{
to[++cnt] = e, Next[cnt] = head[s], head[s] = cnt;
}
void bfs()
{
q.push(s);
d[s] = 1;
while (q.empty() == false)
{
int x = q.front();
q.pop();
for (int i = head[x]; i; i = Next[i])
{
int tar = to[i];
if (d[tar])
continue;
d[tar] = d[x] + 1;
f[tar][0] = x;
for (int j = 1; j <= t; j++)
f[tar][j] = f[f[tar][j - 1]][j - 1];
q.push(tar);
}
}
}
int lca(int x, int y)
{
if (d[x] > d[y])
swap(x, y); //默认x小于y
for (int i = t; i >= 0; i--)
if (d[f[y][i]] >= d[x])
y = f[y][i];
if (x == y)
return x;
for (int i = t; i >= 0; i--)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> s;
t = (int)(log(n) / log(2)) + 1; //层数
for (int i = 1; i < n; i++)
{
int s, e;
cin >> s >> e;
add(s, e);
add(e, s);
}
bfs();
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
cout << lca(a, b)<<endl;
}
return 0;
}
S - 负环
#include <bits/stdc++.h>
using namespace std;
// 判断负环https://www.luogu.com.cn/problem/P3385
#define maxn 1000000
int T, n, m;
int to[maxn], edge[maxn], head[maxn], Next[maxn], cnt;
int dist[maxn];
bool visit[maxn];
int num[maxn]; //判断负环
queue<int> q;
void add(int x, int y, int z)
{
to[++cnt] = y, edge[cnt] = z, Next[cnt] = head[x], head[x] = cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
bool flag = false;
memset(visit, 0, sizeof(visit));
memset(dist, 0x3f, sizeof(dist));
memset(num, 0, sizeof(num));
memset(head, 0, sizeof(head));
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
if (w >= 0)
{
add(u, v, w);
add(v, u, w);
}
if (w < 0)
{
add(u, v, w);
}
}
dist[1] = 0, visit[1] = 1;
q.push(1);
while (q.empty() == false)
{
int x = q.front();
q.pop();
visit[x] = 0;
for (int i = head[x]; i; i = Next[i])
{
int y = to[i], z = edge[i];
if (dist[y] > dist[x] + z)
{
dist[y] = dist[x] + z;
num[y] = num[x] + 1; //This line and the followingnumJudgment is removedSPFA了
if (num[y] >= n)
{
flag = true;
break;
}
if (!visit[y])
q.push(y), visit[y] = true;
}
}
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
T - 二分图最大匹配
#include <bits/stdc++.h>
using namespace std;
// 传送门;https://www.luogu.com.cn/problem/P3386
// 匈牙利算法
#define maxn 10000100
int n, m, e, ans;
bool f[1000][1000];
int to[maxn], Next[maxn], head[maxn], cnt;
int match[maxn];
bool visit[maxn];
void add(int x, int y)
{
to[++cnt] = y, Next[cnt] = head[x], head[x] = cnt;
}
bool dfs(int x)
{
for (int i = head[x]; i; i = Next[i])
{
int y = to[i];
if (visit[y] == false)
{
visit[y] = true;
if (!match[y] || dfs(match[y]))
{
match[y] = x;
return true;
}
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> e;
for (int i = 1; i <= e; i++)
{
int u, v;
cin >> u >> v;
if (u <= n && v <= m)
add(u, v);
}
ans = 0;
for (int i = 1; i <= n; i++)
{
memset(visit, 0, sizeof(visit));
if (dfs(i))
ans++;
}
cout << ans << endl;
return 0;
}
边栏推荐
猜你喜欢
Intouch Historian历史曲线配置导入导出
Scala基础语法入门(三)Scala中的各种运算符
你知道图论的Dijkstra吗?
鲁大师7月新机性能/流畅榜:骁龙8+正面对决天玑9000+,性能跑分突破123万!
In-depth analysis and use of Ribbon load balancing
【C语言】函数哪些事儿,你真的get到了吗?(2)
PHP+MYSQL [Student Information Management System] (Minimalist Edition)
工厂方法模式
国产 GPU 创业潮 喧嚣下的资本游戏
js stopwatch countdown plugin
随机推荐
短视频美食自媒体怎么做?5步教你快速上手
86.(cesium之家)cesium叠加面接收阴影效果(gltf模型)
【typescript】使用antd中RangePicker组件实现时间限制 当前时间的前一年(365天)
UAC绕过学习-总结
一款强大的js弹出alert插件
wx-wow(微信小程序动效库)
【C语言】剖析函数递归(3)
FreeRTOS--栈实验
Four seasons of trees realized by svg
机器人碰撞检测方法形式化
Mysql视图
企业用直播平台能实现什么
如何通过DBeaver 连接 TDengine?
Intouch Historian历史曲线配置导入导出
【C语言】剖析函数递归(1)
动态组件-component
百日刷题计划 ———— DAY1
FreeRTOS实验--一个函数创建多个任务
Name conventions in FreeRTOS
【622. 设计循环队列】