Toj 2248 Channel Design 解题报告

【题意分析】

给一个有向图求最小生成树。由于是有向图所以prim和kruskal是不能解决的。这里涉及到一个求有向图最小生成树的算法叫做最小树形图。

【算法分析】

1.把这个图消去自环

2.给除了根以外的每个点找到一个最小的入边

3.如果这个最小入边集中不含有向环的话我们就可以证明这个集合就是该图的最小生成树了。

4.如果存在有向环的话，我们就将这个有向环整体看做一个顶点，同时改变图中边的权值。

5.现在假设u在该环上，这个环中指向u的边权是in[u]，那么对于每条从u出发的边(u,i,w),在新图中连接(new,i,w)的边。

6.对于每条进入u的边(i,u,w),在新图中建立边(i,new,w-in[u])的边。

7.对于这个算法正确性的证明，可以参考目录下的在网络中寻找最小树形图的简易算法.pdf

  1#include <stdio.h>
  2#include <string.h>
  3using namespace std;
  4 
  5const unsigned int maxn=128,NOEDGE=-1;
  6unsigned int G[maxn][maxn];
  7int N,M;
  8int res; 
  9unsigned int update(unsigned int o,unsigned int x){
 10    if(o>x)return x;
 11        return o;
 12}
 13bool vis[maxn]; 
 14void dfs(int v){
 15    vis[v]=true;
 16    for(int i=2;i<=N;++i)
 17        if((!vis[i])&&G[v][i]!=NOEDGE)
 18            dfs(i); 
 19}
 20bool possible(){
 21    memset(vis,0,sizeof(vis));
 22    dfs(1);
 23    for(int i=2;i<=N;++i)
 24        if(!vis[i])
 25            return false;
 26    return true;
 27}
 28int pre[maxn];
 29bool del[maxn];
 30void solve(){
 31    int num=N;
 32    memset(del,0,sizeof(del));
 33    for(;;){
 34        int i;
 35        for(i=2;i<=N;++i){
 36            if(del[i])continue;
 37            pre[i]=i;
 38            G[i][i]=NOEDGE;
 39            for(int j=1;j<=N;++j){
 40                if(del[j])continue;
 41                if(G[j][i]<G[pre[i]][i])
 42                    pre[i]=j;
 43            }
 44        }
 45        for(i=2;i<=N;++i){
 46            if(del[i])continue;
 47            int j=i;
 48            memset(vis,0,sizeof(vis));
 49            while(!vis[j]&&j!=1){
 50                vis[j]=true;
 51                j=pre[j];
 52            }
 53            if(j==1)continue;
 54            i=j;
 55            res+=G[pre[i]][i];
 56            for(j=pre[i];j!=i;j=pre[j]){
 57                res+=G[pre[j]][j];
 58                del[j]=true;    
 59            }
 60            for(j=1;j<=N;++j){
 61                if(del[j])continue;
 62                if(G[j][i]!=NOEDGE)
 63                    G[j][i]-=G[pre[i]][i];
 64            }
 65            for(j=pre[i];j!=i;j=pre[j]){
 66                for(int k=1;k<=N;++k){
 67                    if(del[k])continue;
 68                    G[i][k]=update(G[i][k],G[j][k]);
 69                    if(G[k][j]!=NOEDGE)
 70                        G[k][i]=update(G[k][i],G[k][j]-G[pre[j]][j]);
 71                }
 72            }
 73            for(j=pre[i];j!=i;j=pre[j]){
 74                del[j]=true;
 75            }
 76            break;
 77        }
 78        if(i>N){
 79            for(int i=2;i<=N;++i){
 80                if(del[i])continue;
 81                res+=G[pre[i]][i];
 82            }
 83            break;
 84        }
 85    }
 86}
 87int main(){
 88    for(;;){
 89        scanf("%d%d",&N,&M);
 90        if(N==0)break;
 91        memset(G,NOEDGE,sizeof(G));
 92        for(int i=0;i<M;++i){
 93            unsigned int a,b,c;
 94            scanf("%u%u%u",&a,&b,&c);
 95            G[a][b]=c;
 96        }
 97        if(!possible()){
 98            puts("impossible"); 
 99        }
100        else{
101            res=0; 
102            solve();
103            printf("%d\n",res);
104        }
105    }
106}

posted on 2008-07-15 12:36 gong 阅读(184) 评论(0)  编辑 收藏 引用