| ||||||||||
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 |
多亏讨论区,又学了一招一直想用最大流做,好像不行的说! #include <iostream> #include <stdio.h> using namespace std; int r[25]; int d[25]; bool keyi(int); bool isInit; int from[74] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24, 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23, 8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24, 1,2,3,4,5,6,7, 0,24}; int to[74] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23, 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24, 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16, 17,18,19,20,21,22,23, 24,0}; int weight[74] = {0}; int main() { int cases; scanf("%d", &cases); for(int ii = 0; ii < cases; ii++){ //each case isInit = false; for(int i = 0; i < 24; i++) scanf("%d", &r[i]); for(int i = 0; i < 24; i++) d[i] = 0; int numD; scanf("%d", &numD); for(int i = 0; i < numD; i++){ int temp; scanf("%d", &temp); d[temp] ++; } bool yj = true; for(int i = 0; i < 24; i++){ int sum = 0; for(int j = 0; j < 8; j++){ sum += d[(i+j)%24]; } if(sum < r[(i+7)%24]){ yj = false; break; } } if(!yj){ printf("No Solution\n"); continue; } int rsum = 0; for(int i = 0; i < 24; i++) rsum += r[i]; int minAns = (rsum-1)/8+1, maxAns = numD; //minAns不一定行,maxAns肯定可以 while(maxAns > minAns){ //cout << maxAns << endl; int midAns = (minAns+maxAns)/2; if(keyi(midAns)){ maxAns = midAns; } else{ minAns = midAns+1; } } printf("%d\n", maxAns); } return 0; } void initB(){ isInit = true; for(int i = 24; i < 48; i++) weight[i] = d[i-24]; for(int i = 48; i < 65; i++) weight[i] = -r[i-41]; } bool keyi(int ans){ int del[25]; del[0] = 0; for(int i = 1; i <= 24; i++){ del[i] = 10000000; } if(!isInit){ initB(); } for(int i = 65; i < 72; i++) weight[i] = ans - r[i-65]; weight[72] = ans; weight[73] = -ans; for(int i = 0; i < 24; i++){ for(int j = 0; j < 74; j++){ if(del[to[j]] > del[from[j]] + weight[j]){ del[to[j]] = del[from[j]] + weight[j]; } } } for(int j = 0; j < 74; j++){ if(del[to[j]] > del[from[j]] + weight[j]) return 0; } return 1; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator