https://vjudge.net/contest/496336#problem/K
2021东北四省赛 [Cloned] K - City
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,q;
const int N = 5e5+9;
int p[N];
ll Size[N];
ll ans[N];
struct node
{
int p,id;
}x[N];
struct E
{
int a,b,c;
}e[N];
bool cmp(node a,node b)
{
return a.p > b.p;
}
bool cmp2(E a,E b)
{
return a.c > b.c;
}
int find(int x)
{
if(p[x] != x) return p[x] = find(p[x]);
return p[x];
}
void Merge(int x,int y)
{
int px = find(x),py = find(y);
if(px != py)
{
Size[py] += Size[px];
p[px] = py;
}
}
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1; i<=m; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[i] = {a,b,c};
}
for(int i=1; i<=n; i++) p[i] = i,Size[i] = 1;
sort(e+1,e+m+1,cmp2);
for(int i=1; i<=q; i++)
{
scanf("%d",&x[i].p);
x[i].id = i;
}
sort(x+1,x+q+1,cmp);
ll sum = 0;
for(int i=1,j = 1; i<=q; i++)
{
for(; j <= m; j++)
{
if(e[j].c < x[i].p) break;
int a = e[j].a,b = e[j].b;
int px = find(a),py = find(b);
if(px != py)
{
sum += 1LL * Size[px] * Size[py];
Merge(a,b);
}
}
ans[x[i].id] = sum;
}
for(int i=1; i<=q; i++) printf("%lld\n",ans[i]);
}
return 0;
}
//https://oj.neauacm.cn/problem.php?cid=1195&pid=1
拼拼图图
//转换成一维度坐标！
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 2e3+9;
int a[N][N];
int p[N*N];
int find(int x)
{
if(x == p[x]) return p[x];
return p[x] = find(p[x]);
}
void Merge(int x,int y)
{
int px = find(x),py = find(y);
if(px != py) p[px] = py;
}
int main()
{
for(int i=1; i<=N*N; i++) p[i] = i;
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++) scanf("%d",&a[i][j]);
}
int m;
scanf("%d",&m);
while(m--)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int p1 = (x1 - 1)*n + y1 ;
int p2 = (x2 - 1)*n + y2 ;
Merge(p1,p2);
}
int ans = 0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
int p1 = (i-1)*n + j;
if(a[i][j] != p1)
{
if(find(p1) == find(a[i][j]))
{
ans++;
}
}
else ans++;
}
}
ans = n*n - ans;
if(ans == 0) printf("Yes\n");
else printf("%d\n",ans);
return 0;
}
//https://oj.neauacm.cn/problem.php?cid=1198&pid=4
题目描述
有一颗有n个结点树，结点被编号为1~n，其中每条边有权值w，从a结点走到b结点的花费是a到b路径上边权的最大值
每条边的权值为1~n-1中的一个且互不相等，求树中所有两结点间的花费之和
输入
第一行输入一个整数T，代表有T组测试数据
对于每一组测试数据，第一行有1个整数n，接下来n-1行，每行有3个整数x, y, w表示x和y之间有一条边，权值为w
数据范围 : 1 ≤ T ≤ 1000, 1 ≤ n ≤ 2·105, 1 ≤ w ≤ n, ∑n≤2·105.
输出
对于每组测试数据，输出树中所有两结点间的花费之和
样例输入
2
6
4 5 4
5 6 2
2 5 5
1 3 1
4 3 3
5
1 2 3
2 3 2
3 4 1
4 5 4
样例输出
58
30
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 3e5+9;
int p[N],sum[N];
struct node
{
int a,b,c;
bool operator < (const node & o) const
{
return c < o.c;
}
}H[N];
int find(int x)
{
if(x != p[x]) return p[x] = find(p[x]);
return p[x];
}
void Merge(int x,int y)
{
int px = find(x),py = find(y);
if(px != py)
{
p[px] = py;
sum[py] += sum[px];
}
}
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
long long ans = 0;
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++) p[i] = i,sum[i] = 1;
for(int i=1; i<n; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
H[i] = {a,b,c};
}
sort(H+1,H+n);
long long maxx = 0;
for(int i=1; i<n; i++)
{
maxx = max(maxx,1LL*H[i].c);
int x = H[i].a,y = H[i].b;
int px = find(x),py = find(y);
long long cnt = 1LL*sum[px] * sum[py];
ans += cnt * maxx;
Merge(x,y);
}
printf("%lld\n",ans);
}
return 0;
}
最大子段和！
https://oj.neauacm.cn/problem.php?cid=1199&pid=3
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 2e5+9;
ll p[N],vis[N],sum[N],a[N],b[N],ans[N];
ll find(int x)
{
if(x != p[x]) return p[x] = find(p[x]);
return p[x];
}
void Merge(int x,int y)
{
int px = find(x),py = find(y);
if(px != py)
{
sum[py] += sum[px];
p[px] = py;
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(sum,0,sizeof(sum));
memset(vis,0,sizeof(vis));
for(int i=1; i<N; i++) p[i] = i;
int n,k;
scanf("%d%d",&n,&k);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]),sum[i] = a[i];
for(int i=1; i<=k; i++) scanf("%lld",&b[i]),vis[b[i]] = 1;
ll maxx = 0;
for(int i=1; i<=n; i++)
{
if(!vis[i])
{
if(!vis[i-1]) Merge(i,i-1);
if(!vis[i+1]) Merge(i,i+1);
maxx = max(maxx,sum[find(i)]);
}
}
ans[k] = maxx;
for(int i=k; i>=2; i--)
{
int pos = b[i];
vis[pos] = 0;
if(!vis[pos - 1] && pos >= 2) Merge(pos-1,pos);
if(!vis[pos + 1] && pos <= n-1) Merge(pos+1,pos);
ll x = sum[find(pos)];
maxx = max(maxx,x);
ans[i-1] = maxx;
}
for(int i=1; i<=k; i++) printf("%lld\n",ans[i]);
}
return 0;
}
https://codeforces.com/contest/722/problem/C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+9;
int a[N],b[N],vis[N];
ll p[N],sum[N];
ll ans[N];
int find(int x)
{
if(x != p[x]) return p[x] = find(p[x]);
return p[x];
}
void Merge(int x,int y)
{
int px = find(x),py = find(y);
p[px] = py;
sum[py] += sum[px];
}
int main()
{
for(int i=1; i<N; i++) p[i] = i;
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]),sum[i] = a[i];
for(int i=1; i<=n; i++) scanf("%d",&b[i]),vis[b[i]] = 1;
long long maxx = 0;
for(int i=n; i>=1; i--)
{
int pos = b[i];
vis[pos] = 0;
if(!vis[pos - 1]) Merge(pos - 1,pos);
if(!vis[pos + 1]) Merge(pos + 1,pos);
maxx = max(1LL*maxx,sum[find(pos)]);
ans[i-1] = maxx;
}
for(int i=1; i<=n; i++) printf("%lld\n",ans[i]);
return 0;
}
京公网安备 11010502036488号