求助,萌新too young too simple,90pts,无法通过第五个测试点,原题讨论区虽然有错第五个点的,但是底下全是谈笑风生的。
回归正题,求助谷内各位大佬帮帮蒟蒻看看到底哪里有问题,蒟蒻会关注您的。
测试点:
23 603
J HK E E J E HK YYY YYY E HK HK YYY J J YYY YYY J W YYY W HK W
W J YYY HK E W J W E YYY HK HK HK E YYY J W W W J W HK W
38 43 6 23 32 8 15 36 7 17 9 43 22 25 43 42 6 32 45 34 46 42 44
27 21 38 28 26 23 15 42 43 48 11 35 4 32 9 21 39 6 47 6 39 46 36
标准答案:
204
蒟蒻的答案:
203
原码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<sstream>
#include<queue>
using namespace std;
const int N=310;
const int M=2e4+10;
const int INF=0x3f3f3f3f;
int n,m,s,t,ans;
int he[N],ne[M<<1],to[M<<1],w[M<<1],tot=1;
string a[N],b[N];
int aa[N],bb[N];
vector<int> kind[6];
void addedge(int x,int y,int z){
to[++tot]=y;
ne[tot]=he[x];
he[x]=tot;
w[tot]=z;
}
int d[N],cur[N];
queue<int> q;
bool bfs(){
while(q.size()){
q.pop();
}
memset(d,-1,sizeof d);
d[s]=0;
q.push(s);
cur[s]=he[s];
while(q.size()){
int tt=q.front();
q.pop();
for(int i=he[tt];i!=-1;i=ne[i]){
int v=to[i];
if(d[v]==-1&&w[i]){
d[v]=d[tt]+1;
cur[v]=he[v];
if(v==t){
return true;
}
q.push(v);
}
}
}
return false;
}
int find(int x,int lim){
if(x==t){
return lim;
}
int flow=0;
for(int i=cur[x];i!=-1&&flow<lim;i=ne[i]){
int v=to[i];
cur[x]=i;
if(d[v]==d[x]+1&&w[i]){
int tt=find(v,min(w[i],lim-flow));
if(!tt){
d[v]=-1;
}
w[i]-=tt;
w[i^1]+=tt;
flow+=tt;
}
}
return flow;
}
void dinic(){
ans=0;
int flow;
while(bfs()){
while(flow=find(s,INF)){
ans+=flow;
}
}
}
int get(string x){
if(x=="J"){
return 1;
}
if(x=="HK"){
return 2;
}
if(x=="W"){
return 3;
}
if(x=="YYY"){
return 4;
}
return 5;
}
int main(){
scanf("%d%d",&n,&m);
s=0,t=2*n+1;
memset(he,-1,sizeof he);
int y;
for(int i=1;i<=n;i++){
cin>>a[i];
int k=get(a[i]);
kind[k].push_back(i);
if(k==4){
y++;
}
}
for(int i=1;i<=n;i++){
cin>>b[i];
int k=get(b[i]);
vector<int>::iterator it;
if(k==1){
for(it=kind[4].begin();it!=kind[4].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
for(it=kind[5].begin();it!=kind[5].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
}
else if(k==2){
for(it=kind[1].begin();it!=kind[1].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
for(it=kind[4].begin();it!=kind[4].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
}
else if(k==3){
for(it=kind[1].begin();it!=kind[1].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
for(it=kind[2].begin();it!=kind[2].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
}
else if(k==4){
for(it=kind[3].begin();it!=kind[3].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
for(it=kind[5].begin();it!=kind[5].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
}
else{
for(it=kind[2].begin();it!=kind[2].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
for(it=kind[3].begin();it!=kind[3].end();it++){
addedge(*it,i+n,1);
addedge(i+n,*it,0);
// cout<<*it<<" - "<<i+n<<endl;
}
}
}
for(int i=1;i<=n;i++){
scanf("%d",&aa[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&bb[i]);
addedge(i+n,t,bb[i]);
addedge(t,i+n,0);
// cout<<i+n<<" - "<<t<<" : "<<bb[i]<<endl;
}
for(int i=1;i<=5;i++){
vector<int>::iterator it;
for(it=kind[i].begin();it!=kind[i].end();it++){
if(i==1){
addedge(s,*it,y+aa[*it]);
addedge(*it,s,0);
// cout<<s<<" - "<<*it<<" : "<<y+aa[*it]<<endl;
}
else{
addedge(s,*it,aa[*it]);
addedge(*it,s,0);
// cout<<s<<" - "<<*it<<" : "<<aa[*it]<<endl;
}
}
}
// cout<<"fuck"<<endl;
dinic();
printf("%d",min(ans,m));
}