ほせいろけいかく

9881 ワード
道路工事案
時間制限:
3000 ms|メモリ制限:65535 KB
難易度:
5
 
説明
南将軍は多くの部隊を率いて、それらはそれぞれNの異なる都市に駐屯して、これらの都市はそれぞれ1~N番号をつけて、交通があまり便利ではないため、南将軍は道路を修理するつもりです.
今ではどの都市の間で道路を修理できるか、もし道路を修理すれば、費用はいくらですか.
今、軍師の小工はすでに道路を修理する案を見つけて、各都市をつなぐことができて、しかも費用が最も少ないです.
しかし、南将軍は、この道路工事案が綴られた図案は縁起が悪いと言っています.
 
入力
1行目に入力される整数T(1しゅつりょく
テストデータのセットごとにYesまたはNoを出力します(最小コストスキームが2つ以上ある場合はYesを出力し、最小コストスキームが1つしかない場合はNoを出力します)
サンプル入力
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

サンプル出力
No
Yes
  ：             ；              ，        ，     ，              ；               ；    yes
     ：

問題を解く構想:費用が最も少なく、任意の2つの都市が同じであれば、最小生成ツリーが要求されることを説明する.問題の中で別の案があるかどうかを聞いて、
最小生成ツリーの効果ですので、サブ生成ツリーを使用できます
最小生成ツリーを求めた上でエッジを追加するのが一般的です
具体的な実装:primアルゴリズムを用いて最小生成ツリーを求め,任意の点から他の各点への経路上の最大エッジ重みを統計する.その後、改生成ツリーにないエッジ(u,v)を追加し、エッジを追加するとリングが形成され、
次に、このループの重み値が2つ大きいエッジ(すなわち(u,v)を除く最大重み値のエッジ)を削除し、このときの費用を再統計し、最小生成ツリーの費用と同じであれば、別のスキームがあることを示す.
次のようになります.
mp!=-1は最小生成ツリーにないエッジを表し、mx[i][j]はiからjの最大エッジを表し、主判断sum-mx[i][j]+mp[i][j]=sum
コード:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int INF=0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
#define PI(x) printf("%d",x)
typedef long long LL;
const int MAXN=520;
int mp[MAXN][MAXN];
int mx[MAXN][MAXN];
int vis[MAXN];
int N,sum;
vector<int>vec;
void prim(int sx){
    mem(vis,0);
    vis[sx]=1;
    vec.push_back(sx);
    int u,v;
    while(vec.size()<N){
        int temp=INF;
        for(int i=0;i<vec.size();i++){
            int x=vec[i];
        //    printf("%d
",x);
            for(int j=1;j<=N;j++){
                
                if(!vis[j]&&mp[x][j]!=-1){
                    if(temp>mp[x][j]){
                        temp=mp[x][j];
                        u=x;
                        v=j;
                    //    printf("u=%d v=%d
",u,v);
                    }
                }
            }
        }
        for(int i=0;i<vec.size();i++){
            int x=vec[i];
        //    printf("u=%d v=%d
",u,v);
            if(mx[x][u]<mp[u][v])mx[x][v]=mx[v][x]=mp[u][v];
            else mx[x][v]=mx[v][x]=mx[x][u];
            
        }
        vec.push_back(v);
        vis[v]=1;
        sum+=mp[u][v];
        mp[u][v]=mp[v][u]=-1;
        //printf("%d %d %d
",u,v,vec.size());
    }
}
int main(){
    int E,T;
    SI(T);
    int a,b,c;
    while(T--){
        mem(mp,-1);mem(mx,-1);
        SI(N);SI(E);
        while(E--){
            scanf("%d%d%d",&a,&b,&c);
                mp[a][b]=mp[b][a]=c;
                mx[a][b]=mx[b][a]=c;
        }
        sum=0;
        vec.clear();
        prim(1);
        bool ans=false;
        for(int i=1;i<=N;i++){
            if(ans)break;
            for(int j=1;j<=N;j++){
                if(mp[i][j]!=-1){
                    if(sum-mx[i][j]+mp[i][j]==sum){
                        ans=true;break;
                    }
                //    else printf("mx[%d][%d]=%d
",i,j,mx[i][j]);
                }
            }
        }
        if(ans)puts("Yes");
        else puts("No");
    }
    return 0;
}

8、androidコード最適化技術記録
python 3 loggingログカット