怎么根据网站前端做网站后台,多语言多商户商城源码,wordpress auto,提供网站建设题意 Farmer John已经决定把水灌到他的n(1n300)块农田#xff0c;农田被数字1到n标记。把一块土地进行灌水有两种方法#xff0c;从其他农田饮水#xff0c;或者这块土地建造水库。 建造一个水库需要花费Wi(1Wi100000),连接两块土地需要花费Pij(1pijn300)块农田农田被数字1到n标记。把一块土地进行灌水有两种方法从其他农田饮水或者这块土地建造水库。 建造一个水库需要花费Wi(1Wi100000),连接两块土地需要花费Pij(1pij100000,pijpji,pii0). 计算Farmer John所需的最少代价。 思路 很经典的最小生成树模型……很久没做最小生成树一下子没想出来TAT…… 首先得有个水源吧设个虚节点当水源然后连向每个土地权值为建造水库的花费其他的照常建图然后求最小生成树就行了。 代码 [cpp] #include iostream #include cstdio #include cmath #include algorithm #include string #include cstring #include vector #include set #include stack #include queue #define MID(x,y) ((xy)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, end) for (int i begin; i end; i ) using namespace std; const int MAX 305; struct edge{ int v, w; edge(){ } edge(int _v, int _w){ v _v; w _w; } }; struct MST{ vector edge adj[MAX]; int dist[MAX]; bool vis[MAX]; priority_queue pairint, int, vectorpairint, int , greaterpairint, int PQ; void init(int n){ for (int i 0; i n; i ){ adj[i].clear(); vis[i] false; } } void add_edge(int u, int v, int w){ adj[u].push_back(edge(v, w)); adj[v].push_back(edge(u, w)); } int solve(int s, int n){ for (int i 0; i n; i ) dist[i] 0x3fffffff; while(!PQ.empty()) PQ.pop(); dist[s] 0; PQ.push(make_pair(0, s)); while(!PQ.empty()){ int u PQ.top().second; PQ.pop(); vis[u] true; for (int i 0; i (int)adj[u].size(); i ){ int v adj[u][i].v, w adj[u][i].w; if (!vis[v] dist[v] w){ dist[v] w; PQ.push(make_pair(w, v)); } } } int res 0; for (int i 1; i n; i ) res dist[i]; return res; } }prim; int main(){ //freopen(test.in, r, stdin); //freopen(test.out, w, stdout); int n; scanf(%d, n); prim.init(n1); for (int i 1; i n; i ){ int tmp; scanf(%d, tmp); prim.add_edge(n1, i, tmp); } for (int i 1; i n; i ){ for (int j 1; j n; j ){ int tmp; scanf(%d, tmp); if (i j) continue; prim.add_edge(i, j, tmp); } } printf(%d\n, prim.solve(n1, n1)); return 0; } [/cpp]转载于:https://www.cnblogs.com/AbandonZHANG/p/4114351.html
