求助,为啥这爆零了
查看原帖
求助,为啥这爆零了
334351
zstu_yjy楼主2021/5/29 22:24
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N 100010
#define mod 1000000007
#define itn ll
#define debug(x) cout << #x << " is " << x << endl;
#define FOR(i,n) for(ll i=1;i<=n;i++)
#define rep(i) for(ll i=head[u];i;i=t[i].Next)
using namespace std;
ll n,k=0,S,F,T,dis[2000],now[2000],head[2000];
struct node{
	ll u,v,Next,flo;
}t[4*N];
void add(ll u,ll v,ll l){
	t[k].u=u;
	t[k].v=v;
	t[k].flo=l;
	t[k].Next=head[u];
	head[u]=k;
	k++;
}
bool bfs(ll st,ll fi){
	queue<ll>q;
	for(ll i=0;i<=2*n+10;i++)now[i]=head[i];
	for(ll i=0;i<=n*2+10;i++)dis[i]=-1;
	q.push(st);
	dis[st]=0;
	now[st]=head[st];
	while(!q.empty()){
		ll u=q.front();
		q.pop();
		for(ll i=head[u];i!=-1;i=t[i].Next){//cout<<t[i].Next<<' ';
			ll v=t[i].v;//if(v==1)cout<<"*";
			if(dis[v]==-1&&t[i].flo){
				dis[v]=dis[u]+1;
				now[v]=head[v];
				q.push(v);
				if(v==fi)return 1;
			}
		}
	}
	return 0;
}
ll dfs(ll u,ll fi,ll flo){
	ll delta=flo;
	if(u==fi)return flo;
	for(ll i=now[u];i!=-1&&delta;i=t[i].Next){//debug(i)
		ll v=t[i].v;
		now[u]=i;
		if((dis[v]==dis[u]+1)&&t[i].flo>0){
			ll d=dfs(v,fi,min(delta,t[i].flo));
			if(d==0)dis[v]=INF;
			delta-=d;
			t[i].flo-=d;t[i^1].flo+=d;	
		}
	}
	return flo-delta;
}
ll dinic(ll st,ll fi){
	ll cnt=0;
	while(bfs(st,fi)){
		cnt+=dfs(st,fi,INF);
		//debug(cnt)
	}
	return cnt;
}
ll a[800],b[800],c[800],dp[800];
pair<ll,ll>l[800];
void solve(){
	vector<ll>q;
	ll cnt=dinic(S,F);
	cout<<cnt<<' ';
	FOR(i,n){
		l[i].first=c[i];
		l[i].second=i;
	}
	sort(l+1,l+1+n);
	 
	FOR(i,n){
		ll u=l[i].second*2-1,v=u+1;
		if(bfs(u,v)==0){//退流 
			q.push_back(l[i].second);
			cnt=dinic(F,v);
			cnt=dinic(u,S);
			for(ll i=head[u];i!=-1;i=t[i].Next){//把边的影响消除 
				ll vi=t[i].v;
				if(vi!=v)continue;
				t[i].flo=t[i^1].flo=0;
			}
		}
	}
	cout<<q.size()<<endl;
	sort(q.begin(),q.end());
	for(ll i=0;i<q.size();i++)cout<<q[i]<<' ';
	cout<<endl;
	/**/
}
void build(){
	ll s=0;
	scanf("%d",&n);S=0,F=2*n+1;
	for(ll i=0;i<=F;i++)head[i]=-1;
	FOR(i,n)scanf("%lld",&a[i]);
	FOR(i,n)scanf("%lld",&b[i]);
	FOR(i,n)scanf("%lld",&c[i]);
	FOR(i,n){
		for(ll j=i;j>=0;j--)if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
		s=max(s,dp[i]);
	}
	FOR(i,n){
		if(dp[i]==1){
			add(S,i*2-1,INF);
			add(2*i-1,S,0);
		}else if(dp[i]==s){
			add(i*2,F,INF);
			add(F,2*i,0);
		}//拆点建边 
		add(2*i-1,2*i,b[i]);
		add(2*i,2*i-1,0);
		
		for(ll j=1;j<=n;j++)if(a[j]<a[i]&&dp[j]+1==dp[i])add(2*j,2*i-1,INF),add(2*i-1,2*j,0);
	}
}
int main(){
	scanf("%lld",&T);
	while(T--){
		k=0;
		build();
		solve();
	}
}
2021/5/29 22:24
加载中...