1. http://acm.pku.edu.cn/JudgeOnline/problem?id=3207题意:在一个圆圈上顺时针或逆时针排好N个点(0-->N-1),现在要以给定的M组端点画M条曲线段,曲线段可在圆内或圆外,判断是否存在一种画法使得这M条曲线段不相交。 分析:每一条曲线段可置于圆内或圆外。这样可用两个顶点分别表示曲线段的摆放情况,例如(顶点2*i表示第i条曲线段置于圆内,顶点2*i+1表示第i条曲线段置于圆外)。 这样对于如下图的两条曲线段 seg[i]=[a,b],seg[j]= [c,d],seg[i]和seg[j]是不能都置于园内,或都置于圆外的。所以顶点2*i和顶点2*j+1,顶点2*j和顶点2*i+1的真值情况必然相同。 【顺时距离==>用于判断圆内曲线段是否相交】 对于圆内判断是否相交可以这样:如果在a顺时到达b的过程中经过并且只经过了c,d中的一点,那么seg[a,b]和seg[c,d]必然相交。定义顺时距dist[a,b]为a顺时到达b所经过的距离(这个距离可以有几种形式),那么如果 dist[a,c]+dist[c,b]==dist[a,b] 则 “c 在a,b内”,这样如果 c,d中有且只有一点在a,b内,那么seg[a,b]和seg[c,d]必然相交。
POJ_3207 1#include <iostream> 2#include <cstring> 3#include <cstdio> 4using namespace std; 5 6const int max_v=1000+5; 7const int max_e=500+5; 8 9bool g[max_e*2][max_e*2]; 10int N,M; 11int pos[max_e][2],ord[max_e*2],num,col[max_e*2],color; 12bool used[max_e*2]; 13 14int direc(int u,int p,int v){ //u顺时针到v是否经过p,如果经过返回1否则返回-1; 15 int dist_up=(p>=u)?(p-u):(p-u+N); int dist_pv=(v>=p)?(v-p):(v-p+N); 16 int dist_sum=(v>=u)?(v-u):(v-u+N); 17 18 if(dist_up==0||dist_pv==0) return 0; //如果有一个共同点 19 return (dist_up+dist_pv==dist_sum)?1:-1; 20} 21 22void back(int v){ 23 used[v]=true; 24 col[v]=color; 25 for(int u=0;u<N;u++){ 26 if(!used[u] && g[u][v]){ 27 back(u); 28 } 29 } 30} 31void dfs(int u){ 32 used[u]=true; 33 for(int v=0;v<N;v++){ 34 if(!used[v]&&g[u][v]){ 35 dfs(v); 36 } 37 } 38 ord[num--]=u; 39} 40int main(){ 41 scanf("%d%d",&N,&M); 42 for(int i=0;i<M;i++){ 43 scanf("%d%d",&pos[i][0],&pos[i][1]); 44 } 45 memset(g,false,sizeof(g)); 46 47 for(int i=0;i<M;i++){ 48 for(int j=0;j<M;j++){ 49 if(i!=j){ 50 int direc1=direc(pos[i][0],pos[j][0],pos[i][1]); 51 int direc2=direc(pos[i][0],pos[j][1],pos[i][1]); 52 if(direc1*direc2==-1){ 53 g[2*i][2*j+1]=g[2*j+1][2*i]=true; 54 g[2*j][2*i+1]=g[2*i+1][2*j]=true; 55 } 56 } 57 } 58 } 59 60 N=M*2; num=M*2-1; 61 62 memset(used,0,sizeof(used)); 63 for(int i=0;i<N;i++) if(!used[i]) dfs(i); 64 memset(used,0,sizeof(used)); 65 color=0; 66 for(int i=0;i<N;i++) if(!used[ord[i]]){ 67 back(ord[i]); ++color; 68 } 69 70 for(int i=0;i<M;i++){ 71 if(col[2*i]==col[2*i+1]){ 72 printf("the evil panda is lying again\n"); 73 return 0; 74 } 75 } 76 printf("panda is telling the truth...\n"); 77 return 0; 78}
另外此题是判定能否将曲线段划分到两个集合中。可以用并查集来写
POJ_3207 1#include <iostream> 2#include <cstring> 3#include <cstdio> 4using namespace std; 5 6const int max_v=1000+5; 7const int max_e=500+5; 8 9 10int N,M; 11int pos[max_e][2]; 12int pnt[max_e]; 13int ct[max_e]; 14 15int direc(int u,int p,int v){ //u顺时针到v是否经过p,如果经过返回1否则返回-1; 16 int dist_up=(p>=u)?(p-u):(p-u+N); int dist_pv=(v>=p)?(v-p):(v-p+N); 17 int dist_sum=(v>=u)?(v-u):(v-u+N); 18 19 if(dist_up==0||dist_pv==0) return 0; //如果有一个共同点 20 return (dist_up+dist_pv==dist_sum)?1:-1; 21} 22 23int findSet(int u){ 24 if(pnt[u]<0) return u; 25 26 int tmp=pnt[u]; 27 pnt[u]=findSet(pnt[u]); 28 ct[u]=(ct[u]+ct[tmp])%2; 29 30 return pnt[u]; //It's pnt[u],but not tmp! 31} 32 33void unionSet(int u,int v){ 34 int pv=findSet(v),pu=findSet(u); 35 pnt[pu]=pv; 36 ct[pu]=(ct[v]-ct[u]+3)%2; 37} 38int main(){ 39 scanf("%d%d",&N,&M); 40 for(int i=0;i<M;i++){ 41 scanf("%d%d",&pos[i][0],&pos[i][1]); 42 } 43 44 memset(pnt,-1,sizeof(pnt)); 45 memset(ct,0,sizeof(ct)); 46 47 for(int i=0;i<M;i++){ 48 for(int j=i+1;j<M;j++){ 49 int direc1=direc(pos[i][0],pos[j][0],pos[i][1]); 50 int direc2=direc(pos[i][0],pos[j][1],pos[i][1]); 51 if(direc1*direc2==-1){ 52 int pi=findSet(i),pj=findSet(j); 53 if(pi==pj && ct[i]!=(ct[j]^1)){ 54 printf("the evil panda is lying again\n"); 55 return 0; 56 }else if(pi!=pj){ 57 unionSet(i,j); 58 } 59 } 60 } 61 } 62 printf("panda is telling the truth\n"); 63 return 0; 64} 65
2. http://acm.hdu.edu.cn/showproblem.php?pid=3622 (二分答案+2-sat判定)
HDU_3622_Bomb_Game 1#include <iostream> 2#include <cstring> 3#include <cstdio> 4#include <cmath> 5using namespace std; 6 7const int max_v=200+5; 8bool g[max_v][max_v]; 9bool used[max_v]; 10int N; 11int pos[max_v][2]; 12double dist[max_v][max_v]; 13int color ,col[max_v],num,ord[max_v]; 14 15double cal(int i,int j){ 16 double x1=pos[i][0]*1.0,x2=pos[j][0]*1.0,y1=pos[i][1]*1.0,y2=pos[j][1]*1.0; 17 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); 18} 19 20void back(int v){ 21 used[v]=true; 22 col[v]=color; 23 for(int u=0;u<N;u++){ 24 if(!used[u] && g[u][v]){ 25 back(u); 26 } 27 } 28} 29void dfs(int u){ 30 used[u]=true; 31 for(int v=0;v<N;v++){ 32 if(!used[v] && g[u][v]){ 33 dfs(v); 34 } 35 } 36 ord[num--]=u; 37} 38 39bool isok(double mid_dist){ 40 41 memset(g,0,sizeof(g)); 42 43 for(int i=0;i<N;i++){ 44 for(int j=0;j<N;j++){ 45 if((i/2)!=(j/2)){ 46 int ai=((i/2)*4+1)-i, bj=((j/2)*4+1)-j; 47 if(dist[i][j]<mid_dist*2.0){ 48 g[i][bj]=true; 49 g[j][ai]=true; 50 } 51 } 52 } 53 } 54 memset(used,false,sizeof(used)); 55 num=N-1; 56 for(int i=0;i<N;i++) if(!used[i]) dfs(i); 57 58 memset(used,false,sizeof(used)); 59 color=0; 60 for(int j=0;j<N;j++) if(!used[ord[j]]){ 61 ++color; back(ord[j]); 62 } 63 for(int i=0;i+1<N;i+=2){ 64 if(col[i]==col[i+1]){ 65 return false; 66 } 67 } 68 return true; 69} 70 71int main() 72{ 73 while(scanf("%d",&N)!=EOF){ 74 N*=2; 75 for(int i=0;i<N;i++){ 76 scanf("%d%d",&pos[i][0],&pos[i][1]); 77 } 78 for(int i=0;i<N;i++){ 79 for(int j=i+1;j<N;j++){ 80 dist[i][j]=dist[j][i]=cal(i,j); 81 } 82 } 83 84 85 double lt=0,rt=15000.0; 86 87 while(fabs(lt-rt)>(1e-4)){ 88 double mid=(lt+rt)/2.0; 89 if(isok(mid)){ 90 lt=mid; 91 }else{ 92 rt=mid; 93 } 94 } 95 printf("%.2f\n",lt); 96 } 97 return 0; 98} 99
3. http://acm.pku.edu.cn/JudgeOnline/problem?id=2723 二分答案 + 2-sat判定。 最开始我构图不够严谨,只是以用了某个钥匙为顶点。然后判断是不是用了某两个属于同一组的钥匙从而判断是否有解。 其实这样是不够的,因为有解的话并不一定要从同一组钥匙中选一个。所以这样转化成2-sat是不行的,应该将用第i类钥匙和不用第i类钥匙作为图的 p 和 ¬p顶点,这样p和¬p必选其一。
POJ_2723_Get_Luffy_Out 1#include <iostream> 2#include <cstdio> 3#include <cstring> 4 5using namespace std; 6 7const int max_v=5000; 8const int max_e=max_v*max_v*4; 9 10int beg[2][max_v],match[max_v],next[2][max_e],v[2][max_e],nedge[2]; 11int ord[max_v],col[max_v],color,num; bool used[max_v]; 12int N,M; 13int pos[max_v*2]; 14 15void add_edge(int ut,int vt){ 16 v[0][nedge[0]]=vt; next[0][nedge[0]]=beg[0][ut]; beg[0][ut]=nedge[0]++; 17 v[1][nedge[1]]=ut; next[1][nedge[1]]=beg[1][vt]; beg[1][vt]=nedge[1]++; 18} 19 20void back(int ep){ 21 used[ep]=true; col[ep]=color; 22 for(int bp=beg[1][ep];bp!=-1;bp=next[1][bp]){ 23 int vt=v[1][bp]; 24 if(!used[vt]){ 25 back(vt); 26 } 27 } 28} 29void dfs(int bp){ 30 used[bp]=true; 31 for(int ep=beg[0][bp];ep!=-1;ep=next[0][ep]){ int vt=v[0][ep]; 32 if(!used[vt]){ 33 dfs(vt); 34 } 35 } 36 ord[num--]=bp; 37} 38bool isok(int T){ 39 memset(beg,-1,sizeof(beg)); nedge[0]=nedge[1]=0; 40 41 for(int i=0;i<2*N;i++){ 42 if(i<match[i]){ 43 add_edge(2*i,2*match[i]+1); //用i就不用match[i]; 44 add_edge(2*match[i],2*i+1); //用match[i]就不用i; 45 } 46 } 47 for(int i=0;i+1<2*T;i+=2){ //要打开第i扇门,至少用这一组钥匙中的一个。 48 add_edge(2*pos[i]+1,2*pos[i+1]); 49 add_edge(2*pos[i+1]+1,2*pos[i]); 50 } 51 for(int i=0;i<2*T;i++){ 52 for(int j=i+1;j<2*T;j++){ 53 if((i/2)!=(j/2) && match[pos[i]]==pos[j]){//不同的两条门中有两个钥匙属于同一组 54 int partner_i=((i/2)*4+1)-i,partner_j=((j/2)*4+1)-j; 55 add_edge(2*pos[i],2*pos[partner_j]); //用pos[i]就必须用pos[partner_j]; 56 add_edge(2*pos[j],2*pos[partner_i]); //用pos[j]就必须用pos[partner_i]; 57 } 58 } 59 } 60 memset(used,0,sizeof(used)); 61 num=4*N-1; 62 for(int i=0;i<4*N;i++){ 63 if(!used[i]) dfs(i); 64 } 65 memset(used,0,sizeof(used)); 66 color=0; 67 for(int i=0;i<4*N;i++){ 68 if(!used[ord[i]]){ 69 color++; back(ord[i]); 70 } 71 } 72 for(int i=0;2*i+1<4*N;i+=2){ //不能既用i又不用i 73 if(col[2*i]==col[2*i+1]){ 74 return false; 75 } 76 } 77 return true; 78} 79 80int main() 81{ 82 while(scanf("%d%d",&N,&M),(N+M)){ 83 int ut,vt; 84 for(int i=0;i<N;i++){ 85 scanf("%d%d",&ut,&vt); 86 match[ut]=vt; match[vt]=ut; 87 } 88 for(int i=0;i<M;i++){ 89 scanf("%d%d",&pos[2*i],&pos[2*i+1]); 90 } 91 int lt=1,rt=M; 92 while(lt<=rt){ 93 int mid=(lt+rt)/2; 94 if(isok(mid)){ 95 lt=mid+1; 96 }else{ 97 rt=mid-1; 98 } 99 } 100 printf("%d\n",rt); 101 } 102 103 return 0; 104} 105
4. http://acm.pku.edu.cn/JudgeOnline/problem?id=2749 (二分+ 2SAT) 牛i 连S1和S2分别为顶点Pi 和¬Pi之后二分就行 (第一次WA后发现没用memcpy将信息备份那个nedge一直在增加,第二次WA后发现竟然将enemy和friend的输入顺序搞反了,太没素质了。悲剧)。
POJ_2749_Building roads 1#include <iostream> 2#include <cstdio> 3#include <cstring> 4using namespace std; 5 6const int max_v=2000+5; 7const int max_e=max_v*max_v*4; 8int coord[max_v][2]; 9int s[2][2]; 10int beg[2][max_v],next[2][max_e],v[2][max_e],nedge[2]; 11int beg_backup[2][max_v],nedge_backup[2]; 12bool used[max_v]; int ord[max_v],num,col[max_v],color; 13int dist[max_v],dist_s1_s2; 14int N,M,K; 15 16int cal(int a[],int b[]){ 17 return abs(a[0]-b[0])+abs(a[1]-b[1]); 18} 19 20void back(int ep){ 21 used[ep]=true; col[ep]=color; 22 for(int i=beg[1][ep];i!=-1;i=next[1][i]){ int vt=v[1][i]; 23 if(!used[vt]){ 24 back(vt); 25 } 26 } 27} 28void dfs(int bp){ 29 used[bp]=true; 30 for(int i=beg[0][bp];i!=-1;i=next[0][i]){ int vt=v[0][i]; 31 if(!used[vt]){ 32 dfs(vt); 33 } 34 } 35 ord[num--]=bp; 36} 37 38 39void add_edge(int ut,int vt){ 40 v[0][nedge[0]]=vt; next[0][nedge[0]]=beg[0][ut]; beg[0][ut]=nedge[0]++; 41 v[1][nedge[1]]=ut; next[1][nedge[1]]=beg[1][vt]; beg[1][vt]=nedge[1]++; 42} 43 44bool isok(int mid_dist){ 45 46 memcpy(beg,beg_backup,sizeof(beg)); memcpy(nedge,nedge_backup,sizeof(nedge)); 47 for(int i=0;i<2*N;i++){ 48 for(int j=i+1;j<2*N;j++){ 49 if((i/2)!=(j/2)){ 50 int part_i=((i/2)*4)+1-i,part_j=((j/2)*4)+1-j; 51 52 if( (i+j)%2==0 && dist[i]+dist[j]>mid_dist){//同一个节点 53 add_edge(i,part_j); add_edge(j,part_i); 54 }else if( (i+j)%2 && dist[i]+dist[j]+dist_s1_s2>mid_dist){ 55 add_edge(i,part_j); add_edge(j,part_i); 56 } 57 } 58 } 59 } 60 61 memset(used,0,sizeof(used)); 62 num=2*N-1; 63 for(int i=0;i<2*N;i++){ 64 if(!used[i]) dfs(i); 65 } 66 67 memset(used,0,sizeof(used)); 68 color=0; 69 70 for(int i=0;i<2*N;i++){ 71 if(!used[ord[i]]){ 72 color++; back(ord[i]); 73 } 74 } 75 76 for(int i=0;i+1<2*N;i+=2){ 77 if(col[i]==col[i+1]) return false; 78 } 79 80 return true; 81} 82int main() 83{ 84// freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); 85 while(scanf("%d%d%d",&N,&M,&K)!=EOF){ 86 87 scanf("%d%d%d%d",&s[0][0],&s[0][1],&s[1][0],&s[1][1]); 88 dist_s1_s2=cal(s[0],s[1]); 89 90 for(int i=0;i<N;i++){ 91 scanf("%d%d",&coord[i][0],&coord[i][1]); 92 } 93 int ut,vt; 94 memset(beg,-1,sizeof(beg)); 95 nedge[0]=nedge[1]=0; 96 for(int i=0;i<M;i++){//连接不同节点 97 scanf("%d%d",&ut,&vt); 98 ut--; vt--; 99 add_edge(ut*2,vt*2+1); add_edge(ut*2+1,vt*2); 100 add_edge(vt*2,ut*2+1); add_edge(vt*2+1,ut*2); 101 } 102 103 for(int i=0;i<K;i++){//ut,vt连通一个节点 104 scanf("%d%d",&ut,&vt); 105 ut--; vt--; 106 add_edge(ut*2,vt*2); add_edge(vt*2,ut*2); //同为S1 107 add_edge(ut*2+1,vt*2+1); add_edge(vt*2+1,ut*2+1); //同为S2 108 } 109 110 memcpy(beg_backup,beg,sizeof(beg)); memcpy(nedge_backup,nedge,sizeof(nedge)); 111 112 int max_dist=dist_s1_s2,min_dist=(1<<30); 113 114 for(int i=0;i<N;i++){ 115 dist[2*i]=cal(coord[i],s[0]); 116 dist[2*i+1]=cal(coord[i],s[1]); 117 max_dist=max(max_dist,dist[2*i]); max_dist=max(max_dist,dist[2*i+1]); 118 min_dist=min(min_dist,dist[2*i]); min_dist=min(min_dist,dist[2*i+1]); 119 } 120 121 if(!isok(1<<30)){ 122 printf("-1\n"); 123 continue; 124 } 125 126 int lt=min_dist*2,rt=max_dist*3; 127 128 while(lt<=rt){ 129 int mid=(lt+rt)/2; 130 if(isok(mid)){ 131 rt=mid-1; 132 }else{ 133 lt=mid+1; 134 } 135 } 136 printf("%d\n",lt); 137 } 138 return 0; 139} 140
|
|
CALENDER
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
常用链接
留言簿
随笔分类
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
Powered By: 博客园 模板提供:沪江博客
|