1.poj2236

http://poj.org/problem?id=2236 题意明了，不解释，但是样例多次不通过，自己还是太渣…… #include <algorithm> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <string> #include <set> #include <vector> #include<cmath> using namespace std; #define maxn 1005 int par[maxn];//父亲 int Rank[maxn];//树的高度 //初始化 void init(int n) { for(int i=0;i<n;i++){ par[i]=-1; Rank[i]=0; } } //查询父亲，路径压缩 int Find(int x) { int s; for(s=x;par[s]!=-1;s=par[s]); while(s!=x){ int temp=par[x]; par[x]=s; x=temp; } return s; } //合并x，y属于的集合 void unite(int x,int y) { x=Find(x);y=Find(y); if(x==y) return; if(Rank[x]<Rank[y]){ par[x]=y; } else{ par[y]=x; if(Rank[x]==Rank[y]) Rank[x]++; } } bool same(int x,int y) { return Find(x)==Find(y); } int N,d; int x[maxn],y[maxn]; bool mark[maxn]; int dist[maxn][maxn]; int main() { scanf("%d%d",&N,&d); for(int i=0;i<N;i++){ scanf("%d%d",&x[i],&y[i]); } memset(mark,0,sizeof(mark)); memset(dist,0,sizeof(dist)); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(i==j) continue; int dx=x[i]-x[j]; int dy=y[i]-y[j]; dist[i][j]=dx*dx+dy*dy; } } init(N); char c; int x,y; while(cin>>c){ if(c=='O'){ cin>>x; x--; mark[x]=true; for(int i=0;i<N;i++){ if(i==x) continue; if(mark[i]&&dist[i][x]<=d*d){ unite(i,x); } } } else{ cin>>x>>y; x--; y--; if(same(x,y)){ cout<<"SUCCESS"<<endl; } else{ cout<<"FAIL"<<endl; } } } return 0; }

2.poj1703

http://poj.org/problem?id=1703 有多个操作，有一些让你判断两个罪犯，是否属于同一伙，并查集水题。 C++能AC，G++却超时

#include <cstdio> #include<iostream> using namespace std; #define maxn 200005 int par[maxn];//父亲 int Rank[maxn];//树的高度 //初始化 void init(int n) { for(int i=0;i<n;i++){ par[i]=-1; Rank[i]=0; } } //查询父亲，路径压缩 int Find(int x) { int s; for(s=x;par[s]!=-1;s=par[s]); while(s!=x){ int temp=par[x]; par[x]=s; x=temp; } return s; } //合并x，y属于的集合 void unite(int x,int y) { x=Find(x);y=Find(y); if(x==y) return; if(Rank[x]<Rank[y]){ par[x]=y; } else{ par[y]=x; if(Rank[x]==Rank[y]) Rank[x]++; } } bool same(int x,int y) { return Find(x)==Find(y); } int main() { int N,M; int t; scanf("%d",&t); while(t--){ scanf("%d%d",&N,&M); init(2*N); for(int i=0;i<M;i++){ char c; int p,q; cin>>c; scanf("%d%d",&p,&q); if(c=='A'){ if(same(p,q+N)){ printf("In different gangs.\n"); } else if(same(p,q)){ printf("In the same gang.\n"); } else{ printf("Not sure yet.\n"); } } else{ unite(p,q+N); unite(p+N,q); } } } return 0; }