kuangbin专题六最小生成树【从入门到熟练】【5题】

太过爱你忘了你带给我的痛 2021-09-30 09:04 178阅读 0赞

POJ 2031 Building a Space Station

猜一个结论两个球体间的最短距离是圆心间距离减去两个球的半径，如果是负数就说明相交。

然后理解了三维上两个点之间的距离怎么求

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//#include<bits/stdc++.h>
    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<cmath>
    #include<vector>
    #define inf 2e9
    #define maxnode 200000
    #define ll long long
    #define lowbit(x) (x&(-x))
    const int mod = 1e9 + 7;
    const int maxn = 1e5 + 10;
    int dx[4]={
         0,0,1,-1};
    int dy[4]={
         1,-1,0,0};
    using namespace std;
    
    int par[105],cnt;
    struct edge{
        int u,v;
        double cost;
        edge(int u1=0,int v1=0,double c1=0): u(u1),v(v1),cost(c1) {}
    }edges[10010];
    bool cmp(edge n1,edge n2){
        return n1.cost<n2.cost;
    }
    
    int find_root(int x){
        if( x==par[x] ) return x;
        return par[x] = find_root( par[x] );
    }
    
    double x[105],y[105],z[105],r[105];
    
    double find_dist(int i,int j){
        //圆心间距离
        double dis = sqrt( abs(x[i]-x[j])*abs(x[i]-x[j]) + abs(y[i]-y[j])*abs(y[i]-y[j]) + abs(z[i]-z[j])*abs(z[i]-z[j]) );
        dis-=r[i]; dis-=r[j];
        return dis;
    }
    
    int main(){
        int n;
        while(1){
            cin>>n; if(n==0) break;
    
            cnt=0;
            for(int i=1;i<=n;i++) par[i]=i;
    
            for(int i=1;i<=n;i++) cin>>x[i]>>y[i]>>z[i]>>r[i];
            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
         //find distance
                    double dist = find_dist(i,j);
                    if( dist<=0 ){
         //i跟j一开始就在一个集合
                        int rooti = find_root(i), rootj = find_root(j);
                        par[rooti] = rootj;
                    }
                    else edges[++cnt] = edge(i,j,dist);
                }
            }
            sort(edges+1,edges+1+cnt,cmp);
            //for(int i=1;i<=cnt;i++) cout<<edges[i].u<<" "<<edges[i].v<<" "<<edges[i].cost<<endl;
            double ans=0;
            for(int i=1;i<=cnt;i++){
                int u = edges[i].u,v=edges[i].v;
                int rootu = find_root(u), rootv = find_root(v);
                if( rootu!=rootv  ){
                    par[rootu] = rootv;
                    ans+=edges[i].cost;
                }
            }
            printf("%.3lf\n",ans);
    
        }
    
    
        return 0;
    }

POJ 1789 Truck History

如果把每个Truck当作一个顶点的话，那任意一颗生成树都能对应上一个derive的方案，那就是求MST

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//#include<bits/stdc++.h>
    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<cmath>
    #include<vector>
    #define inf 2e9
    #define maxnode 200000
    #define ll long long
    #define lowbit(x) (x&(-x))
    const int mod = 1e9 + 7;
    const int maxn = 2e3 + 10;
    int dx[4]={
         0,0,1,-1};
    int dy[4]={
         1,-1,0,0};
    using namespace std;
    
    int dist[maxn],vis[maxn];//从mst集合到这个点的距离
    
    int a[maxn][maxn];
    char trucks[maxn][10];
    int find_difference(int i,int j){
        int ans=0;
        for(int k=0;k<7;k++){
            if( trucks[i][k]!=trucks[j][k] ) ans++;
        }
        return ans;
    }
    
    int main(){
        int n;
        while( scanf("%d",&n)){
            if(n==0) break;
    
            for(int i=1;i<=n;i++) scanf("%s",trucks[i]);
            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                    a[i][j] = a[j][i] = find_difference(i,j);
                }
            }
            memset(vis,0,sizeof(vis));
            //mst
            int ans=0;
            for(int i=2;i<=n;i++){
                dist[i] = a[1][i];
            }
    
            for(int i=2;i<=n;i++){
                int mind=10,index;
                for(int j=2;j<=n;j++){
                    if( vis[j]==0 && dist[j]<mind ) { mind=dist[j]; index=j; }
                }
                //
                ans+=dist[index]; vis[index]=1;
                for(int j=2;j<=n;j++){
                    if( j!=index && dist[j]>a[index][j] ) dist[j] = a[index][j];
                }
            }
    
            printf("The highest possible quality is 1/%d.\n",ans);
    
        }
        
    
    
        return 0;
    }

POJ 2349 Arctic Network

知道结论：所有最小生成树边按边的权值排序后，序列一样

找第k大的边就行了（其原因可以靠贪心去证明）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//#include<bits/stdc++.h>
    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<cmath>
    #include<vector>
    #define inf 2e9
    #define maxnode 200000
    #define ll long long
    #define lowbit(x) (x&(-x))
    const int mod = 1e9 + 7;
    const int maxn = 5e2 + 10;
    int dx[4]={
         0,0,1,-1};
    int dy[4]={
         1,-1,0,0};
    using namespace std;
    
    int a[maxn][maxn],dist[maxn];
    int x[maxn],y[maxn],vis[maxn];
    
    int find_dist(int i,int j){
        return abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]);
    }
    
    int main(){
        int t; scanf("%d",&t);
        while( t-- ){
            int s,n; scanf("%d%d",&s,&n);
            for(int i=1;i<=n;i++) scanf("%d%d",x+i,y+i);
            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                    a[i][j] = a[j][i] = find_dist(i,j);
                 //   cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
                }
            }
            memset(vis,0,sizeof(vis));
            //mst
            for(int i=2;i<=n;i++) dist[i] = a[1][i];
            vector<int> edge; edge.clear();
    
            for(int i=2;i<=n;i++){
                int mind=inf,index;
                for(int j=2;j<=n;j++){ if( vis[j]==0 && dist[j]<mind ) { mind=dist[j]; index=j; } }
               // cout<<"!!! "<<index<<" "<<dist[index]<<endl;
                edge.push_back(dist[index]); vis[index]=1;
                for(int j=2;j<=n;j++){ if( j!=index && dist[j]>a[index][j] ) dist[j] = a[index][j]; }
            }
    
           // for(int i=0;i<edge.size();i++) cout<<edge[i]<<" "; cout<<endl;
            sort(edge.begin(),edge.end()); reverse(edge.begin(),edge.end());
           // for(int i=0;i<edge.size();i++) cout<<edge[i]<<" "; cout<<endl;
            printf("%.2lf\n",sqrt( double(edge[ s-1  ]) ) );
        }
        
    
    
        return 0;
    }

POJ 3026 Borg Maze

bfs + kruskal

主要是建模

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//#include<bits/stdc++.h>
    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<cstring>
    #include<map>
    #include<vector>
    #define inf 2e9
    #define maxnode 200000
    #define ll long long
    #define lowbit(x) (x&(-x))
    const int mod = 1e9 + 7;
    const int maxn = 5e2 + 10;
    int dx[4]={
         0,0,1,-1};
    int dy[4]={
         1,-1,0,0};
    using namespace std;
    
    int par[maxn],cnt,mp[maxn][maxn];
    struct edge{
        int u,v,cost;
        edge(int u1=0,int v1=0,int c1=0): u(u1),v(v1),cost(c1) {}
    }edges[maxn*maxn];
    bool cmp(edge n1,edge n2){
        return n1.cost<n2.cost;
    }
    
    int find_root(int x){
        if( x==par[x] ) return x;
        return par[x] = find_root( par[x] );
    }
    
    int x[maxn],y[maxn],vis[maxn][maxn],n,m,mat[maxn][maxn];
    char a[maxn][maxn];
    
    struct node{
        int x,y,step;
        node(int x1=0,int y1=0,int s1=0): x(x1),y(y1),step(s1) {}
    };
    
    void bfs(int s){
        queue<node> q; 
        memset(vis,0,sizeof(vis));
        q.push( node(x[s],y[s],0) ); vis[ x[s] ][ y[s] ]=1;
        while( !q.empty() ){
            node u=q.front(); q.pop();
            if( mp[u.x][u.y] ) mat[s][ mp[u.x][u.y] ] = u.step;
            for(int k=0;k<4;k++){
                int x1=u.x+dx[k];
                int y1=u.y+dy[k];
                if( x1>=1 && x1<=n && y1>=1 && y1<=m && a[x1][y1]!='#' && vis[x1][y1]==0 ){
                    vis[x1][y1]=1;
                    q.push( node(x1,y1,u.step+1) );
                }
            }
        }
    
    }
    
    int main(){
        int t,tc=0; scanf("%d",&t);
        while( t-- ){
    
            scanf("%d%d",&m,&n); char temp[51]; gets(temp);
            memset(mp,0,sizeof(mp));
            cnt=0;
    
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    scanf("%c",&a[i][j]);
                    if( a[i][j]=='S' || a[i][j]=='A' ) { x[++cnt]=i; y[cnt]=j; mp[i][j]=cnt; }
                }
                getchar();
            }
    
            for(int i=1;i<=cnt;i++) bfs(i);
            for(int i=1;i<=cnt;i++) par[i]=i;
            
            int cnt_edge=0;
            for(int i=1;i<=cnt;i++)
                for(int j=i+1;j<=cnt;j++) edges[++cnt_edge] = edge(i,j, mat[i][j] );
    
            sort(edges+1,edges+1+cnt_edge,cmp);
    
            int ans=0;
            for(int i=1;i<=cnt_edge;i++){
                int u = edges[i].u,v=edges[i].v;
                int rootu = find_root(u), rootv = find_root(v);
                if( rootu!=rootv  ){
                    par[rootu] = rootv;
                    ans+=edges[i].cost;
                }
            }
    
            printf("%d\n",ans);
        }
    
    
        return 0;
    }

POJ 1679 The Unique MST

次小生成树

求出数组mat\[u\]\[v\]表示最小生成树上u到v路径上的最长边边权，

那么mat\[ u \]\[ v \] = mat\[ v \]\[ u \] = max( mat\[ u \]\[ pre\[v\] \] , dist\[v\] ) 不会被迭代更新，只是在v第一次接到最小生成树上的时候确定所有已经在生成树上的点到该点的最长边距离

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//#include<bits/stdc++.h>
    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<cmath>
    #include<vector>
    #define inf 2e9
    #define maxnode 200000
    #define ll long long
    #define lowbit(x) (x&(-x))
    const int mod = 1e9 + 7;
    const int maxn = 1e2 + 10;
    int dx[4]={
         0,0,1,-1};
    int dy[4]={
         1,-1,0,0};
    using namespace std;
    
    int mp[maxn][maxn],dist[maxn],pre[maxn];
    int mat[maxn][maxn],used[maxn][maxn],vis[maxn];//mat[u][v] u到v最短路径的最长距离
    
    int main(){
        int t; cin>>t;
        while( t-- ){
            int n,m; cin>>n>>m;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++) mp[i][j]=inf;
            memset(used,0,sizeof(used));
            memset(mat,0,sizeof(mat));
            memset(vis,0,sizeof(vis));
            
    
            for(int i=1;i<=m;i++){
                int u,v,d; cin>>u>>v>>d;
                mp[u][v]=mp[v][u]=d;
            }
    
            vis[1]=1;
            for(int i=2;i<=n;i++) { dist[i]=mp[1][i]; pre[i]=1; }
    
            int ans=0;
            for(int i=2;i<=n;i++){
                int mind=inf,index;
                for(int j=2;j<=n;j++){
                    if( !vis[j] && dist[j]<mind ) { mind=dist[j]; index=j; } 
                }
                //找到要加入vis的顶点index
                used[index][pre[index]] = used[pre[index]][index]= 1;
                vis[index]=1;
                ans+=dist[index];
                for(int j=2;j<=n;j++){
                    if( vis[j] ) mat[j][index] = mat[index][j] = max( mat[j][pre[index]],dist[index] );
                    if( !vis[j] && mp[index][j]<dist[j] ){
                        dist[j]=mp[index][j];
                        pre[j]=index;
                    }
                }
    
            }
            //mst长度，并且mat维护出来
            int minlen=inf;
            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                    if( used[i][j]==0 && mp[i][j]!=inf ){
                        minlen = min( minlen,ans+mp[i][j]-mat[i][j] );
                    }
                }
            }
            if( minlen==ans ) cout<<"Not Unique!"<<endl;
            else cout<<ans<<endl;
    
        }
        
    
    
        return 0;
    }

转载于:https://www.cnblogs.com/ZhenghangHu/p/10259099.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/04736686b7e544c78d69da1b1fd76c2d.png