专门做日租房的网站/濮阳市网站建设

写在前面

分析一下各位过不了的原因

1. 数组开小了！数组开小了！数组开小了！
2. 没写当前弧优化！没写当前弧优化！没写当前弧优化！
3. 当前弧优化写错了！当前弧优化写错了！当前弧优化写错了！
4. 没打快读！没打快读！没打快读！

我改这些真心改到疯掉


当前弧真的恶心。。。

---

$Description$

有$n$件任务，$m$个机器人

使用某个机器人可以解决某些任务，使用的前提是购买或者租借，这都要付出一定代价，租借的话只能用其解决一类问题

求最终最小花费

数据范围：$n,m\le 1200$

---

$Solution$

明显就是这道题的弱化版本嘛

这就是一道比较经典的最大权闭合子图问题，答案就是$\sum a_i-maxflow$嘛

考虑建图

$(S,i,a_i)$，表示如果不做$i$号任务将失去$a_i$点价值
$(i+n,t,b_i)$，表示购买$i+n$号机器将付出$b_i$点代价
$(i,j+n,c_i)$，表示租用$j$号机器完成$i$号任务（做了这个任务，却没选这个机器【其实就是租借】）

接下来跑最大流求解最小割即可

---

$Code$

当前弧优化首打

#include<queue>
#include<cstdio>
#include<vector>
#include<cctype>
#include<cstring>
#define N 2505
#define M 3000005
using namespace std;int n,s,t,ans,m;
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 long long read()
{char c;int d=1;long long 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,w;}e[M];
int l[N],tot=-1,d[N],used[N];
inline void add(int u,int v,int 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 int dfs(int x,int 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 int dinic()
{int 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()
{n=read();m=read();s=0;t=n+m+1;memset(l,255,sizeof(l));for(register int i=1,w;i<=n;i++)	{w=read();add(s,i,w);ans+=w;for(int num=read(),d;num--;){d=read();w=read();add(i,d+n,w);}}for(register int i=1,w;i<=m;i++) w=read(),add(i+n,t,w);printf("%d",ans-dinic());
}