次小生成树.
这道题,最后一个点很坑,必须记录次小值才能过。
(10/11)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505;
int s;
int n,m;
int tot;
int x,y,z;
int pre[N];
int head[N];
int maxx[N][N];//最小生成树上两点树上路径中边权最大值
struct Kano{
int l,r,w,tag;
}kano[20*N];
bool cmp(Kano a,Kano b){
return a.w<b.w;
}
struct Bird{
int u,v,w;
}boy[5*N];
void add(int x,int y,int z){
boy[++tot].u=head[x];
boy[tot].v=y;
boy[tot].w=z;
head[x]=tot;
return ;
}
int find(int x){
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);
}
void dfs(int now){//dfs找maxx[s][now]
for(int i=head[now];i;i=boy[i].u){
int to=boy[i].v;
int pay=boy[i].w;
if(!maxx[s][to]&&to!=s){
maxx[s][to]=max(maxx[s][now],pay);
dfs(to);
}
}
return;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
kano[i]=(Kano){x,y,z};//建原图
}
for(int i=1;i<=n;++i)
pre[i]=i;
sort(kano+1,kano+m+1,cmp);
ll now=0;//记录最小生成树的边权和
for(int i=1;i<=m;++i){
int u=find(kano[i].l),v=find(kano[i].r);
if(u!=v){
pre[u]=v;
add(kano[i].l,kano[i].r,kano[i].w);//建树图
add(kano[i].r,kano[i].l,kano[i].w);
now+=kano[i].w;
kano[i].tag=1;//标记为树边
}
}
for(s=1;s<=n;++s)
dfs(s);
ll res=1e15;
for(int i=1;i<=m;++i)
if(!kano[i].tag&&kano[i].w>maxx[kano[i].l][kano[i].r]){
//如果该边为非树边并且它的权值大于左右端点的树上距离(因为是次小生成树,所以权值要比最小生成树大)
res=min(res,now-maxx[kano[i].l][kano[i].r]+kano[i].w);//把路径上最大的换成这条边的答案
}
printf("%lld\n",res);
return 0;
}
(11/11)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<queue>
#include<vector>
#include<deque>
#include<stack>
#include<set>
#include<map>
using namespace std;
inline long long read()
{
char ch = getchar();
long long result = 0,flag=1;
while(ch < '0' || ch > '9')
{
if(ch == '-')
flag = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
result = (result<<3)+(result<<1)+ch-'0';
ch = getchar();
}
return result*flag;
}
void print(long long x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
putchar((x>9?print(x/10),x%10:x)+'0');
return;
}
#define inf 0x3f3f3f3f3f3f3f3f
#define maxnode 1000050
#define maxedge 3000050
long long ans,mst,n,m,total,head[maxnode],father[maxnode],sum[maxnode];
long long fa[maxnode][19],maxn[maxnode][19],smax[maxnode][19],depth[maxnode];
bool in_mst[maxedge];
struct Edge
{
long long start,end,value,next;
friend bool operator < (Edge a,Edge b)//kruskal
{
return a.value < b.value;
}
}edge[maxedge],temp[maxedge];
inline void insert(long long now,long long v,long long w)
{
edge[++total].start = now;
edge[total].end = v;
edge[total].value = w;
edge[total].next = head[now];
head[now] = total;
}
inline void dfs(long long now,long long from)
{
fa[now][0] = from;
long long i,v;
for(i=head[now]; i; i=edge[i].next)
{
v = edge[i].end;
if(v != from)
{
depth[v] = depth[now]+1;
maxn[v][0] = edge[i].value;
smax[v][0] = -inf;
dfs(v,now);
}
}
}
inline void calc()
{
long long i,j;
for(i=1; i<=18; ++i)
for(j=1; j<=n; ++j)
{
fa[j][i] = fa[fa[j][i-1]][i-1];
maxn[j][i] = max(maxn[j][i-1],maxn[fa[j][i-1]][i-1]);
smax[j][i] = max(smax[j][i-1],smax[fa[j][i-1]][i-1]);
if(maxn[j][i-1] > maxn[fa[j][i-1]][i-1])//严格次小,绝无等号
smax[j][i] = max(smax[j][i],maxn[fa[j][i-1]][i-1]);
else if(maxn[j][i-1] < maxn[fa[j][i-1]][i-1])
smax[j][i] = max(smax[j][i],maxn[j][i-1]);
}
}
inline long long LCA(long long x,long long y)
{
if(depth[x] < depth[y])
swap(x,y);
long long i;
for(i=18; i >= 0; --i)
if(depth[fa[x][i]] >= depth[y])
x = fa[x][i];
if(x == y)
return x;
for(i=18; i>=0; --i)
if(fa[x][i]^fa[y][i])
x = fa[x][i],y = fa[y][i];
return fa[x][0];
}
inline long long qmax(long long u,long long v,long long maxx)
{
long long res = -inf;
for(long long i = 18; i >= 0; --i)
if(depth[fa[u][i]] >= depth[v])
{
if(maxx != maxn[u][i])
res = max(res,maxn[u][i]);
else
res = max(res,smax[u][i]);
u = fa[u][i];
}
return res;
}
inline long long find(long long a)
{
while(a != father[a])
a = father[a] = father[father[a]];
return a;
}
inline void input()
{
n = read();
m = read();
for(long long i=1; i<=m; ++i)
{
temp[i].start = read();
temp[i].end = read();
temp[i].value = read();
}
}
inline void combine(long long a,long long b)
{
if(sum[a] > sum[b])
father[b] = a,sum[a] += sum[b];
else
father[a] = b,sum[b] += sum[a];
}
inline void Mst()
{
memset(head,0,sizeof(head));
total = mst = 0;
sort(temp+1,temp+m+1);
long long i,fx,fy;
for(i=1;i<=n;++i)
father[i] = i,sum[i] = 1;
for(i=1; i<=m; ++i)
{
fx = find(temp[i].start);
fy = find(temp[i].end);
if(fx != fy)
{
mst += temp[i].value;
combine(fx,fy);
insert(temp[i].start,temp[i].end,temp[i].value);
insert(temp[i].end,temp[i].start,temp[i].value);
in_mst[i] = true;
}
}
}
inline void Smst()
{
smax[1][0] = -inf;
depth[1] = 1;
ans = inf;
dfs(1,-1);
calc();
long long i,u,v,d,lca,maxu,maxv;
for(i=1; i<=m; ++i)
if(!in_mst[i])
{
u = temp[i].start;
v = temp[i].end;
d = temp[i].value;
lca = LCA(u,v);
maxu = qmax(u,lca,d);
maxv = qmax(v,lca,d);
ans = min(ans,mst-max(maxu,maxv)+d);
}
}
int main()
{
input();
Mst();
Smst();
print(ans);
return 0;
}
看不懂,但还是tql!
tql
tql