Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
媽题啊!dp求可行部分解+最大流,32ms,1A,如果去掉一块地只熊建一栋别墅的限制的话怎么做呀?(祘法應該是O(26*K*M*N)的)#include <iostream> #include <stdio.h> #include <queue> using namespace std; const int SSS = 2147483647; const int TTT = -2147483648; bool s[101] = {false}, t[101] = {false};//false表示可用 int k,m,n,h,w;//k从1開始,m,n,h,w從洞開始 int layout[100][100][100]; int graph[100][100]; int cnt; int M,N; void init(){//所有初始化 for(int i = 0; i < 100; i++){ for(int j = 0; j < 100; j++){ graph[i][j] = 0; } } cnt = 0; M = 26; N = 1; for(int i = 0; i < 101; i++){ s[i] = t[i] = 0; } } int type(int *state){ //返回状態码。0表示不用去掉就可以建,-1表示无论去掉谁都不行,正数代表可以去掉符合条件的编号 int nonzero = -1; for(int i = 1; i <= 26; i++){ if(state[i]>0 && nonzero!=-1) return -1; else if(state[i]>0){ nonzero = i; } } if(nonzero==-1) return 0; return nonzero; } bool pushflow(){ //如果push不了,返回false queue<int> bfs; bool getT = false; int noT; int S[101] = {0}, T[101] = {0}; for(int i = 1; i < N; i++){ if(!s[i]){ S[i] = SSS; bfs.push(i); } } while(!bfs.empty()){ int cur = bfs.front(); bfs.pop(); if(cur > 0){ //是s这边的点 for(int j = 1; j <= M; j++){ if(graph[cur][j] == 1 && T[j] == 0){ bfs.push(-j); T[j] = cur; } } } else{ //是t这边的点 int j = -cur; if(!t[j]){ getT = true; noT = cur; break; } for(int i = 1; i < N; i++){ if(graph[i][j] == -1 && S[i] == 0){ bfs.push(i); S[i] = cur; } } } } if(!getT) return false; t[-noT] = true; int TtoS = 1; while(1){ if(TtoS){ //push路径当前从S端到T端 int noS = T[-noT]; graph[noS][-noT] = -1; noT = noS; } else{ //从T端到S端 int noS = S[noT]; if(noS == SSS){ s[noT] = true; break; } graph[noT][-noS] = 1; noT = noS; } TtoS = 1 - TtoS; } return true; } int main() { int t_; scanf("%d", &t_); for(int ii = 0; ii < t_; ii++){ init(); scanf("%d%d%d%d%d", &k,&m,&n,&h,&w); for(int i = 1; i <= k; i++){ for(int j = 0; j < m; j++){ char str[100]; scanf("%s", str); for(int q = 0; q < n; q++){ char tr = str[q]; if(tr == '0') layout[i][j][q] = 0; else layout[i][j][q] = tr-'A'+1; } } } if(h>m || w>n){ printf("0\n"); continue; } for(int i = 1; i <= k; i++){ for(int z = 1; z <= 26; z++) graph[N][z] = 0;//清除上一个循环可能遗留的无效的1 bool ZF = 0, KF = 0;//ZF: 是否可以直接建别墅 KF: 是否可以昆掉某个字呣建别墅 int bfh[100][27] = {0}; for(int j = 0; j < n; j++){ for(int q = 0; q < h; q++){ bfh[j][layout[i][q][j]]++; } } for(int q = 0; q <= m-h; q++){ int tmp[27] = {0}; for(int j = 0; j < w; j++){ for(int z = 1; z <= 26; z++){ tmp[z] += bfh[j][z]; } } for(int j = 0; j <= n-w; j++){ int tp = type(tmp); if(!tp) { ZF = 1; goto done; } if(tp>0){ KF = 1; graph[N][tp] = 1; } if(j==n-w) break; for(int z = 1; z <= 26; z++){ tmp[z] += (bfh[j+w][z] - bfh[j][z]); } } if(q==m-h) break; for(int j = 0; j < n; j++){ bfh[j][layout[i][q+h][j]]++; bfh[j][layout[i][q][j]]--; } } done: if(ZF) cnt++; else if(KF) N++; } while(pushflow()){ cnt++; } printf("%d\n", cnt); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator