打井

洛谷 P1550

我刚开始看这道题目的时候发现这题似乎无从下手

我首先开始从贪心角度考虑，想了两种情况：① 以打井的代价贪心 ② 以连接的代价贪心

但是后来都被我否认了—_—

考虑一下这种情况：一) 打井的价格很小但是连接的价格很大，此时，①不是最优解二) 打井的价格很大但是连接的价格很小，此时②不是最优解

所以这道题不能用一般的贪心考虑

那该怎么做呢？

这时候我看到矩阵的斜线上都是0，感到很别扭，想干点事

然后想到这些0的意义：从i到j点的连接代价

哦！那自己连自己不就是在自己这个点凿井的代价吗？

假设有一个k点，我们认为如果每个点连接k的代价都是凿井的代价的话，那么矩阵中就可以将(i,k) 0 修改为 val[i]

由于不能自己连自己，所以我们可以用0或n+1来充当这个k

然后整个算法的流程就是下面这个图：

代码是非常好打的：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int N = 400,M = 160010;
 7 struct node
 8 {
 9     int x,y,v;
10 }a[M];
11 int fa[N];
12 int n,val[N],cnt,Ans;
13 bool cmp(node p,node q)
14 {
15     return p.v<q.v;
16 }
17 int getfa(int x)
18 {
19     if (fa[x]!=x) fa[x]=getfa(fa[x]);
20     return fa[x];
21 }
22 inline int read()
23 {
24     int x=0,w=1; char c=getchar();
25     while (c>'9' || c<'0') {if (c=='-') w=-1; c=getchar();}
26     while (c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0'; c=getchar();}
27     return w*x;
28 }
29 int main()
30 {
31     n=read();
32     for (int i=1;i<=n;++i) val[i]=read(),fa[i]=i;
33     fa[n+1]=n+1;
34     for (int i=1;i<=n;++i)
35     {
36         for (int j=1;j<=n;++j)
37         {
38             int x; x=read();
39             if (i==j) a[++cnt].x=i,a[cnt].y=n+1,a[cnt].v=val[i];
40             else a[++cnt].x=i,a[cnt].y=j,a[cnt].v=x;
41         }
42     }
43     sort(a+1,a+cnt+1,cmp);
44     for (int i=1;i<=cnt;++i)
45     {
46         int t1,t2; 
47         t1=getfa(a[i].x),t2=getfa(a[i].y);
48         if (t1!=t2) fa[t1]=t2,Ans+=a[i].v;
49     }
50     printf("%d
",Ans);
51     return 0;
52 }

View Code

CSP-S RP++