97pts求调

#include<bits/stdc++.h>
const int N=23;
#define int long long
using namespace std;
int n,m,s,a[N+1],d[N+1],cnt,p[N+1];
struct node{
    int x,t;
}dp[1<<N];
int f[N+1];
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
bool t[N+1];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>s;
    string ss;
    getline(cin,ss);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=s;i++){
        int x=0,xx,pp=0;
        string ss;
        getline(cin,ss);
        for(int j=0;j<ss.size();j++){
            if(ss[j]!=' '){
                x*=10;
                x+=ss[j]-'0';
            }else{
                if(!pp) pp=1,xx=x;
                f[x]=xx;
                x=0;
            }
        }
        if(!pp) pp=1,xx=x;
        f[x]=xx;
    }
    for(int i=1;i<=n;i++){
        if(t[i]) continue;
    	t[i]=1;
    	int sum=a[i];
    	for(int j=i+1;j<=n;j++){
    		if(find(i)==find(j)&&!t[j]){
    			t[j]=1;
    			sum+=a[j];
			}
		}
		d[++cnt]=sum;
	}
    dp[0].t=m;dp[0].x=0;
    for(int i=1;i<=cnt;i++){
        dp[1<<(i-1)].x=1;
        dp[1<<(i-1)].t=m-d[i];
    }
    for(int k=1;k<(1<<cnt);k++){
        if(!(k&(k-1))) continue;
        dp[k].x=1e15;
        for(int i=1;i<=cnt;i++){
            if(!(k&(1<<(i-1)))) continue;
            int x=dp[k^(1<<(i-1))].x,t=dp[k^(1<<(i-1))].t;
            if(t>=d[i]) t-=d[i];
            else{
                t=max(t,m-d[i]);
                x++;
            }
            if(x<dp[k].x){
                dp[k].x=x;dp[k].t=t;
            }else if(x==dp[k].x&&t>dp[k].t){
                dp[k].x=x;dp[k].t=t;
            }
        }
    }
    cout<<(dp[(1<<cnt)-1].x);
    return 0;
}