2017暑期集训Day 6

首页 > 代码库 > 2017暑期集训Day 6

2024-10-17 19:47:39 211人阅读

T1:华容道

Code:

  1 #include<iostream> 
  2 #include<cmath> 
  3 #include<cstdio> 
  4 #include<cstdlib> 
  5 #include<cstring> 
  6 #include<algorithm> 
  7 #define inf 707406378 
  8 #define ME 100005 
  9 #define MN 1505 
 10 #define len 6005 
 11 #define p (m+2) 
 12 #define q (n+2) 
 13 using namespace std; 
 14 struct edge{ 
 15     int to,next,val; 
 16 }e[ME]; 
 17 int head[len],dis[MN],q1[len],dir[4],xy[6],dist[len],qu[len]; 
 18 bool vist[MN],map[MN],vis[len]; 
 19 int n,m,qq,cnt=1; 
 20 void ins (int x,int y,int v){ 
 21     cnt++;e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt;e[cnt].val=v; 
 22 } 
 23 void bfs(int s,int t) 
 24 { 
 25     memset(dis,0,sizeof(dis)); 
 26     memset(vist,0,sizeof(vist));dis[s]=1;vist[t]=1; 
 27     int qh=0,qt=1;q1[1]=s;vist[s]=1; 
 28     while (qh!=qt){ 
 29         qh++; 
 30         for (int k=0;k<4;k++){ 
 31             int v=q1[qh]+dir[k]; 
 32             if (vist[v]||map[v]) continue; 
 33             q1[++qt]=v;vist[v]=1; 
 34             dis[v]=dis[q1[qh]]+1; 
 35         } 
 36     } 
 37 } 
 38 void addedge() 
 39 { 
 40     for (int i=1;i<=n;i++) 
 41     for (int j=1;j<=m;j++) if (!map[i*p+j]) 
 42     for (int k=0;k<4;k++){ 
 43         int cur=i*p+j,v=cur+dir[k]; 
 44         if (map[v]) continue;bfs(v,cur); 
 45         for (int l=0;l<4;l++) if (k!=l){ 
 46             int u=cur+dir[l]; 
 47             if (map[u]||!(dis[u])) continue; 
 48             ins(k*p*q+cur,l*p*q+cur,dis[u]-1); 
 49         } 
 50         ins(k*p*q+cur,(k^1)*p*q+v,1); 
 51     }  
 52 } 
 53 int spfa(int s,int t) 
 54 { 
 55     if (s==t) return 0; 
 56     bfs(xy[0]*p+xy[1],xy[2]*p+xy[3]); 
 57     int qh=0,qt=0; 
 58     memset(vis,0,sizeof(vis)); 
 59     memset(dist,127/3,sizeof(dist)); 
 60     for (int k=0;k<4;k++) 
 61     if (!map[s+dir[k]]&&dis[s+dir[k]]){ 
 62         int v=k*p*q+s; 
 63         (++qt)%=len;qu[qt]=v;vis[v]=1; 
 64         dist[v]=dis[s+dir[k]]-1; 
 65     } 
 66     while(qh!=qt){ 
 67         (++qh)%=len;int w=qu[qh]; 
 68         for (int i=head[w];i;i=e[i].next){ 
 69             int v=e[i].to; 
 70             if (dist[v]>dist[w]+e[i].val){ 
 71                 dist[v]=dist[w]+e[i].val; 
 72                 if (!vis[v]){ 
 73                     vis[v]=1; 
 74                     if (dist[v]<dist[(qh+1)%len]){ 
 75                         qu[qh]=v;qh=(qh-1+len)%len; 
 76                     }else{ 
 77                         (++qt)%=len;qu[qt]=v; 
 78                     } 
 79                 } 
 80             } 
 81         } 
 82         vis[w]=0; 
 83     }int ans=inf; 
 84     for (int k=0;k<4;k++) ans=min(ans,dist[k*p*q+t]); 
 85     return ans==inf?-1:ans; 
 86 } 
 87 int main() 
 88 { 
 89     scanf("%d%d%d",&n,&m,&qq); 
 90     dir[0]=1;dir[1]=-1;dir[2]=p;dir[3]=-p; 
 91     for (int i=1;i<=n;i++) 
 92     for (int j=1;j<=m;j++){ 
 93         scanf("%d",&map[i*p+j]);map[i*p+j]^=1; 
 94     } 
 95     for (int i=0;i<=q;i++) map[i*p]=map[i*p+p-1]=1; 
 96     for (int i=0;i<=p;i++) map[i]=map[p*q-p+i]=1;addedge(); 
 97     for (int i=1;i<=qq;i++){ 
 98         for (int j=0;j<6;j++) scanf("%d",&xy[j]); 
 99         printf("%d\n",spfa(xy[2]*p+xy[3],xy[4]*p+xy[5])); 
100     } 
101     return 0; 
102 }

T2:次短路

Code:

 1 #include<cstdio> 
 2 #include<cstring> 
 3 #include<algorithm> 
 4 #include<queue> 
 5 #include<iostream> 
 6 #define MN 5005 
 7 #define ME 200005 
 8 #define mp(x,y) make_pair(x,y) 
 9 using namespace std; 
10 inline int in(){ 
11     int x=0;bool f=0; char c; 
12     for (;(c=getchar())<‘0‘||c>‘9‘;f=c==‘-‘); 
13     for (x=c-‘0‘;(c=getchar())>=‘0‘&&c<=‘9‘;x=(x<<3)+(x<<1)+c-‘0‘); 
14     return f?-x:x; 
15 } 
16 typedef pair<int,int> P; 
17 struct edge{ 
18     int to,next,val; 
19 }e[ME]; 
20 int head[MN],dis[MN],dis2[MN]; 
21 int n,m,u,v,c,cnt=0; 
22 inline void ins(int x,int y,int v){ 
23     e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;e[cnt].val=v; 
24 } 
25 void dijkstra(){ 
26     priority_queue<P,vector<P>,greater<P> >q; 
27     memset(dis,0x3f,sizeof(dis)); 
28     memset(dis2,0x3f,sizeof(dis2));dis[1]=0;q.push(mp(0,1)); 
29     while(!q.empty()){ 
30         P p=q.top();q.pop();int x=p.second; 
31         if (dis2[x]<p.first) continue; 
32         for (int i=head[x];i;i=e[i].next){ 
33             int v=e[i].to; 
34             if (dis[v]==p.first+e[i].val) continue; 
35             if (dis[v]>p.first+e[i].val){  
36                 dis2[v]=dis[v];dis[v]=p.first+e[i].val; 
37                 q.push(mp(dis[v],v));q.push(mp(dis2[v],v)); 
38             }else if (dis2[v]>p.first+e[i].val){ 
39                 dis2[v]=p.first+e[i].val;q.push(mp(dis2[v],v)); 
40             } 
41         } 
42     } 
43 } 
44 int main() 
45 { 
46     n=in();m=in(); 
47     for (int i=1;i<=m;++i){ 
48         u=in();v=in();c=in(); 
49         ins(u,v,c);ins(v,u,c); 
50     }dijkstra();printf("%d",dis2[n]);return 0; 
51 }

T3:保卫萝卜

Code:

  1 #include<iostream> 
  2 #include<cmath> 
  3 #include<cstdio> 
  4 #include<cstdlib> 
  5 #include<cstring> 
  6 #include<algorithm> 
  7 #define inf 707406378 
  8 #define ME 100005 
  9 #define MN 1505 
 10 #define len 6005 
 11 #define p (m+2) 
 12 #define q (n+2) 
 13 using namespace std; 
 14 struct edge{ 
 15     int to,next,val; 
 16 }e[ME]; 
 17 int head[len],dis[MN],q1[len],dir[4],xy[6],dist[len],qu[len]; 
 18 bool vist[MN],map[MN],vis[len]; 
 19 int n,m,qq,cnt=1; 
 20 void ins (int x,int y,int v){ 
 21     cnt++;e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt;e[cnt].val=v; 
 22 } 
 23 void bfs(int s,int t) 
 24 { 
 25     memset(dis,0,sizeof(dis)); 
 26     memset(vist,0,sizeof(vist));dis[s]=1;vist[t]=1; 
 27     int qh=0,qt=1;q1[1]=s;vist[s]=1; 
 28     while (qh!=qt){ 
 29         qh++; 
 30         for (int k=0;k<4;k++){ 
 31             int v=q1[qh]+dir[k]; 
 32             if (vist[v]||map[v]) continue; 
 33             q1[++qt]=v;vist[v]=1; 
 34             dis[v]=dis[q1[qh]]+1; 
 35         } 
 36     } 
 37 } 
 38 void addedge() 
 39 { 
 40     for (int i=1;i<=n;i++) 
 41     for (int j=1;j<=m;j++) if (!map[i*p+j]) 
 42     for (int k=0;k<4;k++){ 
 43         int cur=i*p+j,v=cur+dir[k]; 
 44         if (map[v]) continue;bfs(v,cur); 
 45         for (int l=0;l<4;l++) if (k!=l){ 
 46             int u=cur+dir[l]; 
 47             if (map[u]||!(dis[u])) continue; 
 48             ins(k*p*q+cur,l*p*q+cur,dis[u]-1); 
 49         } 
 50         ins(k*p*q+cur,(k^1)*p*q+v,1); 
 51     }  
 52 } 
 53 int spfa(int s,int t) 
 54 { 
 55     if (s==t) return 0; 
 56     bfs(xy[0]*p+xy[1],xy[2]*p+xy[3]); 
 57     int qh=0,qt=0; 
 58     memset(vis,0,sizeof(vis)); 
 59     memset(dist,127/3,sizeof(dist)); 
 60     for (int k=0;k<4;k++) 
 61     if (!map[s+dir[k]]&&dis[s+dir[k]]){ 
 62         int v=k*p*q+s; 
 63         (++qt)%=len;qu[qt]=v;vis[v]=1; 
 64         dist[v]=dis[s+dir[k]]-1; 
 65     } 
 66     while(qh!=qt){ 
 67         (++qh)%=len;int w=qu[qh]; 
 68         for (int i=head[w];i;i=e[i].next){ 
 69             int v=e[i].to; 
 70             if (dist[v]>dist[w]+e[i].val){ 
 71                 dist[v]=dist[w]+e[i].val; 
 72                 if (!vis[v]){ 
 73                     vis[v]=1; 
 74                     if (dist[v]<dist[(qh+1)%len]){ 
 75                         qu[qh]=v;qh=(qh-1+len)%len; 
 76                     }else{ 
 77                         (++qt)%=len;qu[qt]=v; 
 78                     } 
 79                 } 
 80             } 
 81         } 
 82         vis[w]=0; 
 83     }int ans=inf; 
 84     for (int k=0;k<4;k++) ans=min(ans,dist[k*p*q+t]); 
 85     return ans==inf?-1:ans; 
 86 } 
 87 int main() 
 88 { 
 89     scanf("%d%d%d",&n,&m,&qq); 
 90     dir[0]=1;dir[1]=-1;dir[2]=p;dir[3]=-p; 
 91     for (int i=1;i<=n;i++) 
 92     for (int j=1;j<=m;j++){ 
 93         scanf("%d",&map[i*p+j]);map[i*p+j]^=1; 
 94     } 
 95     for (int i=0;i<=q;i++) map[i*p]=map[i*p+p-1]=1; 
 96     for (int i=0;i<=p;i++) map[i]=map[p*q-p+i]=1;addedge(); 
 97     for (int i=1;i<=qq;i++){ 
 98         for (int j=0;j<6;j++) scanf("%d",&xy[j]); 
 99         printf("%d\n",spfa(xy[2]*p+xy[3],xy[4]*p+xy[5])); 
100     } 
101     return 0; 
102 }

T4:派对

Code:

 1 #include<cstdio> 
 2 #include<cstring> 
 3 #include<algorithm> 
 4 #define ME 9000005 
 5 #define MA 205 
 6 #define MB 3005 
 7 using namespace std; 
 8 inline int in(){ 
 9     int x=0;bool f=0; char c; 
10     for (;(c=getchar())<‘0‘||c>‘9‘;f=c==‘-‘); 
11     for (x=c-‘0‘;(c=getchar())>=‘0‘&&c<=‘9‘;x=(x<<3)+(x<<1)+c-‘0‘); 
12     return f?-x:x; 
13 } 
14 struct edge{ 
15     int to,next; 
16 }e[ME]; 
17 int head[MB],a[MA],b[MB],bi[2048],sum[2],x,y,res; 
18 bool mp[MA][MB],vis[MB];  
19 int cnt=0,na,nb,m; 
20 inline void ins(int x,int y){ 
21     e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt; 
22 } 
23 inline int max(int x,int y){return x>y?x:y;} 
24 inline void pre(){ 
25     for (int i=0;i<2048;++i){ 
26         int x=i;bi[i]=0; 
27         while (x){bi[i]+=(x&1);x>>=1;} 
28     } 
29 } 
30 inline void dfs(int x,bool c){ 
31     vis[x]=1;++sum[c]; 
32     for (int i=head[x];i;i=e[i].next){ 
33         int v=e[i].to;if (!vis[v]) dfs(v,c^1); 
34     } 
35 }  
36 inline int col(int n){ 
37     for (int i=1;i<=n;++i) 
38     for (int j=i+1;j<=n;++j) 
39     if (((b[i]^b[j])&1)&&!(bi[b[i]|b[j]]&1)&&!vis[i]&&!vis[j]) ins(i,j),ins(j,i); 
40     int ans=0;for (int i=1;i<=n;++i)if (!vis[i]){ 
41         sum[0]=sum[1]=0;dfs(i,1);ans+=max(sum[0],sum[1]); 
42     }return ans; 
43 } 
44 int main() 
45 { 
46     na=in();nb=in();m=in();pre();res=0; 
47     for (int i=1;i<=na;++i) a[i]=in(); 
48     for (int i=1;i<=nb;++i) b[i]=in(); 
49     for (int i=1;i<=m;++i) x=in(),y=in(),mp[x][y]=1; 
50     memset(vis,0,sizeof(vis));res=col(nb); 
51     for (int i=1;i<=na;++i){ 
52         memset(vis,0,sizeof(vis)); 
53         for (int j=1;j<=nb;++j) if (!mp[i][j]) vis[j]=1; 
54         res=max(res,col(nb)+1); 
55     } 
56     for (int i=1;i<=na;++i) 
57     for (int j=i+1;j<=na;++j){ 
58         if (!((a[i]^a[j])&1)) continue; 
59         memset(vis,0,sizeof(vis)); 
60         for (int k=1;k<=nb;++k) if ((!mp[i][k])||(!mp[j][k])) vis[k]=1; 
61         res=max(res,col(nb)+2); 
62     }printf("%d",res);return 0; 
63 }

2017暑期集训Day 6

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 2017暑期集训Day 6

2017暑期集训Day 6

看完仍有疑问？有类似问题直接问程序猿