当前位置:编程学习 > C/C++ >>

POJ 3164 Command Network

   这是最小树形图的题目,1是根节点,在开始的时候自己建图。

输入n,m;代表有n个结点,接下来n行给出结点的坐标。

接下来m行给出i,j两个整数,代表i到j有连通,求出i到j的坐标距离,最后求最小树形图。

用朱刘算法可以解决。

代码:


[cpp]
#include<iostream> 
#include<algorithm> 
#include<string.h> 
#include<cmath> 
using namespace std; 
const int maxn=105; 
#define INF 0x7fffffff 
double map[maxn][maxn],visit[maxn]; 
int pt[maxn][2],n,pre[maxn]; 
double Dist(int i,int j) 

       return sqrt(pow(pt[i][0]-pt[j][0],2.0)+pow(pt[i][1]-pt[j][1],2.0)); 

void DFS(int u) 

     visit[u]=true; 
     for(int i=1; i<=n; i++) 
          if( !visit[i]&&map[u][i]<INF) 
              DFS(i); 

bool Connected() //判断是否连通,如果连通一定存在最小树形图。 

     memset(visit,false,sizeof(visit)); 
     int i,cnt=0; 
     DFS(1); 
     for( i=1; i<=n; i++) 
          if( !visit[i]) 
              return false; 
     return true; 

double ZLEdmonds(){ 
    int i,j,k; 
    bool circle[maxn]; 
    double ans=0; 
    memset(circle,false,sizeof(circle)); 
    while(true){ 
        for(i=2;i<=n;i++){//找出最短弧集合E0 
            if(circle[i]) continue; 
            pre[i]=i; 
            map[i][i]=INF; 
            for(j=1;j<=n;j++){ 
                if(circle[j]) continue; 
                if(map[j][i]<map[pre[i]][i]) 
                    pre[i]=j; 
            } 
        } 
        for(i=2;i<=n;i++){ 
            if(circle[i]) continue; 
            j=i; 
            memset(visit,false,sizeof(visit)); 
            while(!visit[j] && j!=1){ 
                visit[j]=true; 
                j=pre[j]; 
            } 
            if(j==1) continue;  //检查是否有环,能找到根节点说明没环 
            i=j; 
            ans+=map[pre[i]][i]; 
            for(j=pre[i];j!=i;j=pre[j]){  //i不用标记,用作后面缩点用  
                ans+=map[pre[j]][j]; 
                circle[j]=true; 
            } 
            for(j=1;j<=n;j++){ 
                if(circle[j]) continue; 
                if(map[j][i]!=INF) 
                    map[j][i]-=map[pre[i]][i]; 
            } 
            for(j=pre[i];j!=i;j=pre[j]) //将环中所有的点成点i,改变边 
                for(k=1;k<=n;k++){ 
                    if(circle[k]) continue; 
                    map[i][k]=min(map[i][k],map[j][k]); 
                    if(map[k][j]!=INF) 
                        map[k][i]=min(map[k][i],map[k][j]-map[pre[j]][j]); 
                } 
            break; 
        } 
        if(i>n){  //求出最小树形图的权值 
            for(j=2;j<=n;j++){ 
                if(circle[j]) continue; 
                ans+=map[pre[j]][j]; 
            } 
            break; 
        } 
    } 
    return ans;  

int main() 

    int m,i,j; 
    while( scanf("%d%d",&n,&m)!=EOF){ 
           for( i=1; i<=n; i++) 
                for( j=1; j<=n; j++) 
                     map[i][j]=INF; 
           for( i=1; i<=n; i++) 
                scanf("%d%d",&pt[i][0],&pt[i][1]); 
      &

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,