POJ 1679 The Unique MST

正文索引 [隐藏]

题目大意
题解
代码

题目大意

判读一个 N 个点 M 条边的图的最小生成树是否唯一，唯一则输出最小生成树。

题解

第一种方法：
最小生成树至少有一条边与次小生成树不一样。所以最小生成树之后枚举去掉最小生成树里的一条边，再做最小生成树看看答案是否相同，相同则不唯一。
第二种方法：
枚举不在最小生成树上的一条边(u,v)，删除最小生成树中 u ~ v 边权最大的边，并且将 (u,v) 加入最小生成树

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=100;
struct Edge{
    int u,v;
    int w;
    bool inUse;
};
Edge e[Maxn*Maxn+5];
inline bool cmpEdge(Edge a,Edge b){
    return a.w<b.w;
}
int fa[Maxn+5];
inline void initFather(){
    for(int i=0;i<=Maxn;i++) fa[i]=i;
}
int getFather(int x){
    return fa[x]=fa[x]==x?x:getFather(fa[x]);
}
inline void mergeFather(int x,int y){
    int fx=getFather(x),fy=getFather(y);
    if (fx==fy) return ;
    if (fx<fy){
        fa[fx]=fy;
    }else{
        fa[fy]=fx;
    }
}
int n,m;
inline int MST(int ban){
    initFather();
    int ret=0;
    int cnt=n;
    for (int i=1;i<=m;i++){
        if (ban==i) continue;
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (getFather(u)==getFather(v)) continue;
        if (ban==0) e[i].inUse=true;
        ret+=w;
        cnt--;
        mergeFather(u,v);
        if (cnt==1) break;
    }
    if (cnt!=1) return -1;
    return ret;
}
inline void solve(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        e[i].inUse=false;
    }
    sort(e+1,e+m+1,cmpEdge);
    int Ans=MST(0);
    for (int i=1;i<=m;i++){
        if (e[i].inUse){
            if (Ans==MST(i)){
                printf("Not Unique!\n");
                return ;
            }
        }
    }
    if (Ans==-1)
        printf("Not Unique!\n");
    else
        printf("%d\n",Ans);
}
int main(){
    freopen("in.txt","r",stdin);
    int T;
    while(scanf("%d",&T)!=EOF)
        for (int i=1;i<=T;i++)
            solve();
    return 0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

const int Maxn=100;

struct Edge{

int u,v;

int w;

bool inUse;

};

Edge e[Maxn*Maxn+5];

inline bool cmpEdge(Edge a,Edge b){

return a.w<b.w;

}

int fa[Maxn+5];

inline void initFather(){

for(int i=0;i<=Maxn;i++) fa[i]=i;

}

int getFather(int x){

return fa[x]=fa[x]==x?x:getFather(fa[x]);

}

inline void mergeFather(int x,int y){

int fx=getFather(x),fy=getFather(y);

if (fx==fy) return ;

if (fx<fy){

fa[fx]=fy;

}else{

fa[fy]=fx;

}

int n,m;

inline int MST(int ban){

initFather();

int ret=0;

int cnt=n;

for (int i=1;i<=m;i++){

if (ban==i) continue;

int u=e[i].u,v=e[i].v,w=e[i].w;

if (getFather(u)==getFather(v)) continue;

if (ban==0) e[i].inUse=true;

ret+=w;

cnt--;

mergeFather(u,v);

if (cnt==1) break;

}

if (cnt!=1) return -1;

return ret;

}

inline void solve(){

scanf("%d%d",&n,&m);

for (int i=1;i<=m;i++){

scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

e[i].inUse=false;

}

sort(e+1,e+m+1,cmpEdge);

int Ans=MST(0);

for (int i=1;i<=m;i++){

if (e[i].inUse){

if (Ans==MST(i)){

printf("Not Unique!\n");

return ;

}

if (Ans==-1)

printf("Not Unique!\n");

else

printf("%d\n",Ans);

}

int main(){

freopen("in.txt","r",stdin);

int T;

while(scanf("%d",&T)!=EOF)

for (int i=1;i<=T;i++)

solve();

return 0;

}

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int Maxn=100;
struct Edge{
    int v,w,nxt;
    Edge(){}
    Edge(int v0,int w0,int n0){
        v=v0;
        w=w0;
        nxt=n0;
    }
};
Edge e[Maxn*2+5];
int head[Maxn+5];
int nume;
inline void addEdge(int u,int v,int w){
    e[++nume]=Edge(v,w,head[u]);
    head[u]=nume;
    e[++nume]=Edge(u,w,head[v]);
    head[v]=nume;
}
struct NormalEdge{
    int u,v,w;
    bool inUse;
};
inline bool cmpNormalEdge(NormalEdge a,NormalEdge b){
    return a.w<b.w;
}
NormalEdge ne[Maxn*Maxn+5];
int fa[Maxn+5];
inline void initFather(){
    for (int i=1;i<=Maxn;i++)fa[i]=i;
}
int getFather(int x){
    return fa[x]=fa[x]==x?x:getFather(fa[x]);
}
inline void mergeFather(int x,int y){
    int fx=getFather(x),fy=getFather(y);
    if (fx==fy) return;
    if (fx<fy){
        fa[fx]=fy;
    }else{
        fa[fy]=fx;
    }
}
int n,m;
inline int MST(){
    sort(ne+1,ne+m+1,cmpNormalEdge);
    initFather();
    int ret=0,cnt=n;
    for (int i=1;i<=m;i++){
        int u=ne[i].u,v=ne[i].v,w=ne[i].w;
        if (getFather(u)==getFather(v)) continue;
        addEdge(u,v,w);
        ne[i].inUse=true;
        cnt--;
        ret+=w;
        mergeFather(u,v);
        if (cnt==1) break;
    }
    if (cnt!=1) return -1;
    return ret;
}
int dist[Maxn+5][Maxn+5];
queue<int> que;
bool vis[Maxn+5];
inline void bfs(int x){
    dist[x][x]=0;
    memset(vis,false,sizeof(vis));
    vis[x]=true;
    while(!que.empty()) que.pop();
    que.push(x);
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for (int i=head[now];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if (!vis[v]){
                dist[x][v]=max(dist[x][now],w);
                vis[v]=true;
                que.push(v);
            }
        }
    }
}
inline int SMST(int MST_Ans){
    if (MST_Ans==-1) return -1;
    int ret=2100000000;
    for (int i=1;i<=n;i++) bfs(i);
    for (int i=1;i<=m;i++){
        if (!ne[i].inUse){
            int u=ne[i].u,v=ne[i].v,w=ne[i].w;
            ret=min(ret,MST_Ans-dist[u][v]+w);
        }
    }
    return ret;
}
inline void solve(){
    memset(dist,0,sizeof(dist));
    memset(head,0,sizeof(head));
    nume=0;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d%d%d",&ne[i].u,&ne[i].v,&ne[i].w);
        ne[i].inUse=false;
    }
    int Ans=MST();
    int Ans_SMST=SMST(Ans);
    if (Ans_SMST==Ans){
        printf("Not Unique!\n");
    }else{
        printf("%d\n",Ans);
    }
}
int main(){
    freopen("in.txt","r",stdin);
    int T;
    while(scanf("%d",&T)!=EOF)
        for (int i=1;i<=T;i++)
            solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<queue>

using namespace std;

const int Maxn=100;

struct Edge{

int v,w,nxt;

Edge(){}

Edge(int v0,int w0,int n0){

v=v0;

w=w0;

nxt=n0;

}

};

Edge e[Maxn*2+5];

int head[Maxn+5];

int nume;

inline void addEdge(int u,int v,int w){

e[++nume]=Edge(v,w,head[u]);

head[u]=nume;

e[++nume]=Edge(u,w,head[v]);

head[v]=nume;

}

struct NormalEdge{

int u,v,w;

bool inUse;

};

inline bool cmpNormalEdge(NormalEdge a,NormalEdge b){

return a.w<b.w;

}

NormalEdge ne[Maxn*Maxn+5];

int fa[Maxn+5];

inline void initFather(){

for (int i=1;i<=Maxn;i++)fa[i]=i;

}

int getFather(int x){

return fa[x]=fa[x]==x?x:getFather(fa[x]);

}

inline void mergeFather(int x,int y){

int fx=getFather(x),fy=getFather(y);

if (fx==fy) return;

if (fx<fy){

fa[fx]=fy;

}else{

fa[fy]=fx;

}

int n,m;

inline int MST(){

sort(ne+1,ne+m+1,cmpNormalEdge);

initFather();

int ret=0,cnt=n;

for (int i=1;i<=m;i++){

int u=ne[i].u,v=ne[i].v,w=ne[i].w;

if (getFather(u)==getFather(v)) continue;

addEdge(u,v,w);

ne[i].inUse=true;

cnt--;

ret+=w;

mergeFather(u,v);

if (cnt==1) break;

}

if (cnt!=1) return -1;

return ret;

}

int dist[Maxn+5][Maxn+5];

queue<int> que;

bool vis[Maxn+5];

inline void bfs(int x){

dist[x][x]=0;

memset(vis,false,sizeof(vis));

vis[x]=true;

while(!que.empty()) que.pop();

que.push(x);

while(!que.empty()){

int now=que.front();

que.pop();

for (int i=head[now];i;i=e[i].nxt){

int v=e[i].v,w=e[i].w;

if (!vis[v]){

dist[x][v]=max(dist[x][now],w);

vis[v]=true;

que.push(v);

}

inline int SMST(int MST_Ans){

if (MST_Ans==-1) return -1;

int ret=2100000000;

for (int i=1;i<=n;i++) bfs(i);

for (int i=1;i<=m;i++){

if (!ne[i].inUse){

int u=ne[i].u,v=ne[i].v,w=ne[i].w;

ret=min(ret,MST_Ans-dist[u][v]+w);

}

return ret;

}

inline void solve(){

memset(dist,0,sizeof(dist));

memset(head,0,sizeof(head));

nume=0;

scanf("%d%d",&n,&m);

for (int i=1;i<=m;i++){

scanf("%d%d%d",&ne[i].u,&ne[i].v,&ne[i].w);

ne[i].inUse=false;

}

int Ans=MST();

int Ans_SMST=SMST(Ans);

if (Ans_SMST==Ans){

printf("Not Unique!\n");

}else{

printf("%d\n",Ans);

}

int main(){

freopen("in.txt","r",stdin);

int T;

while(scanf("%d",&T)!=EOF)

for (int i=1;i<=T;i++)

solve();

return 0;

}

WNJXYKの博客

喂你脚下有坑