Quantity Of The Stones
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 45 Accepted Submission(s) : 11
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
xysDavidCN wants to fool two fools Jeflie and BandBand, so he designs a game to play with them.
xysDavidCN puts n piles of stones on the floor. Then he asks BandBand to observe the stones. Jeflie is not allowed to see the stones in the game.
Then, BandBand should estimate and tell Jeflie how many stones each pile has at most. And xysDavidCN will give BandBand m chances to estimate and tell Jeflie messages.
The message must be "the total amount from the i-th pile to the j-th pile is at least k stones".
After that, Jeflie should tell xysDavidCN how many stones of all the n piles at least.
Because BandBand is fool, he may make some wrong estimates leading Jeflie not figure it out.
xysDavidCN puts n piles of stones on the floor. Then he asks BandBand to observe the stones. Jeflie is not allowed to see the stones in the game.
Then, BandBand should estimate and tell Jeflie how many stones each pile has at most. And xysDavidCN will give BandBand m chances to estimate and tell Jeflie messages.
The message must be "the total amount from the i-th pile to the j-th pile is at least k stones".
After that, Jeflie should tell xysDavidCN how many stones of all the n piles at least.
Because BandBand is fool, he may make some wrong estimates leading Jeflie not figure it out.
Input
There are multiple test cases. The first line contains an integer T (T<=100), indicating the index of the test cases.
T test cases follow. Each test case contains two integers n and m (0<n<=1000, 0<m<=10000) in the first line.
Then follow n integers next line. The i-th integer indicates that there are at most si stones in the i-th pile, each integer will not exceed 10^9.
Next m lines contain 3 integers i, j, k (0<i<j<=n, 0<k<10^9) each line. It means that the total amount of stones from the i-th pile to the j-th pile is at least k.
T test cases follow. Each test case contains two integers n and m (0<n<=1000, 0<m<=10000) in the first line.
Then follow n integers next line. The i-th integer indicates that there are at most si stones in the i-th pile, each integer will not exceed 10^9.
Next m lines contain 3 integers i, j, k (0<i<j<=n, 0<k<10^9) each line. It means that the total amount of stones from the i-th pile to the j-th pile is at least k.
Output
For each test case, output "Case #D: " first, D is the index of the test case.
If Jeflie can figure out how many stones of all the n piles at least, output the least summation of the n piles stones. Output "Foolish BandBand!" otherwise.
If Jeflie can figure out how many stones of all the n piles at least, output the least summation of the n piles stones. Output "Foolish BandBand!" otherwise.
Sample Input
2 3 2 10 20 10 1 2 11 2 3 13 3 1 1 2 3 2 3 6
Sample Output
Case #1: 13 Case #2: Foolish BandBand!
差分约化
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
#define INF 100000000
int n,m;
int vis[1005];
int dis[1005];
int output[1005];
int head[20000];
int v[20000];
int w[20000];
int next[20000];
int cnt;
void add(int a,int b,int c)
{
v[cnt]=b;
w[cnt]=c;
next[cnt]=head[a];
head[a]=cnt++;
}
bool spfa()
{
queue<int> q;
memset(vis,0,sizeof(vis));
memset(output,0,sizeof(output));
for(int i=0;i<=n;i++)
dis[i]=-INF;
dis[0]=0;
vis[0]=1;
q.push(0);
while(!q.empty())
{
int u=q.front();
q.pop();
output[u]++;
if(output[u]>n)
return 0;
vis[u]=0;
for(int i=head[u];i!=-1;i=next[i])
if(dis[v[i]]<dis[u]+w[i])
{
dis[v[i]]=dis[u]+w[i];
if(!vis[v[i]])
{
q.push(v[i]);
vis[v[i]]=1;
}
}
}
printf("%d\n",dis[n]);
return 1;
}
int main()
{
int t;
int c=1;
scanf("%d",&t);
while(t--)
{
cnt=0;
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
add(i,i-1,-x);
add(i-1,i,0);
}
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x-1,y,z);
}
printf("Case #%d: ",c++);
if(!spfa())
cout<<"Foolish BandBand!"<<endl;
}
return 0;
}