上午思维题训练
https://codeforces.com/contest/2026/problem/C
https://codeforces.com/contest/2026/problem/B
https://codeforces.com/contest/2023/problem/A
https://codeforces.com/contest/2034/problem/D
下午
https://vjudge.net/problem/HDU-4612
题意：有一个无向图，加一条无向边使得这个图的割边最小。
思路：通过eDcc缩点，缩成一棵树，然后求树的直径，答案就是割边-树的直径
思路AC，代码没有AC，一直MLE，日后再改。
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
//typedef unsigned __int128 LL;
const int N=2e4+10,M=1e6+10,inf=1e16,mod=1e8;
int n,m;
struct edge{
int v,last;
}e[M];
int h[N],idx;//0开始
vector<int> fir;
void add(int u,int v) {
fir.push_back(u);
e[idx].v=v;
e[idx].last=h[u];
h[u] = idx++;
}
int dfn[N],low[N],tot;
stack<int> stk;
int dcc[N],cnt;//dcc记录边双连通分量
int bri[M];//bri[i]记录割边
void tarjan(int x,int edg) {
dfn[x] = low[x] = ++tot;
stk.push(x);
for (int i = h[x]; ~i; i = e[i].last) {
int y = e[i].v;
if (!dfn[y]) {
tarjan(y, i);
low[x] = min(low[y], low[x]);
if (low[y] > dfn[x]) {//割边
bri[i] = 1;
bri[i ^ 1] = 1;
}
} else if (i != (edg ^ 1)) {
low[x] = min(dfn[y], low[x]);
}
}
//离，判边双连通分量
if (dfn[x] == low[x]) {
++cnt;
while (1) {
int y = stk.top();
stk.pop();
dcc[y] = cnt;
if (x == y) break;
}
}
}
vector<int> ne[N];
int ans=0;
int dfs(int u,int f){
int d1=0,d2=0;
for(auto v:ne[u]){
if(v==f) continue;
int d=dfs(v,u)+1;
if(d>d1) d2=d1,d1=d;
else if(d>d2) d2=d;
}
ans=max(ans,d1+d2);
return d1;
}
void solve() {
while(cin>>n>>m){
if(n==0&&m==0) break;
idx=tot=cnt=ans=0;
for(int i=0;i<=n;i++) {
dfn[i]=low[i]=0;
h[i]=-1;
dcc[i]=0;
ne[i].clear();
}
while(!stk.empty()) stk.pop();
for(int i=0;i<=m;i++){
e[i].v=-1,e[i].last=-1;
bri[i]=0;
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i,-1);
}
for(int i=0;i<idx;i++){
if(bri[i]){
ne[dcc[fir[i]]].push_back(dcc[e[i].v]);
}
}
dfs(1,-1);
cout<<cnt-1-ans<<endl;
}
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// int _;
// cin >> _;
// while (_--)
solve();
return 0;
}
畅通工程再续 - HDU 1875 - Virtual Judge
这题比较典，数据较小，所以暴力建边，然后并查集求最小生成树。
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
//typedef unsigned __int128 LL;
const int N=105,M=1e6+10,inf=1e16,mod=1e8;
double dis[105][105];
int fa[N];
struct node {
double x, y;
};
double f(node a,node b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
struct node1 {
int u, v;
double w;
}e[M];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void solve() {
int n;
cin >> n;
vector<node> v;
v.push_back({0, 0});
for (int i = 1; i <= n; i++) {
double x, y;
cin >> x >> y;
v.push_back({x, y});
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
dis[j][i] = f(v[j], v[i]);
++cnt;
e[cnt].u = j, e[cnt].v = i, e[cnt].w = dis[j][i];
}
}
auto cmp = [&](node1 a, node1 b) {
return a.w < b.w;
};
double ans = 0;
for (int i = 1; i <= n; i++) fa[i] = i;
sort(e + 1, e + cnt + 1, cmp);
auto kruscal = [&]() {
int num = 0;
for (int i = 1; i <= cnt; i++) {
if (e[i].w > 1000) break;
if (e[i].w < 10) continue;
int x = find(e[i].u);
int y = find(e[i].v);
if (x != y) {
fa[x] = y;
ans += e[i].w;
num++;
}
}
return num == n - 1;
};
if (kruscal()) printf("%.1lf\n", ans * 100);
else cout << "oh!" << endl;
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _;
cin >> _;
while (_--)
solve();
return 0;
}
[P1967 NOIP2013 提高组] 货车运输 - 洛谷 | 计算机科学教育新生态
题意：有一个带权无向图，现在询问图上任意两点的所有路径中最大的边权
思路：要求最大边权，所以，可想而知，图上有些小边权是用不上的，所以要去掉一些边，首先建最大生成树，
然后在最大生成树上求任意两点的路径最大边权，倍增求LCA的时候，可以求出树上俩点的路径，是在图上向上跳，递推而来的，同样，所以求最大边权可以求LCA得来。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
//typedef unsigned __int128 LL;
const int N=3e4+10,M=5e4+10,inf=1e16,mod=1e8;
int fa[N],dfn[N],dep[N];
int Fa[N][25],dis[N][25],tot;
int n,m;
struct edge {
int u, v, w;
bool operator<(const edge &t) const {
return w > t.w;
}
}e[M];
struct node {
int v, w;
};
vector<node> ne[N];
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void kruscal() {
for (int i = 1; i <= m; i++) {
int x = find(e[i].u), y = find(e[i].v);
if (x != y) {
fa[x] = y;
ne[e[i].u].push_back({e[i].v, e[i].w});
ne[e[i].v].push_back({e[i].u, e[i].w});
}
}
}
void dfs(int now,int f) {
dep[now] = dep[f] + 1;
dfn[now] = ++tot;
Fa[now][0] = f;
for (int i = 0; i <= 21; i++) {
Fa[now][i + 1] = Fa[Fa[now][i]][i];
if (dfn[Fa[now][i + 1]]) dis[now][i + 1] = min(dis[now][i], dis[Fa[now][i]][i]);
}
for (auto k: ne[now]) {
int v = k.v, w = k.w;
if (v != f) {
dis[v][0] = w;
dfs(v, now);
}
}
}
int lca(int x,int y) {
int ans = 1e16;
if (dep[x] < dep[y]) swap(x, y);
for (int i = 22; i >= 0; i--) {
if (dep[Fa[x][i]] >= dep[y]) ans = min(ans, dis[x][i]), x = Fa[x][i];
}
if (x == y) return ans;
for (int i = 22; i >= 0; i--) {
if (Fa[x][i] != Fa[y][i]) {
ans = min(ans, min(dis[x][i], dis[y][i]));
x = Fa[x][i], y = Fa[y][i];
}
}
ans = min(ans, min(dis[x][0], dis[y][0]));
return ans;
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
for (int i = 1; i <= n; i++) fa[i] = i;
sort(e + 1, e + m + 1);
kruscal();
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 22; j++) dis[i][j] = 1e16;
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) dis[i][0] = 1e16, dfs(i, 0);
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
if (find(x) != find(y)) {
cout << -1 << endl;
continue;
}
cout << lca(x, y) << endl;
}
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// int _;
// cin >> _;
// while (_--)
solve();
return 0;
}