Toj 2248 Channel Design 解題報告

【題意分析】

給一個有向圖求最小生成樹。由于是有向圖所以prim和kruskal是不能解決的。這里涉及到一個求有向圖最小生成樹的算法叫做最小樹形圖。

【算法分析】

1.把這個圖消去自環(huán)

2.給除了根以外的每個點找到一個最小的入邊

3.如果這個最小入邊集中不含有向環(huán)的話我們就可以證明這個集合就是該圖的最小生成樹了。

4.如果存在有向環(huán)的話，我們就將這個有向環(huán)整體看做一個頂點，同時改變圖中邊的權(quán)值。

5.現(xiàn)在假設(shè)u在該環(huán)上，這個環(huán)中指向u的邊權(quán)是in[u]，那么對于每條從u出發(fā)的邊(u,i,w),在新圖中連接(new,i,w)的邊。

6.對于每條進入u的邊(i,u,w),在新圖中建立邊(i,new,w-in[u])的邊。

7.對于這個算法正確性的證明，可以參考目錄下的在網(wǎng)絡(luò)中尋找最小樹形圖的簡易算法.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 閱讀(187) 評論(0)  編輯 收藏 引用