洛谷P1361 小M的作物
思路：
这是一个两者取一的模型，将点集一分为二。 最小割在数值上等同于最大流。割去权值和最小的边，使图分成两部分，割下来的边权值和为最小割。 对于此题，先不考虑种在一起的情况。对于种在
A
,
B
A,B
A,B两地分别能获得的
a
i
,
b
i
a_i,b_i
ai,bi的收益，我们可以考虑从
S
S
S向
i
i
i建一条边，权值为
a
i
a_i
ai;从
i
i
i向
T
T
T建一条边，权值为
b
i
b_i
bi。 那么种在一起获得额外收益可以建虚点
j
1
,
j
2
j_1,j_2
j1,j2，由
S
S
S向
j
1
j_1
j1连边，权值为
c
1
i
c_{1i}
c1i,
j
1
j_1
j1向集合中其他点连边，权值为
i
n
f
inf
inf；对于
c
2
i
c_{2i}
c2i同理
j
2
j_2
j2连向
T
T
T。权值为
i
n
f
inf
inf意味着不可割，我们只需要考虑
S
−
>
j
1
,
j
2
−
>
T
S->j_1,j_2->T
S−>j1,j2−>T会割哪条（全部）就行了。 这题数据比较大，要采用优化的dinic才行。
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
const int N
=1e4+10;
const int mod
=1e9+7;
const int maxn
=0x3f3f3f3f;
const int minn
=0xc0c0c0c0;
const int inf
=99999999;
using namespace std
;
struct edge
{
int u
,v
,w
;
}maze
[4000000];
int len
=1,head
[N
]={0},dep
[N
];
void add(int u
,int v
,int w
)
{
maze
[++len
]={head
[u
],v
,w
};
head
[u
]=len
;
}
int bfs(int s
,int t
)
{
queue
<int> q
;
cl(dep
,0);
dep
[s
]=1;
q
.push(s
);
while(!q
.empty())
{
int u
=q
.front(),i
;
q
.pop();
for(i
=head
[u
];i
;i
=maze
[i
].u
)
{
int v
=maze
[i
].v
,w
=maze
[i
].w
;
if(w
&& !dep
[v
])
{
dep
[v
]=dep
[u
]+1;
q
.push(v
);
}
}
}
return dep
[t
];
}
int dfs(int u
,int f
,int t
)
{
int ans
=0,i
;
if(u
==t
)
return f
;
for(i
=head
[u
];i
&& f
;i
=maze
[i
].u
)
{
int v
=maze
[i
].v
,w
=maze
[i
].w
;
if(dep
[u
]+1==dep
[v
] && w
)
{
int sum
=dfs(v
,min(f
,w
),t
);
maze
[i
].w
-=sum
;
maze
[i
^1].w
+=sum
;
f
-=sum
;
ans
+=sum
;
}
}
if(!ans
)
dep
[u
]=-2;
return ans
;
}
int dinic(int s
,int t
)
{
int ans
=0;
while(bfs(s
,t
))
ans
+=dfs(s
,maxn
,t
);
return ans
;
}
signed main()
{
int n
,m
,i
,x
,s
,t
,sum
=0;
scanf("%d",&n
);
s
=n
+1;
t
=s
+1;
for(i
=1;i
<=n
;i
++)
{
scanf("%d",&x
);
sum
+=x
;
add(s
,i
,x
);
add(i
,s
,0);
}
for(i
=1;i
<=n
;i
++)
{
scanf("%d",&x
);
sum
+=x
;
add(i
,t
,x
);
add(t
,i
,0);
}
scanf("%d",&m
);
for(i
=1;i
<=m
;i
++)
{
int ca
,j
,a
,b
;
scanf("%d%d%d",&ca
,&a
,&b
);
sum
+=a
+b
;
add(s
,n
+2+i
,a
);
add(n
+2+i
,s
,0);
add(n
+2+i
+m
,t
,b
);
add(t
,n
+2+i
+m
,0);
for(j
=1;j
<=ca
;j
++)
{
scanf("%d",&x
);
add(n
+2+i
,x
,maxn
);
add(x
,n
+2+i
,0);
add(x
,n
+2+i
+m
,maxn
);
add(n
+2+i
+m
,x
,0);
}
}
int flow
=dinic(s
,t
);
int res
=sum
-flow
;
printf("%d\n",res
);
return 0;
}
