本文共 2364 字，大约阅读时间需要 7 分钟。
求次小生成树的两种方法。
第一种：Kruskal算法比较好操作。先求一遍最小生成树，然后再记录最小生成树上的边。然后再枚举删去最小生成树上的边，再求最小生成树，如果求出的最小生成树的花费等于第一次最小生成树的花费，则最小生成树不是唯一的。注意删边之后图可能是不连通的。
第二种：prim算法变形，用一个MAX[i][j]数组维护i点到j点路径上最长的边。然后再枚举不在最小生成树上的边，假设这条边为u到v权值为w，判断w是否等于max[u][v]，如果等于，则可以删去那条边，加入这条边，所以最小生成树就不是唯一的了。
POJ 1679 The Unique MST
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)#define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t))#define rep(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)#define repp(i,a,b,t) for(int (i)=(a);(i)>=(b);(i)-=(t))#define PII pair #define fst first#define snd second#define MP make_pair#define PB push_back#define RI(x) scanf("%d",&(x))#define RII(x,y) scanf("%d%d",&(x),&(y))#define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))#define DRI(x) int (x);scanf("%d",&(x))#define DRII(x,y) int (x),(y);scanf("%d%d",&(x),&(y))#define DRIII(x,y,z) int (x),(y),(z);scanf("%d%d%d",&(x),&(y),&(z))#define RS(x) scanf("%s",x)#define RSS(x,y) scanf("%s%s",x,y)#define DRS(x) char x[maxn];scanf("%s",x)#define DRSS(x,y) char x[maxn],y[maxn];scanf("%s%s",x,y)#define MS0(a) memset((a),0,sizeof((a)))#define MS1(a) memset((a),-1,sizeof((a)))#define MS(a,b) memset((a),(b),sizeof((a)))#define ALL(v) v.begin(),v.end()#define SZ(v) (int)(v).size()using namespace std;const int INF=(1<<29);const int maxn=100000;int cost[110][110];int Max[110][110];bool vise[110][110];bool vis[110];int dist[110];int pre[110];int T,n,m,u,v,w,ans,flag;int main(){ //freopen("in.txt","r",stdin); cin>>T; while(T--) { cin>>n>>m; for(int i=0;i<110;i++) for(int j=0;j<110;j++) cost[i][j]=INF; for(int i=0;i >u>>v>>w; cost[u][v]=cost[v][u]=w; } memset(vise,0,sizeof(vise)); memset(Max,0,sizeof(Max)); for(int i=0;i<110;i++) dist[i]=INF,vis[i]=false,pre[i]=0; dist[1]=0;ans=0;flag=0; while(1) { int v=-1; for(int u=1;u<=n;u++) if(!vis[u]&&(v==-1||dist[u] cost[v][u]) { pre[u]=v; dist[u]=cost[v][u]; } } } for(int i=1;i<=n&&!flag;i++) for(int j=1;j<=n;j++) if(!vise[i][j]&&cost[i][j]==Max[i][j]) { flag=1; printf("Not Unique!\n"); break; } if(!flag) printf("%d\n",ans); } return 0;}
转载于:https://www.cnblogs.com/onlyAzha/p/4793031.html
