题意:要在一天之内访问所有的奶牛(路过一个点就必须停下来交谈),并且最后需要选择一个点睡上一觉(交谈多一次)所需的花费。
思路:我已经弱到看不懂中文题了啊。样例又是错的,数据范围也是错的。遇到这种题目就GG。
其实就是你选择一个点出发,走完所有点后必须回到这个点睡一觉(加多一次点权),因此选一个点权最小的出发就可以了。
因为你走出去,必须走回来,而且必须访问边的两点,所以一条边的边权就是(num[u] + num[v] + 2 * w)。num[]代表点权。
记得存点的数组要开1e5。
正确的样例:
5 6
1010206301 2 52 3 52 4 123 4 172 5 153 5 6answer : 1781 #include2 using namespace std; 3 #define N 100010 4 typedef long long LL; 5 struct Edge { 6 int u, v, nxt, w; 7 bool operator < (const Edge &a) { return w < a.w; } 8 } edge[N*2]; 9 int fa[N], head[N], tot, num[N]; LL ans;10 void Add(int u, int v, int w) {11 edge[tot] = (Edge) { u, v, head[u], w }; head[u] = tot++;12 edge[tot] = (Edge) { v, u, head[v], w }; head[v] = tot++;13 }14 int Find(int x) { if(fa[x] == x) return x; return fa[x] = Find(fa[x]); }15 void Merge(int x, int y) { x = Find(x), y = Find(y); if(x != y) fa[x] = y; }16 void Kruskal(int n) {17 sort(edge, edge + tot); int cnt = 0;18 for(int i = 0; i < tot; i++) fa[i] = i;19 for(int i = 0; i < tot; i++) {20 int u = edge[i].u, v = edge[i].v, w = edge[i].w;21 if(Find(u) == Find(v)) continue;22 Merge(u, v); ans += w;23 }24 }25 int main() {26 int n, p; scanf("%d%d", &n, &p);27 ans = 1000000000;28 for(int i = 1; i <= n; i++) {29 scanf("%d", &num[i]); ans = min(ans, (LL)num[i]);30 }31 memset(head, -1, sizeof(head)); tot = 0;32 for(int i = 1; i <= p; i++) {33 int u, v, w; scanf("%d%d%d", &u, &v, &w);34 Add(u, v, w * 2 + num[u] + num[v]);35 }36 Kruskal(n);37 cout << ans << endl;38 }