01基本概念

貪心算法是指在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，只做出在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

貪心算法沒有固定的算法框架，算法設(shè)計的關(guān)鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性（即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。）

所以，對所采用的貪心策略一定要仔細分析其是否滿足無后效性。

02貪心算法的基本思路

解題的一般步驟是：

1.建立數(shù)學(xué)模型來描述問題；
2.把求解的問題分成若干個子問題；
3.對每一子問題求解，得到子問題的局部最優(yōu)解；
4.把子問題的局部最優(yōu)解合成原來問題的一個解。

03該算法存在的問題

不能保證求得的最后解是最佳的
不能用來求最大值或最小值的問題
只能求滿足某些約束條件的可行解的范圍

04貪心算法適用的問題

貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解。

實際上，貪心算法適用的情況很少。一般對一個問題分析是否適用于貪心算法，可以先選擇該問題下的幾個實際數(shù)據(jù)進行分析，就可以做出判斷。

05貪心選擇性質(zhì)

所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，換句話說，當(dāng)考慮做何種選擇的時候，我們只考慮對當(dāng)前問題最佳的選擇而不考慮子問題的結(jié)果。這是貪心算法可行的第一個基本要素。貪心算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。

當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(guān)鍵特征。

06貪心算法的實現(xiàn)框架

從問題的某一初始解出發(fā)：

while (朝給定總目標(biāo)前進一步){   利用可行的決策，求出可行解的一個解元素。}

由所有解元素組合成問題的一個可行解；

07例題分析

如果大家比較了解動態(tài)規(guī)劃，就會發(fā)現(xiàn)它們之間的相似之處。最優(yōu)解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優(yōu)解，大部分情況下這是不可行的。貪心算法和動態(tài)規(guī)劃本質(zhì)上是對子問題樹的一種修剪，兩種算法要求問題都具有的一個性質(zhì)就是子問題最優(yōu)性(組成最優(yōu)解的每一個子問題的解，對于這個子問題本身肯定也是最優(yōu)的)。動態(tài)規(guī)劃方法代表了這一類問題的一般解法，我們自底向上構(gòu)造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，并且以其中的最優(yōu)值作為自身的值，其它的值舍棄。而貪心算法是動態(tài)規(guī)劃方法的一個特例，可以證明每一個子樹的根的值不取決于下面葉子的值，而只取決于當(dāng)前問題的狀況。換句話說，不需要知道一個節(jié)點所有子樹的情況，就可以求出這個節(jié)點的值。由于貪心算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優(yōu)的路，一直走到底就可以了。

話不多說，我們來看幾個具體的例子慢慢理解它：

1.活動選擇問題

這是《算法導(dǎo)論》上的例子，也是一個非常經(jīng)典的問題。有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結(jié)束時間fi 。一旦被選擇后，活動ai就占據(jù)半開時間區(qū)間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。例如下圖所示的活動集合S，其中各項活動按照結(jié)束時間單調(diào)遞增排序。

考慮使用貪心算法的解法。為了方便，我們用不同顏色的線條代表每個活動，線條的長度就是活動所占據(jù)的時間段，藍色的線條表示我們已經(jīng)選擇的活動；紅色的線條表示我們沒有選擇的活動。

如果我們每次都選擇開始時間最早的活動，不能得到最優(yōu)解：

如果我們每次都選擇持續(xù)時間最短的活動，不能得到最優(yōu)解：

可以用數(shù)學(xué)歸納法證明，我們的貪心策略應(yīng)該是每次選取結(jié)束時間最早的活動。直觀上也很好理解，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。這也是把各項活動按照結(jié)束時間單調(diào)遞增排序的原因。

#include#include#includeusing namespace std;    int N;struct Act{  int start;  int end;}act[100010];
bool cmp(Act a,Act b)  {    return a.end}
int greedy_activity_selector()  {    int num=1,i=1;     for(int j=2;j<=N;j++)    {      if(act[j].start>=act[i].end)      {        i=j;        num++;      }    }    return num;}
int main()  {    int t;  scanf("%d",&t);  while(t--)  {    scanf("%d",&N);    for(int i=1;i<=N;i++)    {      scanf("%lld %lld",&act[i].start,&act[i].end);    }    act[0].start=-1;    act[0].end=-1;    sort(act+1,act+N+1,cmp);    int res=greedy_activity_selector();    cout<endl;    }}

2.錢幣找零問題

這個問題在我們的日常生活中就更加普遍了。假設(shè)1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張?，F(xiàn)在要用這些錢來支付K元，至少要用多少張紙幣？用貪心算法的思想，很顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們自然而然也是這么做的。在程序中已經(jīng)事先將Value按照從小到大的順序排好。

#include#includeusing namespace std;const int N=7;int Count[N]={3,0,2,1,0,3,5};int Value[N]={1,2,5,10,20,50,100};
int solve(int money){  int num=0;  for(int i=N-1;i>=0;i--)  {    int c=min(money/Value[i],Count[i]);    money=money-c*Value[i];    num+=c;  }  if(money>0) num=-1;  return num;}
int main(){  int money;  cin>>money;  int res=solve(money);  if(res!=-1) cout<endl;  else cout<<"NO"<<endl;}

3.再論背包問題

在從零開始學(xué)動態(tài)規(guī)劃中我們已經(jīng)談過三種最基本的背包問題：零一背包，部分背包，完全背包。很容易證明，背包問題不能使用貪心算法。然而我們考慮這樣一種背包問題：在選擇物品i裝入背包時，可以選擇物品的一部分，而不一定要全部裝入背包。這時便可以使用貪心算法求解了。計算每種物品的單位重量價值作為貪心選擇的依據(jù)指標(biāo)，選擇單位重量價值最高的物品，將盡可能多的該物品裝入背包，依此策略一直地進行下去，直到背包裝滿為止。在零一背包問題中貪心選擇之所以不能得到最優(yōu)解原因是貪心選擇無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。在程序中已經(jīng)事先將單位重量價值按照從大到小的順序排好。

#include   using namespace std;   const int N=4;  void knapsack(float M,float v[],float w[],float x[]);  
int main()  {    float M=50;  //背包所能容納的重量     float w[]={0,10,30,20,5};  //每種物品的重量    float v[]={0,200,400,100,10};    //每種物品的價值  float x[N+1]={0};    //記錄結(jié)果的數(shù)組  knapsack(M,v,w,x);    cout<<"選擇裝下的物品比例："<<endl;    for(int i=1;i<=N;i++) cout<<"["<"]:"<endl;  }  
void knapsack(float M,float v[],float w[],float x[])  {    int i;    //物品整件被裝下    for(i=1;i<=N;i++)  {      if(w[i]>M) break;       x[i]=1;      M-=w[i];    }     //物品部分被裝下    if(i<=N) x[i]=M/w[i];   }

4.多機調(diào)度問題

n個作業(yè)組成的作業(yè)集，可由m臺相同機器加工處理。要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。作業(yè)不能拆分成更小的子作業(yè)；每個作業(yè)均可在任何一臺機器上加工處理。這個問題是NP完全問題，還沒有有效的解法(求最優(yōu)解)，但是可以用貪心選擇策略設(shè)計出較好的近似算法(求次優(yōu)解)。當(dāng)n<=m時，只要將作業(yè)時間區(qū)間分配給作業(yè)即可；當(dāng)n>m時，首先將n個作業(yè)從大到小排序，然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機。也就是說從剩下的作業(yè)中，選擇需要處理時間最長的，然后依次選擇處理時間次長的，直到所有的作業(yè)全部處理完畢，或者機器不能再處理其他作業(yè)為止。如果我們每次是將需要處理時間最短的作業(yè)分配給空閑的機器，那么可能就會出現(xiàn)其它所有作業(yè)都處理完了只剩所需時間最長的作業(yè)在處理的情況，這樣勢必效率較低。在下面的代碼中沒有討論n和m的大小關(guān)系，把這兩種情況合二為一了。

#include  #include    using namespace std;  int speed[10010];  int mintime[110];  
bool cmp( const int &x,const int &y)  {    return x>y;  }  
int main()  {    int n,m;           memset(speed,0,sizeof(speed));    memset(mintime,0,sizeof(mintime));    cin>>n>>m;    for(int i=0;icin>>speed[i];    sort(speed,speed+n,cmp);    for(int i=0;i  {    *min_element(mintime,mintime+m)+=speed[i];     }     cout<<*max_element(mintime,mintime+m)<<endl;}

5.小船過河問題

POJ1700是一道經(jīng)典的貪心算法例題。題目大意是只有一艘船，能乘2人，船的運行速度為2人中較慢一人的速度，過去后還需一個人把船劃回來，問把n個人運到對岸，最少需要多久。先將所有人過河所需的時間按照升序排序，我們考慮把單獨過河所需要時間最多的兩個旅行者送到對岸去，有兩種方式：

1.最快的和次快的過河，然后最快的將船劃回來；次慢的和最慢的過河，然后次快的將船劃回來，所需時間為：t[0]+2*t[1]+t[n-1]；

2.最快的和最慢的過河，然后最快的將船劃回來，最快的和次慢的過河，然后最快的將船劃回來，所需時間為：2*t[0]+t[n-2]+t[n-1]。

算一下就知道，除此之外的其它情況用的時間一定更多。每次都運送耗時最長的兩人而不影響其它人，問題具有貪心子結(jié)構(gòu)的性質(zhì)。

AC代碼：

#include#includeusing namespace std;
int main(){  int a[1000],t,n,sum;  scanf("%d",&t);  while(t--)  {    scanf("%d",&n);    sum=0;    for(int i=0;iscanf("%d",&a[i]);    while(n>3)    {      sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);      n-=2;    }    if(n==3) sum+=a[0]+a[1]+a[2];    else if(n==2) sum+=a[1];    else sum+=a[0];    printf("%d
",sum);  }}

6.區(qū)間覆蓋問題

POJ1328是一道經(jīng)典的貪心算法例題。題目大意是假設(shè)海岸線是一條無限延伸的直線。陸地在海岸線的一側(cè)，而海洋在另一側(cè)。每一個小的島嶼是海洋上的一個點。雷達坐落于海岸線上，只能覆蓋d距離，所以如果小島能夠被覆蓋到的話，它們之間的距離最多為d。題目要求計算出能夠覆蓋給出的所有島嶼的最少雷達數(shù)目。對于每個小島，我們可以計算出一個雷達所在位置的區(qū)間。

問題轉(zhuǎn)化為如何用盡可能少的點覆蓋這些區(qū)間。先將所有區(qū)間按照左端點大小排序，初始時需要一個點。如果兩個區(qū)間相交而不重合，我們什么都不需要做；如果一個區(qū)間完全包含于另外一個區(qū)間，我們需要更新區(qū)間的右端點；如果兩個區(qū)間不相交，我們需要增加點并更新右端點。

AC代碼：

#include#include#includeusing namespace std;struct Point{  double x;  double y;}point[1000];
int cmp(const void *a, const void *b){  return (*(Point *)a).x>(*(Point *)b).x?1:-1;}
int main(){  int n,d;  int num=1;  while(cin>>n>>d)  {    int counting=1;    if(n==0&&d==0) break;    for(int i=0;i    {      int x,y;      cin>>x>>y;      if(y>d)      {        counting=-1;      }      double t=sqrt(d*d-y*y);      //轉(zhuǎn)化為最少區(qū)間的問題      point[i].x=x-t;      //區(qū)間左端點      point[i].y=x+t;      //區(qū)間右端點    }    if(counting!=-1)    {      qsort(point,n,sizeof(point[0]),cmp);      //按區(qū)間左端點排序      double s=point[0].y;      //區(qū)間右端點      for(int i=1;i      {        if(point[i].x>s)          //如果兩個區(qū)間沒有重合,增加雷達數(shù)目并更新右端點        {          counting++;          s=point[i].y;        }        else if(point[i].y          //如果第二個區(qū)間被完全包含于第一個區(qū)間,更新右端點        {          s=point[i].y;        }      }    }    cout<<"Case "<':'<<' '<endl;    num++;  }}

7.銷售比賽

在學(xué)校OJ上做的一道比較好的題，這里碼一下。假設(shè)有偶數(shù)天，要求每天必須買一件物品或者賣一件物品，只能選擇一種操作并且不能不選，開始手上沒有這種物品?，F(xiàn)在給你每天的物品價格表，要求計算最大收益。首先要明白，第一天必須買，最后一天必須賣，并且最后手上沒有物品。那么除了第一天和最后一天之外我們每次取兩天，小的買大的賣，并且把賣的價格放進一個最小堆。如果買的價格比堆頂還大，就交換。這樣我們保證了賣的價格總是大于買的價格，一定能取得最大收益。

#include#include#include#include#include#include#includeusing namespace std;long long int price[100010],t,n,res;
int main(){  ios::sync_with_stdio(false);  cin>>t;  while(t--)  {    cin>>n;    priority_queue<long long int, vector<long long int>, greater<long long int> > q;    res=0;    for(int i=1;i<=n;i++)    {      cin>>price[i];    }    res-=price[1];    res+=price[n];    for(int i=2;i<=n-1;i=i+2)    {      long long int buy=min(price[i],price[i+1]);      long long int sell=max(price[i],price[i+1]);      if(!q.empty())      {        if(buy>q.top())        {          res=res-2*q.top()+buy+sell;          q.pop();          q.push(buy);          q.push(sell);        }        else        {          res=res-buy+sell;          q.push(sell);        }      }      else      {        res=res-buy+sell;        q.push(sell);      }    }         cout<endl;  }}

下面我們結(jié)合數(shù)據(jù)結(jié)構(gòu)中的知識講解幾個例子。

8.Huffman編碼

這同樣是《算法導(dǎo)論》上的例子。Huffman編碼是廣泛用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。我們可以有多種方式表示文件中的信息，如果用01串表示字符，采用定長編碼表示，則需要3位表示一個字符，整個文件編碼需要300000位；采用變長編碼表示，給頻率高的字符較短的編碼，頻率低的字符較長的編碼，達到整體編碼減少的目的，則整個文件編碼需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000位，由此可見，變長碼比定長碼方案好，總碼長減小約25%。

對每一個字符規(guī)定一個01串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴，這種編碼稱為前綴碼?？赡軣o前綴碼是一個更好的名字，但是前綴碼是一致認可的標(biāo)準(zhǔn)術(shù)語。編碼的前綴性質(zhì)可以使譯碼非常簡單：例如001011101可以唯一的分解為0,0,101,1101，因而其譯碼為aabe。譯碼過程需要方便的取出編碼的前綴，為此可以用二叉樹作為前綴碼的數(shù)據(jù)結(jié)構(gòu)：樹葉表示給定字符；從樹根到樹葉的路徑當(dāng)作該字符的前綴碼；代碼中每一位的0或1分別作為指示某節(jié)點到左兒子或右兒子的路標(biāo)。

從上圖可以看出，最優(yōu)前綴編碼碼的二叉樹總是一棵完全二叉樹，而定長編碼的二叉樹不是一棵完全二叉樹。給定編碼字符集C及頻率分布f，C的一個前綴碼編碼方案對應(yīng)于一棵二叉樹T。字符c在樹T中的深度記為dT(c)，dT(c)也是字符c的前綴碼長。則平均碼長定義為：

使平均碼長達到最小的前綴碼編碼方案稱為C的最優(yōu)前綴碼。

Huffman編碼的構(gòu)造方法：先合并最小頻率的2個字符對應(yīng)的子樹，計算合并后的子樹的頻率；重新排序各個子樹；對上述排序后的子樹序列進行合并；重復(fù)上述過程，將全部結(jié)點合并成1棵完整的二叉樹；對二叉樹中的邊賦予0、1，得到各字符的變長編碼。

POJ3253一道就是利用這一思想的典型例題。題目大意是有把一塊無限長的木板鋸成幾塊給定長度的小木板，每次鋸都需要一定費用，費用就是當(dāng)前鋸的木板的長度。給定各個要求的小木板的長度以及小木板的個數(shù)，求最小的費用。以要求3塊長度分別為5,8,5的木板為例：先從無限長的木板上鋸下長度為21的木板，花費21；再從長度為21的木板上鋸下長度為5的木板，花費5；再從長度為16的木板上鋸下長度為8的木板，花費8；總花費=21+5+8=34。利用Huffman思想，要使總費用最小，那么每次只選取最小長度的兩塊木板相加，再把這些和累加到總費用中即可。為了提高效率，使用優(yōu)先隊列優(yōu)化，并且還要注意使用long long int保存結(jié)果。

AC代碼：

#include#include#includeusing namespace std;
int main(){  long long int sum;  int i,n,t,a,b;  while(~scanf("%d",&n))  {    priority_queue<int,vector<int>,greater<int> >q;    for(i=0;i    {      scanf("%d",&t);      q.push(t);    }    sum=0;    if(q.size()==1)    {      a=q.top();      sum+=a;      q.pop();    }    while(q.size()>1)    {      a=q.top();      q.pop();      b=q.top();      q.pop();      t=a+b;      sum+=t;      q.push(t);    }    printf("%lld
",sum);  }}

9.Dijkstra算法

Dijkstra算法是由E.W.Dijkstra于1959年提出，是目前公認的最好的求解最短路徑的方法，使用的條件是圖中不能存在負邊。算法解決的是單個源點到其他頂點的最短路徑問題，其主要特點是每次迭代時選擇的下一個頂點是標(biāo)記點之外距離源點最近的頂點，簡單的說就是bfs+貪心算法的思想。

#include#include#define INF 1000#define MAX_V 100using namespace std;  
int main(){  int V,E;  int i,j,m,n;  int cost[MAX_V][MAX_V];  int d[MAX_V];  bool used[MAX_V];  cin>>V>>E;  fill(d,d+V+1,INF);  fill(used,used+V,false);  for(i=0;i  {    for(j=0;j    {      if(i==j) cost[i][j]=0;      else cost[i][j]=INF;    }  }  for(m=0;m  {    cin>>i>>j>>cost[i][j];    cost[j][i]=cost[i][j];  }  cin>>n;  d[n]=0;  //源點  while(true)  {    int v=V;    for(m=0;m    {          if((!used[m])&&(d[m]    }        if(v==V) break;    used[v]=true;    for(m=0;m    {      d[m]=min(d[m],d[v]+cost[v][m]);    }  }  for(i=0;i  {    cout<<"the shortest distance between "<" and "<" is "<endl;  }}

10.最小生成樹算法

設(shè)一個網(wǎng)絡(luò)表示為無向連通帶權(quán)圖G =(V, E) , E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹的代價是指生成樹上各邊權(quán)的總和，在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。例如在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費用，最小生成樹給出建立通信網(wǎng)絡(luò)的最經(jīng)濟方案。

構(gòu)造最小生成樹的Kruskal算法和Prim算法都利用了MST(最小生成樹)性質(zhì)：設(shè)頂點集U是V的真子集(可以任意選取)，如果(u,v)∈E為橫跨點集U和V—U的邊，即u∈U，v∈V- U，并且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，則一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。

使用反證法可以很簡單的證明此性質(zhì)。假設(shè)對G的任意一個最小生成樹T，針對點集U和V—U，(u,v)∈E為橫跨這2個點集的最小權(quán)邊，T不包含該最小權(quán)邊，但T包括節(jié)點u和v。將添加到樹T中，樹T將變?yōu)楹芈返淖訄D，并且該回路上有一條不同于的邊,u’∈U,v’∈V-U。將刪去，得到另一個樹T’，即樹T’是通過將T中的邊替換為得到的。由于這2條邊的耗費滿足c[u][v]≤c[u’][v’]，故即T’耗費≤T的耗費，這與T是任意最小生成樹的假設(shè)相矛盾，從而得證。

Prim算法每一步都選擇連接U和V-U的權(quán)值最小的邊加入生成樹。

#include#include#define MAX_V 100#define INF 1000using namespace std;  
int main(){  int V,E;  int i,j,m,n;  int cost[MAX_V][MAX_V];  int mincost[MAX_V];  bool used[MAX_V];  cin>>V>>E;  fill(mincost,mincost+V+1,INF);  fill(used,used+V,false);  for(i=0;i  {    for(j=0;j    {      if(i==j) cost[i][j]=0;      else cost[i][j]=INF;    }  }  for(m=0;m  {    cin>>i>>j>>cost[i][j];    cost[j][i]=cost[i][j];  }  mincost[0]=0;  int res=0;  while(true)  {    int v=V;    for(m=0;m    {          if((!used[m])&&(mincost[m]        v=m;    }        if(v==V) break;    used[v]=true;    res+=mincost[v];    for(m=0;m    {      mincost[m]=min(mincost[m],cost[v][m]);    }  }  cout<endl;}

Kruskal算法每一步直接將權(quán)值最小的不成環(huán)的邊加入生成樹，我們借助并查集這一數(shù)據(jù)結(jié)構(gòu)可以完美實現(xiàn)它。

#include#include#define MAX_E 100using namespace std;  struct edge{  int u,v,cost;    };int pre[MAX_E];edge es[MAX_E];int find(int x);void initvalue(int x);bool same(int x,int y);void unite(int x,int y);bool comp(const edge& e1,const edge& e2);
int main(){  int V,E;  int i,j,m,n;  cin>>V>>E;  initvalue(V);  for(i=0;icin>>es[i].u>>es[i].v>>es[i].cost;          sort(es,es+E,comp);  int res=0;  for(i=0;i  {    edge e=es[i];    if(!same(e.u,e.v))    {      unite(e.u,e.v);      res+=e.cost;    }  }  cout<endl;    }
bool comp(const edge& e1,const edge& e2){  return e1.cost}
void initvalue(int x){  for(int i=0;i}
int find(int x){  int r=x;  while(pre[r]!=r) r=pre[r];  int i=x,j;  while(pre[i]!=r)  {    j=pre[i];    pre[i]=r;    i=j;  }  return r;}
bool same(int x,int y){  if(find(x)==find(y)) return true;  else return false;    }
void unite(int x,int y){  int fx=find(x);  int fy=find(y);  if(fx!=fy) pre[fx]=fy;    }

關(guān)于貪心算法的基礎(chǔ)知識就簡要介紹到這里，希望能作為大家繼續(xù)深入學(xué)習(xí)的基礎(chǔ)。

審核編輯：湯梓紅

阅读全文

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請聯(lián)系本站處理。舉報投訴