SSLOJ 1462.灌水

题目

题目描述

Farmer John已经决定把水灌到他的n块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。
建造一个水库需要花费wi,连接两块土地需要花费Pij.
计算Farmer John所需的最少代价。

输入

*第一行：一个数n

*第二行到第n+1行：第i+1行含有一个数wi

*第n+2行到第2n+1行：第n+1+i行有n个被空格分开的数，第j个数代表pij。

输出

*第一行：一个单独的数代表最小代价.

样例

input:
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
output:
9

说明

输出详解：

Farmer John在第四块土地上建立水库，然后把其他的都连向那一个，这样就要花费3+2+2+2=9

Data Constraint
对于20%的数据，n<=10;
对于60%的数据，n<=100;
对于100%的数据，n<=300,wi<=100000,pij<=100000,pij=pji,pii=0;

思路

其实这题就是最小生成树，设一个0号节点（农田），与其他农田相连，边权就是其他农田修水库的花费，跑一边最小生成树即可（当时竟然没想出来）

反思

以后做题思路要灵活，仔细想

代码

题目简单不写注释（其实是懒）

#include <iostream>
#include <cstdio>
#include <queue>
#define nn 310
using namespace std;
int read(){int re = 0;char c = getchar();while(c < '0' || c > '9')c = getchar();while(c >= '0' && c <= '9'){re = (re << 1) + (re << 3) + c - '0';c = getchar(); }return re;
}
struct edge{int y , w;bool operator < (const edge &a)const{return w > a.w;}
}k;
edge pus(int y , int w){edge re;re.y = y ; re.w = w;return re;
}
priority_queue<edge> q;int n;
int map[nn][nn];
bool vis[nn];
int sum;
int main(){n = read();for(int i = 1 ; i <= n ; i++)map[0][i] = map[i][0] = read();for(int i = 1 ; i <= n ; i++)for(int j = 1 ; j <= n ; j++)map[i][j] = read();vis[0] = true;	for(int i = 1 ; i <= n ; i++)q.push(pus(i , map[0][i]));for(int i = 1 ; i <= n ; i++){k = q.top();while(vis[k.y]){q.pop();k=q.top();}vis[k.y] = true;sum += k.w;for(int j = 1 ; j <= n ; j++){if(!vis[j])q.push(pus(j , map[k.y][j]));}}cout << sum;return 0;
}