そしてテーマを調べます.

54498 ワード
acm
0.そして検索集
何が同時調査集ですか?検索セットは、いくつかのアンサンブルの統合およびクエリの問題を処理するためのツリー型のデータ構造である.よくある操作
  • 初期化(init)
    • 各ポイントの集合を自身に初期化する.通常、このステップは、データ構造を使用するたびに一回だけ実行される必要があり、どのような実施形態であれ、時間複雑度はO(N)である.
    void init()
{
	for(int i=1;i<=n;i++)
		father[i]=i;
}
  • 検索(getfather)
    • 要素の集合、すなわちルートノードを検索します.
    int getfather(int x)
{
	if(father[x]==x)return x;
    else return father[x]=getfather(father[x]);
}
    ここでは経路圧縮の方法を採用して、iの所属する集をルートの結点に変えて、次に検索する時、O(1)の時間内に結果を得ることができます.
  • 合併(merge)
    • 二つの要素があるセットを一つのセットに統合します.一般的には、統合の前に、2つの要素が同じセットに属するかどうかを先に判断しなければならない.これは上の「検索」動作で実現される.
    void merge(int a,int b)
{
	int f1=getfather(a);
	int f2=getfather(b);
	if(f1!=f2)
	{
		father[f1]=f2;//   father[f2]=f1;
		    ;
	}
}
  • 権限を持ち、
    • を検索する.
    検索(getfather)に基づいて最適化する:
    int getfather(int x)
{
	if(father[x]==x)return x;
    else
    {
    	int t=father[x];//     
    	father[x]=getfather(father[x]);
    	dis[x]+=dis[t];//     x       
    	return father[x];
    }
}
    ここのdis配列は各点からその祖先までの距離を表しています.
    1.最小生成ツリー
    路線計画時間制限:1 Secメモリ制限:128 MBテーマは、n個の村の間に通信回線を設置する必要があることを記述しており、いずれかの2つの村の間で通信が可能になる.2つの村a,b間は通信可能であり、それらの間に1つの通信線が存在する場合のみ、または村cが存在する場合は、a,c,b,c間は通信可能である.村の間に通信線を架けることの代償を与え、最小の総代を求める.入力の最初の行は2つの整数n、mを含み、それぞれ村の数と通信回線を構築できる村の対数を表します.以下のm行は、各行の整数a、b、cで、村a、bの間に架設されている線路の価格をcと表します.1つの整数を出力し、最小の合計値を返します.サンプル入力Copy
    3 3
0 1 1
1 2 1
2 0 3
    サンプル出力Copy
    2
    ヒント50%のデータに対して、n<=100,m<=n^2はすべてのデータに対して、1<=n==10^5;n-1<=m<=10^5、すべての価格は[0、10^6]の範囲で、問題が解決されることを保証します.
    最小生成樹kruskyalアルゴリズム＋そして集合テンプレートの問題を調べると、WAが容易な点は、起点座標が終点座標より小さいことを保証するのではなく、father[f1]=f2かfather[f2]=f1かを選択するのではなく、村落対数を読み込む時に1からmかそれとも0からm-1かを選択するのではなく、最後の総価格はlong long long long型であるかもしれない.最初は全部の価格が[0,10^6]の範囲で、91%のデータしか通過できないと勘違いしました.
    #include
#include
using namespace std;
typedef struct village
{
    int Start,End,Weight;
}v;
int father[100005];
v vil[100005];
int getfather(int x)
{
    if(father[x]==x)return x;
    else return father[x]=getfather(father[x]);
}
int cmp(const void*a,const void*b)
{
    v*x=(v*)a;
    v*y=(v*)b;
    return x->Weight-y->Weight;
}
int main()
{
    int n,m,edge=0,a,b,c;
    long long int cost=0;
    scanf("%d %d",&n,&m);
    for(int i=0;i<=n-1;i++)father[i]=i;
    for(int i=0;i<=m-1;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        vil[i].Start=a;
        vil[i].End=b;
        vil[i].Weight=c;
    }
    int f1,f2;
    qsort(vil,m,sizeof(vil[0]),cmp);
    for(int i=0;i<=m-1;i++)
    {
        f1=getfather(vil[i].Start);
        f2=getfather(vil[i].End);
        if(f1!=f2)
        {
            father[f1]=f2;
            edge++;
            cost+=vil[i].Weight;
            if(edge==n-1)break;
        }
    }
    printf("%lld",cost);
    return 0;
}
/**************************************************************
    Language: C++
    Result:   
    Time:65 ms
    Memory:3852 kb
****************************************************************/
    2.最大生成ツリー
    sunflower時間制限:1 Secメモリ制限:128 MBテーマ:NさんはよくTさんの家の花園に散歩に行きます.Tさんの家の花園はN個の長い同じあずまやとM本の道があずまやとつながっていますが、Tさんの花園はとても乱れています.そこでNさんはTさんにその中のある道をヒマワリに植えさせて、残りの道に輪が現れないようにします.ヒマワリは不便なので、第iの道の長いLiは、Liのヒマワリが必要です.そこで、Tさんは彼が少なくともどれぐらいのひまわりを植えたら、Nさんの要求を満たすことができますか?最初の行の2つの整数Nを入力して、庭の亭の数と道の数を表します.次のM行は、各行3個の整数A、B、Cで、AとBを接続している長さCの道があることを示しています.1行1つの整数を出力して、小さいTが少なくとも種のヒマワリの数を必要とすることを表します.サンプル入力Copy
    5 5
1 2 5
1 4 4
3 4 3
2 3 2
3 5 1
    サンプル出力Copy
    2
    ヒント100%のデータに対して、1≦N≦10^5,1≦M≦2×10^5,0類比の「破輪法」の原理は、連結性を変えずに毎回権利値が最小となる辺を削除することと等価であり、削除できなくなるまで、すなわち最大樹問題が発生する.kruskyalアルゴリズムの並べ替え方法を、大きな値から小さい値への並べ替えに変更するだけです.
    #include
#include
using namespace std;
typedef struct Edge
{
    int Start,End,cost;
}edge;
int cmp(const void*a,const void*b)
{
    edge*x=(edge*)a;
    edge*y=(edge*)b;
    return y->cost-x->cost;
}
edge road[200005];
int father[100005];
int n,m,a,b,c,cnt=0;
int getfather(int v)
{
    if(father[v]==v)return v;
    else return father[v]=getfather(father[v]);
}
int main()
{
    long long int sum=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        road[i].Start=a;
        road[i].End=b;
        road[i].cost=c;
        sum+=road[i].cost;
    }
    qsort(road+1,m,sizeof(road[1]),cmp);//           
    for(int i=1;i<=n;i++)father[i]=i;
    long long int sum1=0;
    int fat1,fat2;
    for(int i=1;i<=m;i++)
    {
        fat1=getfather(road[i].Start);
        fat2=getfather(road[i].End);
        if(fat1!=fat2)
        {
            sum1+=road[i].cost;
            father[fat2]=fat1;
            cnt++;
            if(cnt==n-1)break;
        }
    }
    printf("%lld",sum-sum1);
    return 0;
}
/**************************************************************
    Language: C++
    Result:   
    Time:128 ms
    Memory:6196 kb
****************************************************************/
    3.連通図問題
    tunnel時間制限:1 Secメモリ制限:128 MBテーマは自分の地下鉄の線路網の建設に着手している町を描いています.小さな町は多くの小さな島にあり、小さな島はトンネルや橋でつながっています.地下鉄はこれらの既存の橋とトンネルをもとにして建設されました.地下鉄は主に地下にあるので、橋は少なければ少ないほどいいです.町の住民は地下鉄だけでどこの島でも往復できるようにしたいです.幸いなことに、私たちはこの要求を満たすために十分なトンネルと橋がありますので、新しいトンネルや橋を作る必要はありません.このような地下鉄の路線網を構築するには少なくともいくつかの橋が必要です.入力にはK＋M＋1行が含まれます.最初の行はN、M、Kの三つを含みます.ここでNは小島の数で、Mはトンネルの数で、Kは橋の数です.次のM行は各行に2つの数があり、それぞれのトンネル接続の小島の番号を表しています.番号は1からNまでです.次のK行の各行は同じように橋を描きます.1つの数を出力します.一番必要な橋の数です.サンプル入力Copy
    6 3 4
1 2
2 3
4 5
1 3
3 4
4 6
5 6
    サンプル出力Copy
    2
    ヒント100%のデータについては、1≦N≦10000,1≦K≦12000,1≦M≦12000は黒体の部分で知られています.最終的に得られた図は必ず接続図です.だから、トンネルを調べて、いくつかの連結枝を得て、統計的に連結分岐数(各点の祖先ノードは現在ノードです)-1は解答を得ます.
    #include
typedef struct node
{
    int Start,End;
}edge;
edge tunnel[12005];
edge bridge[12005];
int father[10005];
int k,n,m;
int getfather(int x)
{
    if(father[x]==x)return x;
    else return father[x]=getfather(father[x]);
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&tunnel[i].Start,&tunnel[i].End);
    }
    for(int i=1;i<=k;i++)
    {
        scanf("%d %d",&bridge[i].Start,&bridge[i].End);
    }
    for(int i=1;i<=n;i++)father[i]=i;
    int f1,f2;
    for(int i=1;i<=m;i++)
    {
        f1=getfather(tunnel[i].Start);
        f2=getfather(tunnel[i].End);
        if(f1!=f2)father[f2]=f1;
    }
    for(int i=1;i<=n;i++)
        if(father[i]==i)cnt++;
    printf("%d",cnt-1);
    return 0;
}
/**************************************************************
    Language: C++
    Result:   
    Time:11 ms
    Memory:1344 kb
****************************************************************/
    4.環の有無を判断する
    無線放送時間制限:2 Secメモリ制限:256 MBのある放送会社がある地域に無線放送送信装置を設置する.この地域には全部でnの小さな町があります.どの町にも送信機を設置して、それぞれの番組を放送しています.しかし、同社はFM 104.2とFM 98.6の2つの帯域に対してのみ許可を得ており、同じバンドの送信機会を使って互いに干渉している.送信機ごとの信号の被覆範囲は、中心部として知られています.半径20 kmの円形のエリアです.そのため、距離が20 km以下の二つの町で同じ帯域を使用すると、帯域干渉により番組を正常に聞くことができなくなります.これらの距離が20 km以下の町のリストを提示し、地域全体の住民がラジオ番組を正常に聞くことができるかどうかを判断してみます.第一行為の2つの整数n、mを入力して、それぞれ小鎮の個数と次の20 km以下の小鎮ペアの数です.次のm行は、1行につき2つの整数で、2つの町の距離が20 km未満(1から開始)であることを示しています.出力が要求を満たすことができれば、1を出力します.そうでなければ、-1を出力します.サンプル入力Copy
    4 3
1 2
1 3
2 4
    サンプル出力Copy
    1
    制限1≦n≦10000 1≦m≦30000は所与の20 kmの小鎮リストの空間特性を考慮する必要がなく、例えば三角不等式を満たすかどうか、伝達性を利用してより多くの情報を提供することができるかどうかなどです.
    20 km以下を連結関係と見なし、与えられたすべての点を図に形成することができ、容易に検証できる.図中にリングが存在しない場合や、偶数の長さのリングが存在しない場合は要求を満たすことができ、残りの場合は要求を満たさないので、リングとリングの長さの問題があるかどうかを調べることになる.ループの中にリングがあるかどうかを判断して採用して調べます.二つの点(起点、終点)の祖先の接合点が同じであれば、一つのループを構成することができます.dis配列を利用して、接合点から祖先までの距離を記録します.一つの辺の二つの端点に対して、法則を探すことによって、二つの端点から祖先までの距離の差が偶数であることが分かります.逆に,二つの端点から祖先までの距離の差が奇数である場合には,現在の辺を加えて,リングの長さは偶数である.
    #include
using namespace std;
int father[10005];
typedef struct Node
{
    int Start,End;
}node;
node town[30005];
int dis[10005]={0};//           
bool cir=false;//      
bool flag=false;//           
//   
int getfather(int x)//     
{
    if(father[x]==x)return x;
    else
    {
        int t=father[x];
        father[x]=getfather(father[x]);
        dis[x]+=dis[t];//          
        return father[x];
    }
}
int main()
{
    int n,m,a,b;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)father[i]=i;//   ，           
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&a,&b);
        if(a>b)
        {
            int t=a;
            a=b;
            b=t;
        }
        town[i].Start=a;
        town[i].End=b;
    }
    int f1,f2;
    for(int i=1;i<=m;i++)
    {
        f1=getfather(town[i].Start);
        f2=getfather(town[i].End);
        if(f1==f2)//    ，     
        {
            cir=true;
            if((dis[town[i].Start]-dis[town[i].End])%2==0)flag=true;//       
        }
        else//    
        {
            father[f1]=f2;//     
            dis[f1]=dis[town[i].End]+1-dis[town[i].Start];//    
        }
    }
    if(cir==false)printf("1");//     
    else if(flag==false)printf("1");//           
    else printf("-1");//           
    return 0;
}
/**************************************************************
    Language: C++
    Result:   
    Time:4 ms
    Memory:4816 kb
****************************************************************/
    データ構造——11順序両方向リンク表にノードを挿入する