城市建設(shè)傳送門(mén)

題目描述

棟棟居住在一個(gè)繁華的C市中，然而，這個(gè)城市的道路大都年久失修。市長(zhǎng)準(zhǔn)備重新修一些路以方便市民，于是找到了棟棟，希望棟棟能幫助他。
C市中有n個(gè)比較重要的地點(diǎn)，市長(zhǎng)希望這些地點(diǎn)重點(diǎn)被考慮?，F(xiàn)在可以修一些道路來(lái)連接其中的一些地點(diǎn)，每條道路可以連接其中的兩個(gè)地點(diǎn)。另外由于C市有一條河從中穿過(guò)，也可以在其中的一些地點(diǎn)建設(shè)碼頭，所有建了碼頭的地點(diǎn)可以通過(guò)河道連接。
棟棟拿到了允許建設(shè)的道路的信息，包括每條可以建設(shè)的道路的花費(fèi)，以及哪些地點(diǎn)可以建設(shè)碼頭和建設(shè)碼頭的花費(fèi)。
市長(zhǎng)希望棟棟給出一個(gè)方案，使得任意兩個(gè)地點(diǎn)能只通過(guò)新修的路或者河道互達(dá)，同時(shí)花費(fèi)盡量小。

輸入

輸入的第一行包含兩個(gè)整數(shù)n, m，分別表示C市中重要地點(diǎn)的個(gè)數(shù)和可以建設(shè)的道路條數(shù)。所有地點(diǎn)從1到n依次編號(hào)。
接下來(lái)m行，每行三個(gè)整數(shù)a, b, c，表示可以建設(shè)一條從地點(diǎn)a到地點(diǎn)b的道路，花費(fèi)為c。若c為正，表示建設(shè)是花錢(qián)的，如果c為負(fù)，則表示建設(shè)了道路后還可以賺錢(qián)（比如建設(shè)收費(fèi)道路）。
接下來(lái)一行，包含n個(gè)整數(shù)w_1, w_2, …, w_n。如果w_i為正數(shù)，則表示在地點(diǎn)i建設(shè)碼頭的花費(fèi)，如果w_i為-1，則表示地點(diǎn)i無(wú)法建設(shè)碼頭。
輸入保證至少存在一個(gè)方法使得任意兩個(gè)地點(diǎn)能只通過(guò)新修的路或者河道互達(dá)。

輸出

輸出一行，包含一個(gè)整數(shù)，表示使得所有地點(diǎn)通過(guò)新修道路或者碼頭連接的最小花費(fèi)。如果滿足條件的情況下還能賺錢(qián)，那么你應(yīng)該輸出一個(gè)負(fù)數(shù)。

樣例輸入

5  5 
1  2  4 
1  3  -1 
2  3  3 
2  4  5 
4  5  10 
-1  10  10  1  1 

樣例輸出

9 

思路

最小生成樹(shù)變種題，除去碼頭建設(shè)就是完全的Kruskra法求最小生成樹(shù)了。
我們可以引入一個(gè)河流點(diǎn)為0點(diǎn)來(lái)將建設(shè)碼頭也當(dāng)做邊加入邊集中求最小生成樹(shù)。
碼頭建設(shè)要考慮兩個(gè)問(wèn)題:
1.建設(shè)碼頭能不能實(shí)現(xiàn)全連通，因?yàn)?，題目沒(méi)有說(shuō)僅靠道路建設(shè)就能實(shí)現(xiàn)全連通，所以需要判斷一下。
2.建設(shè)碼頭和不建設(shè)碼頭到底誰(shuí)更賺，因?yàn)榻ㄔO(shè)碼頭引入了0點(diǎn)所以最小生成樹(shù)代價(jià)是包括0點(diǎn)的(也就是有可能會(huì)出現(xiàn)沒(méi)有用到碼頭連通城市但建了一座碼頭的情況)
考慮完即可。(還有一個(gè)注意點(diǎn)就是，道路的所有的負(fù)邊都要加入，因?yàn)槭氰F賺的)
if(不建碼頭連通數(shù)!=n) cout<<Kruskra(建設(shè)碼頭);
else min(Kruskra(不建設(shè)碼頭),Kruskra(建設(shè)碼頭));

代碼:(耗時(shí):281ms)

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct Node{
    int from;
    int to;
    int cost;
}a[200010];

int f[10010],r[10010],cnt = 0;

bool cmp(const Node&s1,const Node&s2){
    return s1.cost<s2.cost;
}

int find_father(int x){return x==f[x]?x:f[x] = find_father(f[x]);}

long long Kfunc(int m,int n){
    long long cost = 0;
    for(int i = 0;i<=n;i++){f[i] = i;}
    sort(a,a+m,cmp);
    for(int i = 0;i<m;i++){
        int fx = find_father(a[i].from);
        int fy = find_father(a[i].to);
        if(fx!=fy || a[i].cost<0){//負(fù)邊鐵賺，所以要加入
            cost+=a[i].cost;
            if(fx!=fy){
                f[fx] = fy;
                cnt++;
            }
        }
    }
    return cost;
}

int main(){
    int n,m,flag = 0;
    long long cost1 = 0,cost2 = 0;
    scanf("%d%d",&n,&m);
    for(int i = 0;i<m;i++)
        scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].cost);
    for(int i = 1;i<=n;i++)
        scanf("%d",&r[i]);
    cost1 = Kfunc(m,n);
    if(cnt==n-1) flag = 1;
    for(int i = 1;i<=n;i++){
        if(r[i]!=-1){
            a[m].from = 0;
            a[m].to = i;
            a[m].cost = r[i];
            m++;
        }
    }
    cost2 = Kfunc(m,n);
    if(flag)  cout<<min(cost1,cost2);
    else        cout<<cost2;
    return 0;
}