题目描述
星云中有n颗行星，每颗行星的位置是(x,y,z)。每次可以消除一个面（即x,y或z坐标相等）的行星，但是由于时间有限，求消除这些行星的最少次数。
输入输出格式
输入格式：
第1行为小行星个数n，第2行至第n+1行为xi, yi, zi，描述第i个小行星所在的位置。
输出格式：
共1行，为消除所有行星的最少次数。
输入输出样例
输入样例#1：
31 2 32 3 11 3 2
输出样例#1：
2
说明
1≤n≤50000 1≤x,y,z≤500
建立最小割模型，y拆成两个，一个连x，一个连z
避免重边，最好分开连边# include# define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))# define Copy(a, b) memcpy(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(2010), __(1e6 + 10), INF(2147483647);IL ll Read(){ RG char c = getchar(); RG ll x = 0, z = 1; for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); return x * z;}int n, m, num, w[__], fst[_], nxt[__], to[__], cnt;int S, T, lev[_], cur[_], max_flow, ans;queue Q;IL void Add(RG int u, RG int v, RG int f){ w[cnt] = f; to[cnt] = v; nxt[cnt] = fst[u]; fst[u] = cnt++; w[cnt] = 0; to[cnt] = u; nxt[cnt] = fst[v]; fst[v] = cnt++;}IL int Dfs(RG int u, RG int maxf){ if(u == T) return maxf; RG int ret = 0; for(RG int &e = cur[u]; e != -1; e = nxt[e]){ if(lev[to[e]] != lev[u] + 1 || !w[e]) continue; RG int f = Dfs(to[e], min(w[e], maxf - ret)); ret += f; w[e ^ 1] += f; w[e] -= f; if(ret == maxf) break; } return ret;}IL bool Bfs(){ Fill(lev, 0); lev[S] = 1; Q.push(S); while(!Q.empty()){ RG int u = Q.front(); Q.pop(); for(RG int e = fst[u]; e != -1; e = nxt[e]){ if(lev[to[e]] || !w[e]) continue; lev[to[e]] = lev[u] + 1; Q.push(to[e]); } } return lev[T];}int main(RG int argc, RG char* argv[]){ n = Read(); Fill(fst, -1); T = 2001; for(RG int i = 1; i <= 500; i++) Add(S, i, 1), Add(i + 500, i + 1000, 1), Add(i + 1500, T, 1); for(RG int i = 1, x, y, z; i <= n; i++){ x = Read(); y = Read(); z = Read(); Add(x, y + 500, 1); Add(y + 1000, z + 1500, 1); } while(Bfs()) Copy(cur, fst), max_flow += Dfs(S, INF); printf("%d\n", max_flow); return 0;}