C - 小Y上学记——认识新同学
Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
Problem Description
小Y来到了一个新的班级，新的集体，第一件事肯定是要去认识新同学。
然而想认识全班同学，所需要的代价是很大的，所以小Y想让代价尽可能小。
认识新同学有两种办法，一种是直接去认识，另一种是通过已经认识的同学去认识新同学。
小Y想知道最小代价是多少呢？
Input
多组数据，每组数据首先是一个N，表示新的班级的同学数（包括小Y，2<=N<=1000）
接下来是N-1个整数，表示小Y直接认识第i名同学所需要的代价。
接下来是一个N-1阶矩阵，其中第i行第j列表示通过第i名同学认识第j名同学的代价。
其中保证对角线为0，且保证对称.
所有代价均为不超过1000的正整数。
Output
对于每组数据，输出一个整数，表示最少代价。
Sample Input
3
2 4
0 1
1 0
4
2 4 3
0 1 2
1 0 1
2 1 0
Sample Output
3
4
可以转化成最小生成树来求解即可：
代码：2015.7.30（自己写的还是比不上网上大神的模板，唉。。。）
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
#define MAX 11010
int ID[MAX];
int Sum;
struct Node
{
int a,b,v;
friend bool operator <(Node a,Node b)
{
return a.v>b.v;
}
};
void Cread(int N)
{
for(int i=;i<=N;i++){ID[i]=i;}
}
int Find(int x)
{
int TMD=x,TMP;
while(TMD!=ID[TMD])TMD=ID[TMD];
while(x!=TMD){TMP=ID[x];ID[x]=TMD;x=TMP;}
return x;
}
int main()
{
int N,i,j,a,b,A,B,Q,SIGN;
Node NUM;
while(scanf("%d",&N)!=EOF)
{
priority_queue<Node>ID_N;
Cread(N);Sum=;SIGN=;
for(i=;i<=N;i++)
{
NUM.a=;NUM.b=i;
scanf("%d",&NUM.v);
ID_N.push(NUM);
}
for(i=;i<=N;i++)
{
for(j=;j<=N;j++)
{
NUM.a=i;NUM.b=j;
scanf("%d",&NUM.v);
if(i==j)NUM.v=MAX;
else ID_N.push(NUM);
}
}
while(!ID_N.empty())
{
if(N==SIGN+)break;
NUM=ID_N.top();ID_N.pop();
A=Find(NUM.a);B=Find(NUM.b);
if(A!=B)
{
ID[A]=B;
Sum+=NUM.v;
SIGN++;
}
}
printf("%d\n",Sum);
}
return ;
}