MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
这个代码还没有测试过,有错误指出

#include <stdio.h>
#include 
<string.h>
#include 
<queue>
using namespace std;
struct cut_edge{
    
int p, d;
    cut_edge(
int a, int b){p = a; d = b;}
    
bool operator < (const cut_edge& o) const{
        
if(d != o.d)return d > o.d;
        
return p > o.p;
    }
};
priority_queue
<cut_edge> pq, pp;//队列中放的是通过割的边,利用有限队列来优化找轻边
int m, n, map[100][100], d[100];
bool judge[100];//在生成树和不在的两个集合  false 为不在  true 为在
void mst_pq(){
    
int i, j, k, t, w, ans = 0, count = 0, dd;
    
while(!pq.empty()){
        t 
= pq.top().p;dd = pq.top().d;pq.pop();
        
if(!judge[t]){//这里可能一个点入队2此,但是不影响计算。
            count++;
            judge[t] 
= true;ans += dd;
            
for(i = 1; i <= n; i++){
                
if(map[t][i] && !judge[i] && (d[i] == -1 || map[t][i] < d[i])){
                    d[i] 
= map[t][i];
                    pq.push(cut_edge(i, d[i]));
                }
            }
        }
    }
    printf(
"count = %d   ans = %d\n", count, ans);
}
int main(){
    freopen(
"prime.in""r", stdin);
    freopen(
"prime.out""w", stdout);
    
int i, j, u, v, w;
    
while(scanf("%d%d"&n, &m) != -1){
        memset(judge, 
0sizeof(judge));
        memset(map, 
0sizeof(map));
        memset(d, 
-1sizeof(d));
        
for(i = 0; i < m; i++){
            scanf(
"%d%d%d"&u, &v, &w);
            map[u][v] 
= map[v][u] = w;
        }pq 
= pp;pq.push(cut_edge(10));
        mst_pq();
    }
    
return 0;
}


posted on 2009-10-06 23:33 memorygarden 阅读(117) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理