P1791 [国家集训队] 人员雇佣题解

思路

感觉比较像 P4313。

先不考虑同时选两个人的情况，则源点代表自己要选哪些，汇点表示对方选哪些，则将源点向每个

i

连一条价值为

A_i

的边，将每个

i

向汇点连一条价值为

\sum_{j=1}^nE_{i,j}

的边。

考虑同时选两个人的情况，此时对于

i

和

j

，一定形如

i

连

s

且

j

连

t

。此时这么选的代价为

2E_{i,j}

，则在

i

，

j

之间连价值为

2E_{i,j}

的边。

见图跑网络流即可。

建图部分：

CPP

//vector 建边
int n=read(),num=0;
s=0;t=n+1;
for(int i=1;i<=n;i++){
	int val=read();
	v[s].pb(mp(i,++tot));tag[tot]=val;
	v[i].pb(mp(s,++tot));tag[tot]=0;
}
for(int i=1;i<=n;i++){
	int sum=0;
	for(int j=1;j<=n;j++){
		int x=read();sum+=x;
		if(x){
			v[i].pb(mp(j,++tot));tag[tot]=x*2;
			v[j].pb(mp(i,++tot));tag[tot]=0;
		}
	}
	v[i].pb(mp(t,++tot));tag[tot]=sum;
	v[t].pb(mp(i,++tot));tag[tot]=0;num+=sum;
}

P1791 [国家集训队] 人员雇佣题解

文章操作

思路

相关推荐

评论

P1791 [国家集训队] 人员雇佣题解