程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3164 Command Network (最小樹形圖-朱劉算法)

POJ 3164 Command Network (最小樹形圖-朱劉算法)

編輯：C++入門知識

POJ 3164 Command Network (最小樹形圖-朱劉算法)

最小樹形圖第一發。
把一個v寫成u了。。。。。TLE了一晚上。。。（雖說今晚出去玩了。。）
剛開始看這個算法的時看模板以為又是一個isap。。。。嚇得一個哆嗦。但是仔細看了看之後發現還是挺好理解的。寫下自己的理解。
朱劉算法其實只有3步，然後不斷循環。
1：找到每個點的最小入邊。既然是生成樹，那麼對於每個點來說，只要選一個權值最小的入邊就可以了。貪心思想。因為如果不是最小入邊，那麼它肯定不是最小樹形圖的一條邊，考慮它是沒有意義的。
2：找環。找環找的是最小入邊構成的新圖的環。如果沒找到環，那麼一棵樹就已經形成了，因為樹就是沒有環的圖。再因為邊權都是最小的，因此此時最小樹形圖就已經出來了，停止循環。
3：如果第2步中找到了環，那麼這個環就可以縮成一個點。然後構造新圖，更新邊權。更新邊權的方法是：假設某點u在該環上，並設這個環中指向u的邊權是in[u]，那麼對於每條從u出發的邊(u, i, w)，在新圖中連接(new, i, w)的邊，其中new為新加的人工頂點; 對於每條進入u的邊(i, u, w)，在新圖中建立邊(i, new, w-in[u])的邊。之所以是w-in[u]的原因是如果選擇了w，那麼那個in[u]在樹中就是多余的，完全可以刪除，所以需要減去，然後再後面的總費用累加中會體現出刪掉了這個權值，不理解的畫個圖就明白了。
至於實現方法還是看代碼吧。看不懂的可以留言提問。
代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
using namespace std;
#define LL __int64
#define pi acos(-1.0)
//#pragma comment(linker, "/STACK:1024000000")
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=40000+10;
int cnt, n;
int color[110], id[110], pre[110];
double in[200];
struct Point
{
        double x, y;
}fei[200];
struct node
{
        int u, v;
        double w;
}edge[11000];
void add(int u, int v, double w)
{
        edge[cnt].u=u;
        edge[cnt].v=v;
        edge[cnt++].w=w;
}
double dist(Point f1, Point f2)
{
        return sqrt((f1.x-f2.x)*(f1.x-f2.x)*1.0+(f1.y-f2.y)*(f1.y-f2.y));
}
double dmst(int root)
{
        double ans=0;
        int i, j, u, v, NV=n;
        while(1){
                for(i=1;i<=NV;i++) in[i]=INF;//找最小入邊
                for(i=0;i