小 Z 最近为一款游戏设计了一个集合石系统。这个系统能有效的解决玩家们找不到人组队下副本的问题。
这个游戏中有四个职业:战士,法师,猎人,牧师,而一个完整的小队必然是四个职业各有一位。
玩家有强有弱,每个玩家的实力用证书表示。
但是小 Z 发现,有些玩家之间是处于仇敌关系的,这样关系的玩家如果分配在一起,会导致这个小队内部出现内讧,影响玩家的游戏体验。于是小 Z 给集合石加了一个新系统,如果你有不想匹配到的玩家,可以设置他为黑名单,这样你们两人就不会被匹配在一起了。
每个小队的实力是成员实力之和。小 Z 想要知道一个小队实力的最小值是多少。
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=150001;
int n1,n2,n3,n4,m1,m2,m3;
set<int> s1[maxn],s2[maxn],s3[maxn];
struct node{
int id,val;
friend bool operator <(node x,node y){
return x.val<y.val;
}
}a[maxn],b[maxn],c[maxn],d[maxn];
int main(){
cin>>n1>>n2>>n3>>n4;
for(int i=1;i<=n1;i++){
cin>>a[i].val;
a[i].id=i;
}
for(int i=1;i<=n2;i++){
cin>>b[i].val;
b[i].id=i;
}
for(int i=1;i<=n3;i++){
cin>>c[i].val;
c[i].id=i;
}
for(int i=1;i<=n4;i++){
cin>>d[i].val;
d[i].id=i;
}
cin>>m1;
while(m1--){
int x,y;
cin>>x>>y;
s1[y].insert(x);
}
cin>>m2;
while(m2--){
int x,y;
cin>>x>>y;
s2[y].insert(x);
}
cin>>m3;
while(m3--){
int x,y;
cin>>x>>y;
s3[y].insert(x);
}
sort(a+1,a+1+n1);
for(int i=1;i<=n2;i++){
bool flag=false;
for(int j=1;j<=n1;j++){
if(s1[i].find(a[j].id)==s1[i].end()){
b[i].val=min(b[i].val+a[i].val,inf);
flag=true;
break;
}
}
if(!flag)b[i].val=inf;
}
sort(b+1,b+1+n2);
for(int i=1;i<=n3;i++){
bool flag=false;
for(int j=1;j<=n2;j++){
if(s2[i].find(b[j].id)==s2[i].end()){
c[i].val=min(c[i].val+b[i].val,inf);
flag=true;
break;
}
}
if(!flag)c[i].val=inf;
}
sort(c+1,c+1+n3);
for(int i=1;i<=n4;i++){
bool flag=false;
for(int j=1;j<=n3;j++){
if(s3[i].find(c[j].id)==s3[i].end()){
d[i].val=min(d[i].val+c[i].val,inf);
flag=true;
break;
}
}
if(!flag)d[i].val=inf;
}
int ans=inf;
for(int i=1;i<=n4;i++)ans=min(ans,d[i].val);
if(ans==inf)cout<<-1;
else cout<<ans;
return 0;
}
望有一位大佬能帮我指出我的错误!