关键词:
【BZOJ1976】[BeiJing2010组队]能量魔方 Cube
Description
Input
Output
Sample Input
P?
??
??
N?
Sample Output
HINT
如下状态时,可产生最多的能量。
PN
NP
NP
NN
【数据规模】
10% 的数据N≤3;
30% 的数据N≤4;
80% 的数据N≤10;
100% 的数据N≤40。
题解:经典的最小割模型,只不过变成了三维的。先黑白染色,然后黑色的点翻转源汇,具体方法:
1.S ->i 容量为i周围已确定的N个数
2.i -> T 容量为i周围已确定的P个数
上面2条边要翻转源汇
3.i <-> j 容量1
#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; int n,ans,cnt,tot,S,T; int dx[]={0,0,0,0,1,-1},dy[]={0,0,1,-1,0,0},dz[]={1,-1,0,0,0,0}; int map[50][50][50],to[2000000],next[2000000],val[2000000],d[100000],head[100000]; char str[50]; queue<int> q; int dfs(int x,int mf) { if(x==T) return mf; int i,k,temp=mf; for(i=head[x];i!=-1;i=next[i]) if(d[to[i]]==d[x]+1&&val[i]) { k=dfs(to[i],min(temp,val[i])); if(!k) d[to[i]]=0; val[i]-=k,val[i^1]+=k,temp-=k; if(!temp) break; } return mf-temp; } int bfs() { while(!q.empty()) q.pop(); memset(d,0,sizeof(d)); int i,u; q.push(S),d[S]=1; while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i!=-1;i=next[i]) { if(!d[to[i]]&&val[i]) { d[to[i]]=d[u]+1; if(to[i]==T) return 1; q.push(to[i]); } } } return 0; } inline void add(int a,int b,int c) { to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++; to[cnt]=a,val[cnt]=0,next[cnt]=head[b],head[b]=cnt++; } int main() { int i,j,k,l,x,y,z,a,b,c; scanf("%d",&n); S=0,T=tot=1; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%s",str+1); for(k=1;k<=n;k++) { if(str[k]==‘P‘) map[i][j][k]=1; if(str[k]==‘N‘) map[i][j][k]=0; if(str[k]==‘?‘) map[i][j][k]=++tot; } } memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) { if(map[i][j][k]>1) { a=b=0,c=map[i][j][k]; for(l=0;l<6;l++) { x=i+dx[l],y=j+dy[l],z=k+dz[l]; if(x&&y&&z&&x<=n&&y<=n&&z<=n) { if(map[x][y][z]==0) b++; if(map[x][y][z]==1) a++; if(map[x][y][z]>1&&((i^j^k)&1)) add(c,map[x][y][z],1),add(map[x][y][z],c,1),ans++; } } if((i^j^k)&1) swap(a,b); add(S,c,a),add(c,T,b),ans+=a+b; } if(map[i][j][k]==0) { for(l=0;l<6;l++) { x=i+dx[l],y=j+dy[l],z=k+dz[l]; if(x&&y&&z&&x<=n&&y<=n&&z<=n&&map[x][y][z]==1) ans++; } } } while(bfs()) ans-=dfs(S,1<<30); printf("%d",ans); return 0; }
bzoj1977[beijing2010组队]次小生成树tree
严格次小生成树。一开始没有特批一圈都相等的情况,一直WA,十分难受。先生成最小生成树,枚举每条非树边,连上它构成一个环,拆掉环上树边中最大的一条(若和该边相等则次大的一条)换上这条。用倍增维护一条链上的最... 查看详情
严格次小生成树(bzoj1977:[beijing2010组队]次小生成树)
非严格次小生成树很简单,先做最小生成树然后枚举没加入的边加入,替换掉这个环内最大的边最后取(min)严格次小生成树还是一样的可以考虑维护一个严格次大值最大值和枚举的边相同就替换次大值的边否则替换最大值的边最... 查看详情
bzoj1977[beijing2010组队]次小生成树tree权值线段树合并
题目描述求一张图的严格次小生成树的边权和,保证存在。输入第一行包含两个整数N和M,表示无向图的点数与边数。接下来M行,每行3个数xyz表示,点x和点y之间有一条边,边的权值为z。输出包含一行,仅一个数,表示严格次... 查看详情
[beijing2010组队]次小生成树tree
小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说:如果最小... 查看详情
[beijing2010组队]次小生成树tree(代码片段)
Description小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说:... 查看详情
bzoj1977
1977:[BeiJing2010组队]次小生成树TreeTimeLimit:10Sec MemoryLimit:512MBSubmit:3001 Solved:751[Submit][Status][Discuss]Description小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼... 查看详情
bzoj2005:[noi2010]能量采集
2005:[Noi2010]能量采集TimeLimit:10Sec MemoryLimit:552MBSubmit:4174 Solved:2494[Submit][Status][Discuss]Description栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再... 查看详情
bzoj2005[noi2010]能量採集(容斥)
[Noi2010]能量採集TimeLimit:10Sec MemoryLimit:552MBSubmit:2324 Solved:1387[Submit][Status][Discuss]Description栋栋有一块长方形的地。他在地上种了一种能量植物,这样的植物能够採集太阳光的能量。在这些植物採集能量后,栋栋... 查看详情
bzoj2005[noi2010]能量采集欧拉函数
【BZOJ2005】[Noi2010]能量采集Description栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植... 查看详情
bzoj2005[noi2010]能量采集
2005:[Noi2010]能量采集Description栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得... 查看详情
bzoj2005:[noi2010]能量采集筛法||欧拉||莫比乌斯
2005:[Noi2010]能量采集TimeLimit: 10Sec MemoryLimit: 552MB[Submit][Status][Discuss]Description栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇... 查看详情
bzoj2005:[noi2010]能量采集——题解
...id=2005Description栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐,一共... 查看详情
bzoj2005[noi2010]能量采集
Description栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐,一共有n列... 查看详情
[bzoj2005][noi2010]能量采集
...OJLuoguDescription栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐,一共... 查看详情
洛谷p4180[beijing2010组队]次小生成树tree(最小生成树,lct,主席树,倍增lca,倍增,树链剖分)
洛谷题目传送门%%%天平巨佬和山楠巨佬%%%他们的题解思路分析具体思路都在两位巨佬的题解中。这题做法挺多的,我就不对每个都详细讲了,泛泛而谈吧。首先kruskal把最小生成树弄出来,因为要求次小生成树。至于为什么次小... 查看详情
bzoj2005:[noi2010]能量采集
...)位置的植物,从(0,0)到(i,j)的连线中有k棵植物,能量损失就为2*k-1(包括端点上的植物)。求所有植物的能量损失。 n,m<=10^5【题解】 实际上对于每棵植物k就是x坐标,y坐标的公约数,不过n*m棵植物显然不能一个... 查看详情
●bzoj2005noi2010能量采集
题链:http://www.lydsy.com/JudgeOnline/problem.php?id=2005题解:一个带有容斥思想的递推。%%%首先,对于一个点(x,y)在路径(0,0)->(x,y)上,经过的点数为GCD(x,y)-1所以改点的贡献为2*GCD(x,y)-1 &nbs 查看详情
bzoj2005[noi2010]能量采集(容斥原理|欧拉筛+分块)
能量采集Description栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐,... 查看详情