原题链接：
日常数组开小（1/1）。
一个裸的最小生成树。跑一遍最小生成树记录一下所花价钱，然后扫一下father数组把没优惠的补上，输出就好了。
参考代码：
1 #include2 #include 3 #include 4 #include 5 #define maxn 500000 6 using namespace std; 7 struct Edge{ 8 int from,to,dis; 9 bool operator<(const Edge &rhs)const{10 return dis < rhs.dis;11 }12 };13 inline int read(){14 int num = 0;15 char c;16 bool flag = false;17 while ((c = getchar()) == ' ' || c == '\n' || c == '\r');18 if (c == '-')19 flag = true;20 else21 num = c - '0';22 while (isdigit(c = getchar()))23 num = num * 10 + c - '0';24 return (flag ? -1 : 1) * num;25 }26 Edge edge[maxn];27 int father[maxn];28 int n,m;29 int tot = 0;30 int ans,totedge,readnum;31 int find(int x){32 if (father[x] == x)33 return father[x];34 else35 return find(father[x]);36 }37 void merge(int x,int y){38 father[find(y)] = find(x);39 }40 bool check(int x,int y){41 return find(x) == find(y);42 }43 int main(){44 n = read();m = read();45 for (register int i=1;i<=m;i++)46 father[i] = i;47 for (register int i=1;i<=m;i++)48 for (register int j=1;j<=m;j++){49 readnum = read();50 if (readnum!=0){51 edge[++tot].from = i;52 edge[tot].to = j;53 edge[tot].dis = readnum;54 }55 }56 sort(edge+1,edge+tot+1);57 for (register int i=1;i<=tot;i++){58 int u = edge[i].from;59 int v = edge[i].to;60 if (!check(u,v)){61 totedge++;62 ans += edge[i].dis;63 merge(u,v);64 if (totedge == m-1)65 break;66 }67 }68 for (register int i=1;i<=n;i++)69 if (father[i] == i)70 ans += n;71 printf("%d\n",ans);72 return 0;73 }