题目链接
luogu P1361 小M的作物
题解
源汇点为A,B 向种子连边,容量为价值,每个种子能与A或B联通,考虑最小割 用建边的总流量减去最小割就是答案 相同利益的时候新建节点,由额外利益构成群体向新建节点连边容量INF,新建节点向对应(源\汇)连对应额外利益的边 开始只新开了一个节点连了个双向边orz
代码
// luogu-judger-enable-o2
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::queue;
using std::min;
#define INF 0x7fffffff
const int maxn = 770000;
inline int read() {
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
return x;
}
int n,S,T,sum,A[maxn],B[maxn];
struct node{
int v,flow,next;
}edge[maxn];int head[maxn],num=1;
inline void add_edge(int u,int v,int flow) {
edge[++num].v=v;edge[num].flow=flow,edge[num].next=head[u];head[u]=num;
edge[++num].v=u;edge[num].flow=0;edge[num].next=head[v];head[v]=num;
}
int cur[maxn],lev[maxn];
bool spfa() {
memset(lev,-1,sizeof lev);
memcpy(cur,head,sizeof head);
queue<int>que;
que.push(S);lev[S]=0;
while(!que.empty()) {
int u=que.front();que.pop();
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].v;
if(edge[i].flow>0&&lev[v]<0) {
lev[v]=lev[u]+1;que.push(v);
}
}
}
if(lev[T]!=-1)return true;
else return false;
}
int dfs(int now,int flow) {
if(now==T)return flow;
int rest=0,delta;
for(int &i=cur[now];i;i=edge[i].next) {
int v=edge[i].v;
if(lev[v]==lev[now]+1&&edge[i].flow>0) {
delta=dfs(v,min(flow-rest,edge[i].flow));
if(delta) {
edge[i].flow-=delta;
edge[i^1].flow+=delta;
rest+=delta;if(rest==flow)break;
}
}
}
if(rest==flow)lev[now]=-1;
return rest;
}
int ans=0;
void dinic() {
while(spfa())
ans-=dfs(S,INF);
}
int main() {
n=read();
S=0,T=n+1;
for(int a,i=1;i<=n;++i)
add_edge(S,i,A[i]=read()),ans+=A[i];
for(int a,i=1;i<=n;++i)
add_edge(i,T,B[i]=read()),ans+=B[i];
int m=read();
for(int k,c1,c2,i=1;i<=m;++i) {
k=read();c1=read(),c2=read();
for(int a,j=1;j<=k;++j)
add_edge(a=read(),T+i+m,INF),add_edge(T+i,a,INF);
add_edge(S,T+i,c1),add_edge(T+i+m,T,c2);
ans+=c1+c2;
}
dinic();
printf("%d\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/8429965.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
