ZOJ1586

1.C++和G++对数据类型的printf输出有格式限制。long long型的数据应该用%lld输出

2.在kruskal算法中，根节点只是用来判断两个当前结点有没有在同一个连通分量中，一般考虑权值的问题应该从当前结点考虑。

3.这道题的权值不仅仅在于边，还有结点的权值，这种在考虑时侧重于结点的问题使用kruskal算法更加方便。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f;
const int maxn=1005;
const int maxm=1001*1001;
struct qs
{int to;int from;int weight;
} pp[maxm];
int pre[maxn];
int cost[maxn];
int n,t,qq;
long long ans;
bool cmp(qs a,qs b)
{return (a.weight+cost[a.to]+cost[a.from])<(b.weight+cost[b.to]+cost[b.from]);
}
void init()
{ans=0;qq=0;for(int i=0; i<=n; i++)pre[i]=i;
}
int finds(int x)
{if(x==pre[x])return pre[x];pre[x]=finds(pre[x]);return pre[x];
}
void kruskal()
{sort(pp,pp+qq,cmp);int to,from;for(int i=0; i<qq; i++){to=finds(pp[i].to);from=finds(pp[i].from);if(to==from);else if(to!=from){pre[to]=from;ans+=pp[i].weight;ans+=cost[pp[i].to];//注意这个地方不是根节点的价值，是当前结点的价值ans+=cost[pp[i].from];}}
}
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);init();for(int i=1; i<=n; i++)scanf("%d",&cost[i]);for(int i=1; i<=n; i++)for(int j=1; j<=n; j++){pp[qq].from=i;pp[qq].to=j;scanf("%d",&pp[qq].weight);++qq;}kruskal();printf("%lld\n",ans);}return 0;
}