修路
时限： 2000MS | 内存限制： 65536K | |
|---|---|---|
提交总数： 31810 | 接受： 14215 |
描述
有N个村庄，编号从1到N，您应该修建一些道路，使每两个村庄可以相互连接。我们说两个村庄A和B是连通的，当且仅当A和B之间有一条道路，或者存在一个村庄C使得A和C之间有一条道路，并且C和B连通时。 我们知道，一些村庄之间已经存在一些道路，您的工作是建造一些道路，以使所有村庄都连接起来，并且所有道路的长度都应最小。
输入
第一行是整数N（3 <= N <= 100），它是村庄的数量。然后是N行，其中第i个包含N个整数，而这N个整数中的第j个是村庄i与村庄j之间的距离（该距离应为[1，1000]之内的整数）。 然后有一个整数Q（0 <= Q <= N *（N 1）/ 2）。然后出现Q条线，每条线包含两个整数a和b（1 <= a <b <= N），这意味着已经建立了村庄a和村庄b之间的道路。
产量
您应该输出包含整数的线，该整数是要连接所有村庄的所有道路的长度，并且该值是最小值。
样本输入
代码语言：javascript复制3
0 990 692
990 0 179
692 179 0
1
1 2样本输出
代码语言：javascript复制179资源
北京大学月刊，KICC
就是给了N个村庄，然后给你权值什么的 ，后面又给了一个数M，告诉你哪些路已经修好了，你就不用修了，最后问最小生成树，问需要修的最短的路。
思路：把已经修建好的路的权值设置为0，这样求和就不用重复计算，而且能保证这些之前的路优先选择！
代码语言：javascript复制#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include<cstdio>
#include<cstring>
//---------------------------------Sexy operation--------------------------//
#define cini(n) scanf("%d",&n)
#define cinl(n) scanf("%lld",&n)
#define cinc(n) scanf("%c",&n)
#define cins(s) scanf("%s",s)
#define coui(n) printf("%d",n)
#define couc(n) printf("%c",n)
#define coul(n) printf("%lld",n)
#define debug(n) printf("%d_________________________________n",n);
#define speed ios_base::sync_with_stdio(0)
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
//-------------------------------Actual option------------------------------//
#define rep(i,a,n) for(int i=a;i<=n;i )
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Swap(a,b) a^=b^=a^=b
#define Max(a,b) (a>b?a:b)
#define Min(a,b) a<b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
#define mp(a,b) make_pair(a,b)
#define pb(n) push_back(n)
#define dis(a,b,c,d) ((double)sqrt((a-c)*(a-c) (b-d)*(b-d)))
//--------------------------------constant----------------------------------//
#define INF 0x3f3f3f3f
#define esp 1e-9
#define PI acos(-1)
using namespace std;
#define maxn 1020
#define INF 0x3f3f3f3f
using namespace std;
int dis[maxn][maxn];
int d[maxn];
bool vis[maxn];
int n,q;
void prim()
{
for(int i = 1; i <= n; i )
{
d[i] = dis[1][i];
vis[i] = 0;
}
for(int i = 1; i <= n; i )
{
int minx = INF;
int now;
for(int j = 1; j <= n; j )
{
if(!vis[j] && minx > d[j])
{
now = j;
minx = d[j];
}
}
vis[now] = 1;
for(int k = 1; k <= n; k )
{
if(!vis[k] && d[k] > dis[now][k])
d[k] = dis[now][k];
}
}
int sum = 0;
for(int i = 1; i <= n; i )
sum = d[i];
printf("%dn",sum);
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i )
for(int j = 1; j <= n; j )
{
scanf("%d",&dis[i][j]);
}
scanf("%d",&q);
int x,y;
while(q --)
{
scanf("%d%d",&x,&y);
dis[x][y] = dis[y][x] = 0;
}
prim();
return 0;
}
