题意：有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。

解法：先合并列在把第一行合并

关键：把行号和列号哈希

 1 /*************************************************************************
 2     > File Name: a.cpp
 3     > Author: QWX
 4     > Mail: 
 5     > Created Time: 2018/11/24 14:24:14
 6  ************************************************************************/
 7 
 8 
 9 //{{{ #include
10 #include<iostream>
11 #include<cstdio>
12 #include<algorithm>
13 #include<vector>
14 #include<cmath>
15 #include<queue>
16 #include<map>
17 #include<set>
18 #include<string>
19 #include<cstring>
20 #include<complex>
21 #include<cassert>
22 //#include<bits/stdc++.h>
23 #define vi vector<int>
24 #define pii pair<int,int>
25 #define mp make_pair
26 #define pb push_back
27 #define fi first
28 #define se second
29 #define pw(x) (1ll << (x))
30 #define sz(x) ((int)(x).size())
31 #define all(x) (x).begin(),(x).end()
32 #define rep(i,l,r) for(int i=(l);i<(r);i++)
33 #define per(i,r,l) for(int i=(r);i>=(l);i--)
34 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)
35 #define cl(a,b) memset(a,b,sizeof(a))
36 #define fastio ios::sync_with_stdio(false);cin.tie(0);
37 #define lson l , mid , ls
38 #define rson mid + 1 , r , rs
39 #define INF 0x3f3f3f3f
40 #define LINF 0x3f3f3f3f3f3f3f3f
41 #define ll long long
42 #define ull unsigned long long
43 #define dd(x) cout << #x << " = " << (x) << "," 
44 #define de(x) cout << #x << " = " << (x) << "
" 
45 #define endl "
"
46 using namespace std;
47 //}}}
48 
49 int n,m;
50 const int N=1e6+7;
51 int f[N];
52 int ans;
53 int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
54 void U(int a,int b){int x=F(a),y=F(b);if(x!=y)f[x]=y,ans+=(abs(a-b)==1?2:1);}
55 inline int id(int r,int c){return (r-1)*m+c;}
56 
57 int main()
58 {
59     cin>>n>>m;
60     FOR(i,1,n*m)f[i]=i;
61     int a,b,c,d;
62     while(cin>>a>>b>>c>>d)U(id(a,b),id(c,d));
63     ans=0;
64     FOR(j,1,m)rep(i,1,n)U(id(i,j),id(i+1,j));
65 //    de(ans);
66     rep(j,1,m)U(id(1,j),id(1,j+1));
67     cout<<ans<<endl;
68     return 0;
69 }

View Code