Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

媽题啊!dp求可行部分解+最大流,32ms,1A,如果去掉一块地只熊建一栋别墅的限制的话怎么做呀?(祘法應該是O(26*K*M*N)的)

Posted by KatrineYang at 2016-09-25 11:51:31 on Problem 1358 and last updated at 2016-09-25 11:55:48
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator