NOI 2006 最大获利

\(Link\)

题意略。

对于每个用户群 \(i\)，考虑选不选它。

如果选，则中转站 \(A_i,B_i\) 必选。

然后就有最大权闭合子图的影子了。

接下来建一个二分图，左边点为用户群 \(X\)，右边为中转站 \(Y\)。

对于每个 \(X_i\)，其点权为 \(C_i\)。

对于每个 \(Y_i\)，其点权为 \(-P_i\)。

然后对于每个用户群 \(X_i\)，让它对 \(Y_{A_i},Y_{B_i}\) 连一条边。

求这张图的最大权闭合子图就行了。

\(Code:\)

// Problem: P4174 [NOI2006] 最大获利
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4174
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 

#include
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
#define wt int tt=d;while(tt--)
#define py puts("Yes")
#define pn puts("No")
#define fe(i,e) for(int i=0;i
inline ll rd() {
	ll x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	return x*f;
}
#define d rd()
#define pb push_back
struct edge{ll v,w,nx;}e[1000010];
ll hd[200010],cnt=1;
void add(ll u,ll v,ll w){e[++cnt]=(edge){v,w,hd[u]};hd[u]=cnt;}
ll qp(ll a,ll b,ll p){
	ll ans=1;while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;b>>=1;
	}return ans;
}ll s,t,n,m;
bool vis[200010];
ll de[200010],ans;
bool to;
ll cur[200010];
bool Dinic_bfs(){
	queueq;
	f(i,1,t)cur[i]=hd[i],de[i]=0x3f3f3f3f,vis[i]=0;de[s]=0;
	ll ppp=de[t];
	q.push(s);vis[s]=1;while(!q.empty()){
		ll u=q.front();q.pop();vis[u]=0;
		for(int i=hd[u];i;i=e[i].nx){
			ll v=e[i].v;
			if(de[v]>de[u]+1&&e[i].w){
				de[v]=de[u]+1;if(!vis[v])q.push(v),vis[v]=1;
			}
		}
	}if(de[t]==ppp)return 0;
	return 1;
}ll Dinic_dfs(ll u,ll flo){
	if(u==t){
		to=1;ans+=flo;
		return flo;
	}ll used=0;
	ll now=0;
	for(int i=cur[u];i;i=e[i].nx){
		ll v=e[i].v;cur[u]=i; 
		if(e[i].w&&de[v]==de[u]+1){
			if(now=Dinic_dfs(v,min(flo-used,e[i].w))){
				used+=now;e[i].w-=now;e[i^1].w+=now;
				if(used==flo)break;
			}
		}
	}return used;
}void Dinic(){while(Dinic_bfs())Dinic_dfs(s,1000000000000);}
ll Ans;
int main(){
	n=d,m=d;s=n+m+1,t=n+m+2;
	f(i,1,n){ll x=d;add(m+i,t,x),add(t,m+i,0);}
	f(i,1,m){
		ll u=d,v=d,w=d;
		add(i,u+m,1000000000000),add(u+m,i,0);
		add(i,v+m,1000000000000),add(v+m,i,0);
		add(s,i,w),add(i,s,0);Ans+=w;
	}Dinic();printf("%lld\n",Ans-ans);
	return 0;
}

ps:CF1082G是双倍经验。