P3701 主主树 | Mao新求助主席树(bushi
  • 板块学术版
  • 楼主PCCP
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/4/7 22:52
  • 上次更新2023/10/23 19:08:08
查看原帖
P3701 主主树 | Mao新求助主席树(bushi
310773
PCCP楼主2023/4/7 22:52

求助,萌新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));
} 
2023/4/7 22:52
加载中...