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 閱讀(192) 評論(0)  編輯 收藏 引用