曆屆試題 城市建設 （兩次Kruskal）

問題描述

　　棟棟居住在一個繁華的C市中，然而，這個城市的道路大都年久失修。市長準備重新修一些路以友善市民，于是找到了棟棟，希望棟棟能幫助他。

　　C市中有n個比較重要的地點，市長希望這些地點重點被考慮。現在可以修一些道路來連接配接其中的一些地點，每條道路可以連接配接其中的兩個地點。另外由于C市有一條河從中穿過，也可以在其中的一些地點建設碼頭，所有建了碼頭的地點可以通過河道連接配接。

　　棟棟拿到了允許建設的道路的資訊，包括每條可以建設的道路的花費，以及哪些地點可以建設碼頭和建設碼頭的花費。

　　市長希望棟棟給出一個方案，使得任意兩個地點能隻通過新修的路或者河道互達，同時花費盡量小。

輸入格式

　　輸入的第一行包含兩個整數n, m，分别表示C市中重要地點的個數和可以建設的道路條數。所有地點從1到n依次編号。

　　接下來m行，每行三個整數a, b, c，表示可以建設一條從地點a到地點b的道路，花費為c。若c為正，表示建設是花錢的，如果c為負，則表示建設了道路後還可以賺錢（比如建設收費道路）。

　　接下來一行，包含n個整數w_1, w_2, …, w_n。如果w_i為正數，則表示在地點i建設碼頭的花費，如果w_i為-1，則表示地點i無法建設碼頭。

　　輸入保證至少存在一個方法使得任意兩個地點能隻通過新修的路或者河道互達。

輸出格式

　　輸出一行，包含一個整數，表示使得所有地點通過新修道路或者碼頭連接配接的最小花費。如果滿足條件的情況下還能賺錢，那麼你應該輸出一個負數。

樣例輸入

5 5

1 2 4

1 3 -1

2 3 3

2 4 5

4 5 10

-1 10 10 1 1

樣例輸出

9

樣例說明

　　建設第2、3、4條道路，在地點4、5建設碼頭，總的花費為9。

資料規模和約定

　　對于20%的資料，1<=n<=10，1<=m<=20，0<=c<=20，w_i<=20；

　　對于50%的資料，1<=n<=100，1<=m<=1000，-50<=c<=50，w_i<=50；

　　對于70%的資料，1<=n<=1000；

　　對于100%的資料，1 <= n <= 10000，1 <= m <= 100000，-1000<=c<=1000，-1<=w_i<=1000，w_i≠0。

題解：最小生成樹啊。

用把所有碼頭都連到0點。

然後跑兩次Kruskal。

第一次跑有碼頭的圖，統計此時最小生成樹的邊權ans1。

第二次跑無碼頭的圖，統計此時最小生成樹的邊權ans2。

跑完第二次後，如果剛好還有一個點沒有改變fa[i]=i，即還有一個點沒有沒有加入集合中。(想想kruskal判有環的時候)，此時就去min(ans1,ans2)。否則就去有碼頭時就是最小花費。

注意：小于0的邊權一定要加上，因為隻賺不虧啊！

代碼：

#include<bits/stdc++.h>
using namespace std;
int read()  
{  
    int v = 0, f = 1;  
    char c =getchar();  
    while( c < 48 || 57 < c ){  
        if(c=='-') f = -1;  
        c = getchar();  
    }  
    while(48 <= c && c <= 57)   
        v = v*10+c-48, c = getchar();  
    return v*f;  
}  
int n,m;

struct edge
{
    int u,v,val;
}e[123456];

int fa[100100];
int ans1,ans2;
int cmp(edge a, edge b)  
{  
    return a.val<b.val;  
}  
int find(int x)
{
    return fa[x]==x? x:fa[x]=find(fa[x]);
}

void kruskal_first() //有碼頭
{
    //int cnt=n;
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(e,e+n+m,cmp);
    ans1=0;
    ans2=0;
    for(int i=0;i<n+m;i++)
    {
        if(e[i].val == - 0x3f3f3f3f)continue;
        int t1=find(e[i].u);
        int t2=find(e[i].v);
        
        if(t1!=t2|| e[i].val < 0) //少于0的一定要連上，因為是賺錢了！
        {
            
            ans1 += e[i].val;
            fa[t1]=t2; 
            //cnt--;
            //if(cnt==1)break;
        }
    }    
}
void kruskal_second() //無碼頭
{
    //int cnt=n;
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(e,e+n+m,cmp);
    for(int i=0;i<n+m;i++)
    {
        if(e[i].u == 0) continue;
        int t1=find(e[i].u);
        int t2=find(e[i].v);
        if(t1!=t2 || e[i].val < 0) //少于0的一定要連上，因為是賺錢了！
        {
            ans2 += e[i].val;
            fa[t1]=t2;
            //cnt--;
            //if(cnt==1)break;
        }
        
    }
}

int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.txt","r",stdin);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>e[i].u>>e[i].v>>e[i].val;
        
    }
    for(int i=m;i<n+m;i++)//把所有碼頭都連到一個0點
    {
        e[i].u = 0;
        e[i].v = i - m + 1;
        cin>>e[i].val;    
        if(e[i].val == -1) e[i].val = -0x3f3f3f3f;
    }

    kruskal_first();
    kruskal_second();
    //cout<<min(ans1,ans2)<<endl;
     
    int sum=0;
    for(int i=1;i<=n;i++){ //跑完無碼頭後 
        if(fa[i]==i)sum++;
    }
    //cout<<ans1<<" "<<ans2<<endl;
    if(sum==1)cout<<min(ans1,ans2)<<endl;
    else cout<<ans1<<endl;
    
    return 0;
}