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

lzh0220 · 2025-03-14 18:16:51 · 题解

思路

感觉比较像 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} 的边。

见图跑网络流即可。

建图部分：

//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;
}