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

~~竟然没有这题的题解，水一发qwq~~ ## 最小割模型 #### 1.题意: 　a.选择每个人有一个代价$A_i$； 　b.如果有两个人同时选择就可以获得收益$E_{i,j}$ 　c.如果一个人选择另一个不选会产生代价$E_{i,j}$ #### 2.解法 　　a,b两条就是典型的最小割模型，从$S$向每个人连边流量为这人可以带来的收益$\Sigma_{j=1}^{n} E_{i,j}$，用$ans$记录总收益，再从人向$T$连边表示代价$A_i$，用$ans-minc$（这样如果割掉人到$T$的边代表选这个人并支付代价，如果割掉$S$到人的边代表舍弃收益，不支付代价）得到的就是最大的收益 　　考虑c条件，那么我们对于每对$i,j$都再新建一条从$i$到$j$的边，流量为$E_{i,j}<<1$这样如果选一个不选另一个的话这条边就会断掉（造成代价）,c条件就能满足了 　　最小割可以转化为最大流，我用的$dinic$极限数据$942ms$~~有点慌~~ 　　~~还有就是千万别忘开long long~~ #### 3.代码 ```cpp #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<algorithm> using namespace std; inline long long read(){ long long ans=0,fh=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') fh=-1; ch=getchar(); } while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar(); return ans*fh; } const int maxn=1e4,maxm=5e6,inf=0x7fffffff; int n,m,a,b,c,cc[maxn],cur[maxn],head[maxn],nex[maxm],v[maxm],s,t; int num=1; long long ans,siz[maxn],fee,w[maxm]; queue<int>q; int bh(int x,int y){return n+(x-1)*n+y;} void add(int x,int y,long long z){ v[++num]=y; w[num]=z; nex[num]=head[x]; head[x]=num; v[++num]=x; w[num]=0; nex[num]=head[y]; head[y]=num; } bool bfs(){ memset(cc,0,sizeof(cc)); cc[s]=1; q.push(s); while(!q.empty()){ int now=q.front(); q.pop(); for(int i=head[now];i;i=nex[i]) if(w[i]&&!cc[v[i]]) cc[v[i]]=cc[now]+1,q.push(v[i]); } return cc[t]; } long long dfs(int x,long long ll){ if(x==t) return ll; for(int &i=cur[x];i;i=nex[i]) if(w[i]&&cc[v[i]]==cc[x]+1){ int pp=dfs(v[i],ll>w[i]?w[i]:ll); if(pp){ w[i]-=pp; w[i^1]+=pp; return pp; } } return 0; } void dinic(){ long long maxl=0,ll; while(bfs()){ memcpy(cur,head,sizeof(cur)); while(ll=dfs(s,inf)) maxl+=ll; } printf("%d\n",ans-maxl); } int main(){ n=read();s=0;t=n+1; for(int i=1;i<=n;i++) a=read(),add(i,t,a); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ fee=read(); siz[i]+=fee; add(i,j,fee*2); } add(s,i,siz[i]); ans+=siz[i]; } dinic(); return 0; } ```