BZOJ 2039 或 洛谷P1791 [国家集训队]人员雇佣

$Hyperlink$

https://www.luogu.org/problemnew/show/P1791

---

$Description$

有$n$个员工，雇佣第$i$个员工，需要$a_i$点代价

如果雇佣了第$i$个员工的同时雇佣了第$j$个员工，则将得到$e_{i,j}$点价值

如果不雇佣，则将花费同样的代价

求价值与代价差值的最大值

数据范围：$n\le 10^3$

---

$Solution$

一道比较明显的最小割

代价与汇点连，表示不选它将付出这么多代价

价值与源点连，表示不选它将失去这些价值

相应$i,j$之间连两倍权值，因为不选将付出两倍的代价

---

$Code$

由于洛谷比较脑残故意卡$dinic$，所以此代码在洛谷上只能拿50，在BZOJ上可以AC

#include<queue> #include<cstdio> #include<vector> #include<cctype> #include<cstring> #define N 10010 #define M 5000010 #define LL long long using namespace std;int n,s,t; LL ans,sum; inline char nc() { static char buf[100000],*L=buf,*R=buf; return L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++; } inline LL read() { char c;int d=1;LL f=0; while(c=nc(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48; while(c=nc(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } struct node{int next,to;LL w;}e[M]; int l[N],tot=-1,d[N],used[N]; inline void add(int u,int v,LL w) { e[++tot]=(node){l[u],v,w};l[u]=tot; e[++tot]=(node){l[v],u,0};l[v]=tot; return; } inline bool bfs() { memset(d,0,sizeof(d)); queue<int>q;d[s]=1;q.push(s); while(q.size()) { int x=q.front();q.pop(); for(int i=l[x];~i;i=e[i].next) { int y=e[i].to; if(e[i].w&&!d[y]) { d[y]=d[x]+1; q.push(y); } } } return d[t]>0; } inline LL dfs(int x,LL flow) { if(x==t) return flow; int f=0; for(int& i=used[x];~i;i=e[i].next) { int y=e[i].to; if(d[y]==d[x]+1&&e[i].w) { f=dfs(y,min(flow,e[i].w)); if(f>0) {e[i].w-=f;e[i^1].w+=f;return f;} } } return 0; } inline LL dinic() { LL res=0,sum; while(bfs()) { for(register int i=s;i<=t;i++) used[i]=l[i]; while(sum=dfs(s,1e9)) res+=sum; } return res; } signed main() { memset(l,-1,sizeof(l)); n=read();s=0;t=n+1; for(register int i=1,a;i<=n;i++) a=read(),add(i,t,a); for(register int i=1;i<=n;i++) { sum=0; for(register int j=1,x;j<=n;j++) { x=read(); sum+=x; add(i,j,x<<1); } add(s,i,sum); ans+=sum; } printf("%lld",ans-dinic()); }