poj1741，【POJ】【3164】Commond Network

2023-11-19 阅读 25 评论 0

摘要：最小樹形圖　　最小樹形圖模板題，朱-劉算法。　　題解：http://blog.csdn.net/shuangde800/article/details/8039359 　　這位大神代碼寫的非常通俗易懂，而且這種代碼風格也很值得學習……面向對象？= =聽說這樣封裝起來可以避免using na

最小樹形圖

　　最小樹形圖模板題，朱-劉算法。

　　題解：http://blog.csdn.net/shuangde800/article/details/8039359

　　這位大神代碼寫的非常通俗易懂，而且這種代碼風格也很值得學習……面向對象？= =聽說這樣封裝起來可以避免using namespace std;出現的奇葩錯誤

poj1741。寫錯的地方：一開始找最小前驅邊的時候把 “!inc[i]"的嘆號丟了……

  1 //POJ 3164
  2 #include<cmath>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<iostream>
  7 #include<algorithm>
  8 #define rep(i,n) for(int i=0;i<n;++i)
  9 #define F(i,j,n) for(int i=j;i<=n;++i)
 10 #define D(i,j,n) for(int i=j;i>=n;--i)
 11 using namespace std;
 12 void read(int &v){
 13     v=0; int sign=1; char ch=getchar();
 14     while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
 15     while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
 16     v*=sign;
 17 }
 18 /******************tamplate*********************/
 19 const int N=110;
 20 const int INF=~0u>>2;
 21 template<typename Type>
 22 class Directed_MST{
 23     public:
 24     void init(int _n){
 25         n=_n;
 26         ans=0;
 27         memset(vis,0,sizeof vis);
 28         memset(inc,0,sizeof inc);
 29         F(i,0,n){
 30             w[i][i]=INF;
 31             F(j,i+1,n) w[i][j]=w[j][i]=INF;
 32         }
 33     }
 34     void insert(int x,int y,Type _w){
 35         if (w[x][y]>_w) w[x][y]=_w;
 36     }
 37     Type directed_mst(int x){
 38 #ifdef debug
 39         F(i,1,n){
 40             F(j,1,n) 
 41                 if (w[i][j]==INF) printf(" INF ");
 42                 else printf("%.2f ",w[i][j]);
 43             printf("\n");
 44         }
 45 #endif
 46         // step1 判斷能否形成最小樹形圖，直接dfs遍歷
 47         dfs(x);
 48         F(i,1,n) if(!vis[i]) return -1;
 49         
 50         // 如果可以形成最小樹形圖，繼續
 51         // step2
 52         memset(vis,0,sizeof vis);
 53         while(1){
 54             //1.找最小前驅邊
 55             F(i,1,n) if (i!=x && !inc[i]){
 56                 w[i][i]=INF, pre[i]=i;
 57                 F(j,1,n) 
 58                     if(!inc[j] && w[j][i]<w[pre[i]][i])
 59                         pre[i]=j;
 60             }
 61             //2.判斷是否有環
 62             int i;
 63             for(i=1;i<=n;++i) if (i!=x && !inc[i]){
 64                 int j=i,cnt=0;
 65                 while(j!=x && pre[j]!=i && cnt<=n) j=pre[j],++cnt;
 66                 if (j==x || cnt>n) continue;
 67                 break;
 68             }
 69                 
 70             //沒有找到環，找到答案
 71             if (i>n){
 72                 F(i,1,n)
 73                     if (i!=x && !inc[i]) ans+=w[pre[i]][i];
 74                 return ans;
 75             }
 76             //有環，進行收縮
 77             int j=i;
 78             memset(vis,0,sizeof vis);
 79             do{
 80                 ans+=w[pre[j]][j],j=pre[j],vis[j]=inc[j]=true;
 81             }while(j!=i);
 82             inc[i]=false;//!!!!環縮成了點i,點i依然存在
 83             
 84             //收縮
 85             F(k,1,n) if(vis[k])
 86                 F(j,1,n) if(!vis[j]){
 87                     if (w[i][j]>w[k][j]) w[i][j]=w[k][j];
 88                     if (w[j][k]<INF && w[j][k]-w[pre[k]][k] < w[j][i])
 89                         w[j][i]=w[j][k]-w[pre[k]][k];
 90                 }
 91         }
 92         return ans;
 93     }
 94 
 95     private:
 96     void dfs(int x){
 97         vis[x]=1;
 98         F(i,1,n) if (!vis[i] && w[x][i]<INF)
 99             dfs(i);
100     }
101     private:
102     Type ans;
103     int n;
104     int pre[N];
105     bool vis[N],inc[N];
106     Type w[N][N];
107 };
108 struct node{
109     double x,y;
110     double operator - (const node&now)const{
111         return sqrt( (x-now.x)*(x-now.x)+(y-now.y)*(y-now.y) );
112     }
113 }a[N];
114 
115 Directed_MST<double>G;
116 
117 int main(){
118     int n,m,x,y;
119     while(scanf("%d%d",&n,&m)!=EOF){
120         G.init(n);
121         F(i,1,n) scanf("%lf%lf",&a[i].x,&a[i].y);
122         
123         F(i,1,m){
124             scanf("%d%d",&x,&y);
125             if (x==y) continue;
126             G.insert(x,y,a[x]-a[y]);
127         }
128         double ans=G.directed_mst(1);
129         if (ans<0) puts("poor snoopy");
130         else printf("%.2f\n",ans);
131     }
132     return 0;
133 }

View Code

轉載于:https://www.cnblogs.com/Tunix/p/4245048.html

原文链接：https://hbdhgg.com/4/180990.html

发表评论: