一、P4180 【模板】严格次小生成树[BJWC2010]：
因为是严格的，维护最大值和严格次大值就好啦。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=300100;
const ll lnf=0x3f3f3f3f3f3f3f3f;
struct node
{
int x,y;
ll z;
node(){}
node(int a,int b,ll c)
{
x=a,y=b,z=c;
}
}a[maxn];
int head[maxn],ver[maxn],nt[maxn];
ll edge[maxn];
int ff[maxn],d[maxn],f[maxn][20];
ll g[maxn][20][2];
bool ha[maxn];
int tot=1;
int t;
ll max1,max2;
int n,m;
void init(int n)
{
for(int i=1;i<=n;i++)
{
head[i]=d[i]=0;
ff[i]=i;
memset(f[i],0,sizeof(f[i]));
memset(g[i],0,sizeof(g[i]));
}
memset(ha,false,sizeof(ha));
tot=1;
t=log2(n)+1;
}
void add(int x,int y,ll z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
int fi(int x)
{
if(ff[x]!=x)
ff[x]=fi(ff[x]);
return ff[x];
}
bool cmp(node &a,node &b)
{
return a.z<b.z;
}
void bfs(void)
{
queue<int>q;
q.push(1);
d[1]=1;
while(q.size())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
ll z=edge[i];
if(d[y]) continue;
d[y]=d[x]+1;
f[y][0]=x;
g[y][0][0]=z;
g[y][0][1]=-lnf;
for(int j=1;j<=t;j++)
{
f[y][j]=f[f[y][j-1]][j-1];
g[y][j][0]=max(g[y][j-1][0],g[f[y][j-1]][j-1][0]);
if(g[y][j-1][0]==g[f[y][j-1]][j-1][0])
g[y][j][1]=max(g[y][j-1][1],g[f[y][j-1]][j-1][1]);
else if(g[y][j-1][0]<g[f[y][j-1]][j-1][0])
g[y][j][1]=max(g[y][j-1][0],g[f[y][j-1]][j-1][1]);
else if(g[y][j-1][0]>g[f[y][j-1]][j-1][0])
g[y][j][1]=max(g[y][j-1][1],g[f[y][j-1]][j-1][0]);
}
q.push(y);
}
}
return ;
}
void ***(int &y,int i)
{
if(g[y][i][0]>max1) max2=max(max1,g[y][i][1]),max1=g[y][i][0];
else if(g[y][i][0]<max1) max2=max(max2,g[y][i][0]);
else max2=max(max2,g[y][i][1]);
y=f[y][i];
}
ll lca(int x,int y,ll z)
{
if(d[x]>d[y]) swap(x,y);
max1=-lnf,max2=-lnf;
for(int i=t;i>=0;i--)
if(d[f[y][i]]>=d[x]) ***(y,i);
if(x==y) return (z==max1?z-max2:z-max1);
for(int i=t;i>=0;i--)
if(f[y][i]!=f[x][i]) ***(x,i),***(y,i);
***(x,0),***(y,0);
return (z==max1?z-max2:z-max1);
}
int main(void)
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init(n);
int x,y;
ll z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%lld",&x,&y,&z);
a[i]=node(x,y,z);
}
sort(a+1,a+m+1,cmp);
int cnt=0;
ll ans=0;
for(int i=1;i<=m;i++)
{
int xx=fi(a[i].x);
int yy=fi(a[i].y);
if(xx==yy) continue;
ha[i]=true;
ff[xx]=yy;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);
cnt++;ans+=a[i].z;
if(cnt==n-1) break;
}
if(cnt!=n-1) printf("-1\n");
bfs();
ll res=lnf;
for(int i=1;i<=m;i++)
{
if(ha[i]) continue;
res=min(res,lca(a[i].x,a[i].y,a[i].z));
}
printf("%lld\n",res+ans);
}
return 0;
}
二、The Unique MST POJ - 1679 ：
这题数据范围这么小，我觉得暴力就能过啊：
删除一条边之后，再求几遍最小生成树就是了。
①：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=10010;
int f[maxn];
int n,m;
vector<int>vc;
struct node
{
int x,y,z;
node(){}
node(int a,int b,int c)
{
x=a,y=b,z=c;
}
}a[maxn];
bool cmp(const node &a,const node &b)
{
return a.z<b.z;
}
int fi(int x)
{
if(x!=f[x])
f[x]=fi(f[x]);
return f[x];
}
int kr(int pt)
{
for(int i=1;i<=n;i++)
f[i]=i;
int cnt=0;
int ans=0;
for(int i=1;i<=m;i++)
{
if(i==pt) continue;
int xx=fi(a[i].x);
int yy=fi(a[i].y);
if(xx==yy) continue;
f[xx]=yy;
cnt++;
ans+=a[i].z;
if(cnt==n-1) break;
}
if(cnt!=n-1) return -1;
return ans;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[i]=node(x,y,z);
}
sort(a+1,a+n+1,cmp);
vc.clear();
int cnt=0;
int ans=0;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int xx=fi(a[i].x);
int yy=fi(a[i].y);
if(xx==yy) continue;
f[xx]=yy;
cnt++;
ans+=a[i].z;
vc.push_back(i);
if(cnt==n-1) break;
}
if(cnt!=n-1)
{
printf("Not Unique!\n");
continue;
}
bool flag=false;
for(int i=0;i<vc.size();i++)
{
int tt=kr(vc[i]);
if(tt==-1) continue;
if(tt==ans)
{
printf("Not Unique!\n");
flag=true;
break;
}
}
if(!flag) printf("%d\n",ans);
}
return 0;
}
②：
求非严格次小生成树也能解决吧：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=300100;
const int inf=0x3f3f3f3f;
struct node
{
int x,y;
ll z;
node(){}
node(int a,int b,ll c)
{
x=a,y=b,z=c;
}
}a[maxn];
int head[maxn],ver[maxn],nt[maxn],edge[maxn];
int ff[maxn],d[maxn],f[maxn][20],g[maxn][20];
bool ha[maxn];
int tot=1,t,max1,n,m;
void init(int n)
{
for(int i=1;i<=n;i++)
{
head[i]=d[i]=0;
ff[i]=i;
memset(f[i],0,sizeof(f[i]));
memset(g[i],0,sizeof(g[i]));
}
memset(ha,false,sizeof(ha));
tot=1;
t=log(n*1.0)/log(2.0)+1;
}
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
int fi(int x)
{
if(ff[x]!=x)
ff[x]=fi(ff[x]);
return ff[x];
}
bool cmp(const node &a,const node &b)
{
return a.z<b.z;
}
void bfs(void)
{
queue<int>q;
q.push(1);
d[1]=1;
while(q.size())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(d[y]) continue;
d[y]=d[x]+1;
f[y][0]=x;
g[y][0]=z;
for(int j=1;j<=t;j++)
{
f[y][j]=f[f[y][j-1]][j-1];
g[y][j]=max(g[y][j-1],g[f[y][j-1]][j-1]);
}
q.push(y);
}
}
return ;
}
void ***(int &y,int i)
{
max1=max(max1,g[y][i]);
y=f[y][i];
}
int lca(int x,int y,int z)
{
if(d[x]>d[y]) swap(x,y);
max1=-inf;
for(int i=t;i>=0;i--)
if(d[f[y][i]]>=d[x]) ***(y,i);
if(x==y) return z-max1;
for(int i=t;i>=0;i--)
if(f[y][i]!=f[x][i]) ***(x,i),***(y,i);
***(x,0),***(y,0);
return z-max1;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init(n);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[i]=node(x,y,z);
}
sort(a+1,a+m+1,cmp);
int cnt=0;
int ans=0;
for(int i=1;i<=m;i++)
{
int xx=fi(a[i].x);
int yy=fi(a[i].y);
if(xx==yy) continue;
ha[i]=true;
ff[xx]=yy;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);
cnt++;ans+=a[i].z;
if(cnt==n-1) break;
}
if(cnt!=n-1)
{
printf("Not Unique!\n");
continue;
}
if(m==n-1)
{
printf("%d\n",ans);
continue;
}
bfs();
int res=inf;
for(int i=1;i<=m;i++)
{
if(ha[i]) continue;
res=min(res,lca(a[i].x,a[i].y,a[i].z));
}
if(res) printf("%d\n",ans);
else printf("Not Unique!\n");
}
return 0;
}
其实我觉得倍增的复杂度已经足够找次小生成树了，下面两种由最小生成树变形而来的算法也了解一下：
数据真水，类似于dp，也类似于lca的找法，维护一个最大值：
Prim
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=1008;
const int inf=0x3f3f3f3f;
int n,m,w[maxn][maxn];
int d[maxn];
bool ha[maxn];
int maxx[maxn][maxn];
int pre[maxn];
bool mst[maxn][maxn];
int Prim(int s) {
memset(d,0x3f,sizeof(d));
memset(maxx,0,sizeof(maxx));
memset(ha,0,sizeof(ha));
memset(mst,0,sizeof(mst));
for(int i=1;i<maxn;i++)
pre[i]=s;
d[s]=0;
priority_queue<pair<int,int> > q;
q.push(make_pair(0,s));
int res = 0;
while(!q.empty()) {
int x=q.top().second;
q.pop();
if(ha[x]) continue;
ha[x]=true;
res+=d[x];
mst[x][pre[x]]=mst[pre[x]][x]=true;
for(int y=1;y<=n;y++) {
if(ha[y])
maxx[x][y]=maxx[y][x]=max(maxx[pre[x]][y],d[x]);
if(!ha[y]&&d[y]>w[x][y]) {
d[y]=w[x][y];
pre[y]=x;
q.push(make_pair(-d[y],y));
}
}
}
return res;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
memset(w,0x3f,sizeof(w));
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
w[x][y]=w[y][x]=z;
}
int ans=Prim(1);
bool flag=false;
for(int x=1;x<=n&&!flag;x++)
{
for(int y=1;y<=n;y++)
{
if(mst[x][y]||w[x][y]==inf) continue;
if(w[x][y]==maxx[x][y])
{
flag=true;
break;
}
}
}
if(flag) printf("Not Unique!\n");
else printf("%d\n",ans);
}
return 0;
}
这个因为是按权值排序的，后更新的一定比先更新的大：
这题数据是真水。。。。
怎么写几乎都能过：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=108;
const int inf=0x3f3f3f3f;
int n,m;
struct node
{
int x,y,z;
}a[maxn*maxn];
bool ha[maxn*maxn];
int maxx[maxn][maxn];
int f[maxn];
vector<int>mst[maxn];
bool cmp(const node &a,const node &b)
{
return a.z<b.z;
}
int fi(int x)
{
if(x!=f[x])
f[x]=fi(f[x]);
return f[x];
}
int ku(void)
{
sort(a+1,a+m+1,cmp);
memset(maxx,0,sizeof(maxx));
memset(ha,0,sizeof(ha));
for(int i=1;i<maxn;i++)
{
f[i]=i;
mst[i].clear();
mst[i].push_back(i);
}
int ans=0;
int cnt=0;
for(int i=1;i<=m;i++)
{
int xx=fi(a[i].x);
int yy=fi(a[i].y);
if(xx==yy) continue;
ans+=a[i].z;
cnt++;
ha[i]=true;
f[xx]=yy;
for(int j=0;j<mst[xx].size();j++)
{
for(int k=0;k<mst[yy].size();k++)
{
maxx[mst[xx][j]][mst[yy][k]]=maxx[mst[yy][k]][mst[xx][j]]=a[i].z;
}
}
for(int j=0;j<mst[xx].size();j++)
mst[yy].push_back(mst[xx][j]);
}
if(cnt!=n-1) return -1;
if(m==n-1) return ans;
int res=inf;
for(int i=1;i<=m;i++)
{
if(!ha[i])
res=min(res,ans+a[i].z-maxx[a[i].x][a[i].y]);
}
return res>ans?ans:-1;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
}
int ans=ku();
if(ans==-1) printf("Not Unique!\n");
else printf("%d\n",ans);
}
return 0;
}
京公网安备 11010502036488号