luoguP2266 爱的距离

题目：http://www.luogu.org/problem/show?pid=2266

题解：感觉题意不清，就去瞅题解了T_T

然后发现好水。。。

类似于MST，我们把边从小到大加进去就可以了。

每加入一条边，判断是否符合条件，统计一下ans。

程序的具体实现有一些技巧

注释写在代码里

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<string>

 #include<set>

 #include<map>

 #include<vector>

 #include<algorithm>

 #include<queue>

 #define for0(i,n) for(int i=0;i<=n;i++)

 #define for1(i,n) for(int i=1;i<=n;i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,y,x) for(int i=(y);i>=(x);i--)

 #define maxn 1000000+5

 #define num(i,j) (i-1)*m+j

 #define ll long long

 using namespace std;

 inline ll read()

 {

     ll x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 ll n,m,k,tot,f[maxn],g[maxn],fa[maxn],v[maxn],a[][];

 struct edge{int x,y;ll w;}e[*maxn];

 inline bool cmp(edge a,edge b){return a.w<b.w;}

 inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();m=read();k=read();

     for1(i,n)for1(j,m)a[i][j]=read(),fa[num(i,j)]=num(i,j),f[num(i,j)]=;//f[x]表示x集合内有多少点

     for1(i,n)for1(j,m)g[num(i,j)]=read();//g[x]表示集合x内有多少个需要统计答案的点

     for1(i,n)for1(j,m)

     {

         if(i<n)e[++tot].x=num(i,j),e[tot].y=num(i+,j),e[tot].w=abs(a[i][j]-a[i+][j]);

         if(j<m)e[++tot].x=num(i,j),e[tot].y=num(i,j+),e[tot].w=abs(a[i][j]-a[i][j+]);//连边

     }

     sort(e+,e+tot+,cmp);//排序

     ll ans=;

     for1(i,tot)

     {

         int x=find(e[i].x),y=find(e[i].y);

         if(x!=y)

         {

             if(f[x]+f[y]>=k)

             {

                 if(!v[x])ans+=(ll)g[x]*(ll)e[i].w,v[x]=;//v[x]表示以x为代表元的集合的答案是否计算过

                 if(!v[y])ans+=(ll)g[y]*(ll)e[i].w,v[y]=;

             }

             fa[x]=y;f[y]+=f[x];g[y]+=g[x];//合并

         }

     }

     cout<<ans<<endl;

     return ;

 }