把码头作为0点处理。
首先判断不建码头是否可以生成最小生成树
最小生成树用kruskal算法，若对于代价<0的边，直接加入
若可以：Min（最小生成树（不建码头），最小生成树（建码头））；
若不可：最小生成树（建码头）
#include "stdio.h"#include "string.h"#include "algorithm"using namespace std;int father[10010];struct Link{int a,b,v;}link[110001];int Min(int a,int b){if (a<b) return a;else return b;}int fin(int x){if (x==father[x]) return x;father[x]=fin(father[x]);return father[x];}bool cmp(Link a,Link b){return a.v<b.v;}int kruskal(int m){int sum,i,fa,fb;sum=0;for (i=0;i<m;i++){fa=fin(link[i].a);fb=fin(link[i].b);if (fa!=fb || link[i].v<0){sum+=link[i].v;father[fa]=fb;}}return sum;}int main(){int n,m,i,cnt,fa,fb,ans,x;scanf("%d%d",&n,&m);for (i=0;i<=n;i++)father[i]=i;for (i=0;i<m;i++)scanf("%d%d%d",&link[i].a,&link[i].b,&link[i].v);cnt=0;for (i=1;i<=n;i++){scanf("%d",&x);if (x!=-1){link[m+cnt].a=0;link[m+cnt].b=i;link[m+cnt].v=x;cnt++;}}for (i=0;i<m;i++){fa=fin(link[i].a);fb=fin(link[i].b);father[fa]=fb;}for (i=2;i<=n;i++)if (fin(1)!=fin(i))break;if (i==n+1){for (i=0;i<=n;i++)father[i]=i;sort(link,link+m,cmp);ans=kruskal(m);for (i=0;i<=n;i++)father[i]=i;sort(link,link+m+cnt,cmp);ans=Min(ans,kruskal(m+cnt));printf("%d\n",ans);}else{for (i=0;i<=n;i++)father[i]=i;sort(link,link+m+cnt,cmp);printf("%d\n",kruskal(m+cnt));}return 0;}
，也有伤心的，既有令人兴奋的，也有令人灰心的，
