| ||||||||||
| 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