考场上压根没想到网络流,感觉这题是做过的网络流里算质量比较高的了。
首先我们肯定是想直接贪心,但是发现怎么贪心都没办法,而且数据范围非常小,一般数据范围非常小,且贪心不了但又只能贪心的题就用网络流实现。
考虑如何建模,首先我们发现权值有正有负,考虑最大权闭合子图,正权值连汇点,负权值连源点。
正权值连接汇点边权为他的成就值。然后再连向他需要的能力,边权无限大。
对于每个能力,考虑拆点,变成 \(5\) 个点,然后因为最大权闭合子图求的是最小割,所以每个点到源点的流量应该是他的花费,所以倒着链,\(5\to 4,4\to 3,3\to 2,2\to 1\) ,然后边权为 \(3c_i,2c_i,1c_i,0c_i\) ,然后 \(S\to 5\) 连一条边,边权为 \(4c_i\) ,然后这题就做完了。
启示:
对于贪心题而言,如果贪心不知道如何去贪心,且数据范围较小,往往要往网络流方向想一想。
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL inf=1e9,MAXN=1e4+10,N=60;
int n,m,S,T;
int a[MAXN],c[MAXN];
int l[N][N];
struct EDGE {
int f,t,c;
}que[(MAXN<<1)];
int h[MAXN],cnt=1;
void add(int f,int t,int c) {
que[++cnt]=(EDGE){h[f],t,c};
h[f]=cnt;
}
void adline(int f,int t,int c) {
add(f,t,c);
add(t,f,0);
}
int dis[MAXN],cur[MAXN];
bool bfs() {
for(int i=1;i<=T;++i) {
dis[i]=-2;
cur[i]=h[i];
}
queue<int> q;
q.push(S);
dis[S]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=h[u];i;i=que[i].f) {
int t=que[i].t;
if(!que[i].c||dis[t]!=-2) continue;
dis[t]=dis[u]+1;
q.push(t);
if(t==T) return true;
}
}
return false;
}
LL dinic(int u,LL flow) {
if(u==T) return flow;
LL res=0;
for(int i=cur[u];i&&flow;i=que[cur[u]].f) {
cur[u]=i;
int t=que[i].t;
if(!que[i].c||dis[u]+1!=dis[t]) continue;
LL k=dinic(t,min(flow,(LL)que[i].c));
if(!k) dis[t]=-2;
res+=k; flow-=k;
que[i].c-=k; que[i^1].c+=k;
}
return res;
}
int main () {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%d",&c[i]);
}
for(int i=1;i<=m;++i) {
scanf("%d",&a[i]);
}
for(int i=1;i<=m;++i) {
for(int j=1;j<=n;++j) {
scanf("%d",&l[i][j]);
}
}
S=5*n+m+1;
T=5*n+m+2;
for(int i=1;i<=n;++i) {
adline(S,i+4*n,4*c[i]);
for(int j=5;j>=2;--j) {
adline(i+(j-1)*n,i+(j-2)*n,(j-2)*c[i]);
}
}
LL ans=0;
for(int i=1;i<=m;++i) {
ans+=a[i];
adline(5*n+i,T,a[i]);
for(int j=1;j<=n;++j) {
adline(j+(l[i][j]-1)*n,5*n+i,inf);
}
}
while(bfs()) ans-=dinic(S,inf);
printf("%lld\n",ans);
return 0;
}