#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> adj[1111];
int b0[1111];
ll s[1111];
void dfs0(int x){
b0[x]=1;
for(auto i:adj[x]) {
if(!b0[i]) dfs0(i);
}
}
//0 -> not choosen
//1 -> choosen alone
//2 -> choosen with group
ll dp[1002][1002][3];
int b1[1111];
int sz[1111];
int dfs1(int x) {
b1[x]=1;
vector<int> lst;
sz[x]=1;
for(auto i:adj[x]) {
if(!b1[i]) {
sz[x]+=dfs1(i);
lst.push_back(i);
}
}
if(lst.empty()) {
dp[x][1][1]=s[x];
dp[x][0][0]=0;
return sz[x];
}
ll dp2[lst.size()+1][sz[x]+1][3];
memset(dp2, 0x0F, sizeof dp2);
dp2[0][0][0]=0;
dp2[0][1][1]=s[x];
dp2[0][1][2]=s[x];
int eddig=1;
for(int i=1;i<(int)lst.size()+1;++i) {
for(int j=0;j<=eddig;++j) {
for(int k=0;k<=sz[lst[i-1]];++k) {
//cerr<<i<<" "<<j+k<<" "<<j<<" "<<k<<" "<<dp2[i-1][j][2]<<" lst "<<lst[i-1]<<", "<<min(dp2[i][j+k][2], dp2[i-1][j][2]+min(dp[lst[i-1]][k][1], dp[lst[i-1]][k][2]))<<"\n";
dp2[i][j+k][0]=min(dp2[i][j+k][0], dp2[i-1][j][0]+min(dp[lst[i-1]][k][0], dp[lst[i-1]][k][2]));
dp2[i][j+k][0]=min(dp2[i][j+k][0], dp2[i-1][j+k][0]);
dp2[i][j+k][1]=min(dp2[i][j+k][1], dp2[i-1][j][1]+dp[lst[i-1]][k][0]);
dp2[i][j+k][1]=min(dp2[i][j+k][1], dp2[i-1][j+k][1]);
dp2[i][j+k][2]=min(dp2[i][j+k][2], dp2[i-1][j][2]+min(dp[lst[i-1]][k][1], dp[lst[i-1]][k][2]));
if(k>0) dp2[i][j+k][2]=min(dp2[i][j+k][2], min(dp2[i-1][j][0],min(dp2[i-1][j][2], dp2[i-1][j][1]))+min(dp[lst[i-1]][k][1], dp[lst[i-1]][k][2]));
dp2[i][j+k][2]=min(dp2[i][j+k][2], dp2[i-1][j+k][2]);
}
}
eddig+=sz[lst[i-1]];
}
for(int i=0;i<=eddig;++i) {
for(int j=0;j<3;++j) {
dp[x][i][j]=dp2[lst.size()][i][j];
}
}
dp[x][1][2]=1LL<<60;
return sz[x];
}
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>s[i];
for(int i=0;i<m;++i) {
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int root=n+1;
for(int i=1;i<=n;++i) {
if(!b0[i]) {
adj[root].push_back(i);
adj[i].push_back(root);
dfs0(i);
}
}
memset(dp,0x0F,sizeof dp);
dfs1(root);
int q;
cin>>q;
/*cerr<<dp[1][8][2]<<"\n";
cerr<<dp[2][1][1]<<"\n";
cerr<<dp[3][3][2]<<"\n";
cerr<<dp[4][3][0]<<"\n";
cerr<<s[1]<<"\n";*/
while(q--) {
int x;
cin>>x;
int ans=0;
for(int i=0;i<=n;++i) {
if(dp[root][i][0]<=x) {
ans=max(ans, i);
}
}
cout<<ans<<"\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
30 ms |
24184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
30 ms |
24184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
549 ms |
26208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
30 ms |
24184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
