首页 > 代码库 > ZOJ 3229 Shoot the Bullet
ZOJ 3229 Shoot the Bullet
Shoot the Bullet
64-bit integer IO format: %lld Java class name: Main
Gensokyo is a world which exists quietly beside ours, separated by a mystical border. It is a utopia where humans and other beings such as fairies, youkai(phantoms), and gods live peacefully together. Shameimaru Aya is a crow tengu with the ability to manipulate wind who has been in Gensokyo for over 1000 years. She runs the Bunbunmaru News - a newspaper chock-full of rumors, and owns the Bunkachou - her record of interesting observations for Bunbunmaru News articles and pictures of beautiful danmaku(barrange) or cute girls living in Gensokyo. She is the biggest connoisseur of rumors about the girls of Gensokyo among the tengu. Her intelligence gathering abilities are the best in Gensokyo!
During the coming n days, Aya is planning to take many photos of m cute girls living in Gensokyo to write Bunbunmaru News daily and record at least Gx photos of girl x in total in the Bunkachou. At the k-th day, there are Ck targets, Tk1, Tk2, ..., TkCk. The number of photos of target Tki that Aya takes should be in range [Lki, Rki], if less, Aya cannot write an interesting article, if more, the girl will become angry and use her last spell card to attack Aya. What‘s more, Aya cannot take more than Dk photos at the k-th day. Under these constraints, the more photos, the better.
Aya is not good at solving this complex problem. So she comes to you, an earthling, for help.
Input
There are about 40 cases. Process to the end of file.
Each case begins with two integers 1 <= n <= 365, 1 <= m <= 1000. Then m integers, G1, G2, ..., Gm in range [0, 10000]. Then n days. Each day begins with two integer 1 <= C <= 100, 0 <= D <= 30000. Then C different targets. Each target is described by three integers, 0 <= T < m, 0 <= L <= R <= 100.
Output
For each case, first output the number of photos Aya can take, -1 if it‘s impossible to satisfy her needing. If there is a best strategy, output the number of photos of each girl Aya should take at each day on separate lines. The output must be in the same order as the input. If there are more than one best strategy, any one will be OK.
Output a blank line after each case.
Sample Input
2 312 12 123 180 3 91 3 92 3 93 180 3 91 3 92 3 92 312 12 123 180 3 91 3 92 3 93 180 0 31 3 62 6 92 312 12 123 150 3 91 3 92 3 93 210 0 31 3 62 6 12
Sample Output
3666666636963369-1
External Links
Wikipedia
Touhou Wiki
Source
Author
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 1500; 18 struct arc{ 19 int to,flow,next; 20 arc(int x = 0,int y = 0,int z = -1){ 21 to = x; 22 flow = y; 23 next = z; 24 } 25 }; 26 int head[maxn],d[maxn],cur[maxn],tot,n,m,S,T; 27 arc e[1000010]; 28 void add(int u,int v,int flow){ 29 e[tot] = arc(v,flow,head[u]); 30 head[u] = tot++; 31 e[tot] = arc(u,0,head[v]); 32 head[v] = tot++; 33 } 34 bool bfs(){ 35 queue<int>q; 36 memset(d,-1,sizeof(d)); 37 d[S] = 1; 38 q.push(S); 39 while(!q.empty()){ 40 int u = q.front(); 41 q.pop(); 42 for(int i = head[u]; ~i; i = e[i].next){ 43 if(e[i].flow && d[e[i].to] == -1){ 44 d[e[i].to] = d[u] + 1; 45 q.push(e[i].to); 46 } 47 } 48 } 49 return d[T] > -1; 50 } 51 int dfs(int u,int low){ 52 if(u == T) return low; 53 int tmp = 0,a; 54 for(int &i = cur[u]; ~i; i = e[i].next){ 55 if(e[i].flow && d[e[i].to] == d[u] + 1 && (a=dfs(e[i].to,min(e[i].flow,low)))){ 56 tmp += a; 57 low -= a; 58 e[i].flow -= a; 59 e[i^1].flow += a; 60 if(!low) break; 61 } 62 } 63 if(!tmp) d[u] = -1; 64 return tmp; 65 } 66 int dinic(){ 67 int tmp = 0; 68 while(bfs()){ 69 memcpy(cur,head,sizeof(head)); 70 tmp += dfs(S,INF); 71 } 72 return tmp; 73 } 74 int de[maxn],pos[400][maxn],low[400][maxn]; 75 int main() { 76 int gs,day,dayup,ith,down,up; 77 while(~scanf("%d %d",&n,&m)){ 78 memset(head,-1,sizeof(head)); 79 memset(de,0,sizeof(de)); 80 memset(low,-1,sizeof(low)); 81 int full = tot = 0; 82 for(int i = 1; i <= m; i++){ 83 scanf("%d",&gs); 84 add(n+i,n+m+1,INF-gs);//女孩到汇点 85 de[n+i] -= gs; 86 de[n+m+1] += gs; 87 } 88 for(int i = 1; i <= n; i++){ 89 scanf("%d %d",&day,&dayup); 90 add(0,i,dayup); 91 for(int j = 1; j <= day; j++){ 92 scanf("%d %d %d",&ith,&down,&up); 93 pos[i][++ith] = tot;//第i天第ith个女孩 94 add(i,n+ith,up-down);//转化 95 de[i] -= down; 96 de[n+ith] += down; 97 low[i][ith] = down; 98 } 99 }100 add(n+m+1,0,INF);101 S = n+m+2;102 T = n+m+3;103 for(int i = 0; i <= n + m + 1; i++){104 if(de[i] > 0){105 full += de[i];106 add(S,i,de[i]);107 }108 if(de[i] < 0) add(i,T,-de[i]);109 }110 if(dinic() == full){111 S = 0;112 T = n + m + 1;113 printf("%d\n",dinic());114 for(int i = 1; i <= n; i++){115 for(int j = 1; j <= m; j++)116 if(low[i][j] > -1) printf("%d\n",low[i][j] + e[pos[i][j]^1].flow);117 }118 119 }else puts("-1");120 puts("");121 }122 return 0;123 }
ZOJ 3229 Shoot the Bullet