显然我没有那种艺术细胞（悲
$\ $
最大流
dinic+当前弧优化
$\ $
- P1231 教辅的组成
对于书本的点数，要控制经过点的流量
因此拆点
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+10,M=1e5+10,inf=1e9;
int n1,n2,n3,m1,m2,s,t;
int cur[N],vis[N],dis[N];
int ver[M<<1],head[N],tot=1,Next[M<<1],edge[M<<1];
void add(int x,int y,int z){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
edge[tot]=z;
}
bool bfs(){
for(int i=1;i<=t;i++)dis[i]=0,cur[i]=head[i];
queue<int>q;
dis[s]=1;
q.push(s);
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!dis[y]&&edge[i]){
dis[y]=dis[x]+1;
q.push(y);
}
}
}
return (dis[t]!=0);
}
int dinic(int x,int limit){
if(x==t||!limit)return limit;
int flow=0,f;
for(int &i=cur[x];i;i=Next[i]){
int y=ver[i];
if(dis[y]==dis[x]+1&&(f=dinic(y,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^1]+=f;
if(!limit)break;
}
}
return flow;
}
int main()
{
scanf("%d%d%d",&n1,&n2,&n3);
s=n1+n1+n2+n3+1,t=n1+n1+n2+n3+2;
scanf("%d",&m1);
for(int i=1,x,y;i<=m1;i++){
scanf("%d%d",&x,&y);
add(x+n2,y,0),add(y,x+n2,1);
}
scanf("%d",&m2);
for(int i=1,x,y;i<=m2;i++){
scanf("%d%d",&x,&y);
add(x+n2+n1,y+n1+n2+n1,1),add(y+n1+n2+n1,x+n2+n1,0);
}
for(int i=1;i<=n1;i++){
add(i+n2,i+n2+n1,1),add(i+n2+n1,i+n2,0);
}
for(int i=1;i<=n2;i++){
add(s,i,1),add(i,s,0);
}
for(int i=1;i<=n3;i++){
add(i+n1+n2+n1,t,1),add(t,i+n1+n2+n1,0);
}
int flow=0;
while(bfs()){
flow+=dinic(s,inf);
}
printf("%d\n",flow);
return 0;
}
$\ $
- P1345 [USACO5.4] 奶牛的电信Telecowmunication
拆成出边点和入边点，控制点的流量为 \(1\)
路径会通过相连的信息建立联系，路径上的每个点都先走到入点，经过流量为 \(1\) 的控制边，再走到出点，保证了流量合法
#include<bits/stdc++.h>
using namespace std;
const int N=410,M=2010,inf=1e9;
int n,m,c1,c2;
int ver[M<<1],head[N],tot=1,Next[M<<1],edge[M<<1];
int cur[N],d[N];
void add(int x,int y,int z){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
edge[tot]=z;
}
bool bfs(){
for(int i=1;i<=n*2;i++)cur[i]=head[i],d[i]=0;
queue<int>q;
d[c1]=1;
q.push(c1);
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!d[y]&&edge[i]){
d[y]=d[x]+1;
q.push(y);
}
}
}
return (d[c2]!=0);
}
int dinic(int x,int limit){
if(x==c2||!limit)return limit;
int flow=0,f;
for(int &i=cur[x];i;i=Next[i]){
int y=ver[i];
if(d[y]==d[x]+1&&(f=dinic(y,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^1]+=f;
if(!limit)break;
}
}
return flow;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&c1,&c2);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
add(x+n,y,inf),add(y,x+n,0);
add(y+n,x,inf),add(x,y+n,0);
}
for(int i=1;i<=n;i++){
if(i!=c1&&i!=c2)add(i,i+n,1),add(i+n,i,0);
else add(i,i+n,inf),add(i+n,i,0);
}
int flow=0;
while(bfs()){
flow+=dinic(c1,inf);
}
printf("%d\n",flow);
return 0;
}
$\ $
最小割
最后的网络中，与S相连的相当于选进 \(S\) 集合，与 \(T\) 相连的则是选进 \(T\) 集合
最小割是分成两个集合的最小割边代价
$\ $
- P1361 小M的作物
把每个植物组合作为两个新点。\(S\) 向新点\(1\)连流量 \(c_{i,1}\) 的边，新点 \(2\) 向 \(T\) 连流量 \(c_{i,2}\) 的边，表示不选进这两个集合的话分别少收获多少贡献。
新点 \(1\) 向相应的作物点连不会被割掉的流量为 \(inf\) 的边，同样地，作物向新点 \(2\) 连不会被割掉的边。
如果某个组合连向 \(S\) 的边没有被割掉，那么组合中所有作物连向 \(T\) 的点都被割掉了。反之同理。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,M=3e6+10;
const ll inf=1e18;
int n,s,t,m,cnt,cur[N],d[N];
ll a[N],b[N],edge[M],sum;
int ver[M],head[N],tot=1,Next[M];
void add(int x,int y,ll z){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
edge[tot]=z;
}
bool bfs(){
for(int i=1;i<=cnt;i++)d[i]=0,cur[i]=head[i];
d[s]=1;
queue<int>q;
q.push(s);
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!d[y]&&edge[i]){
d[y]=d[x]+1;
q.push(y);
}
}
}
return (d[t]!=0);
}
ll dinic(int x,ll limit){
if(x==t||!limit)return limit;
ll flow=0,f;
for(int &i=cur[x];i;i=Next[i]){
int y=ver[i];
if(d[y]==d[x]+1&&(f=dinic(y,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^1]+=f;
if(!limit)break;
}
}
return flow;
}
int main()
{
scanf("%d",&n);
s=n+1,t=cnt=n+2;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
add(s,i,a[i]),add(i,s,0);
sum+=a[i];
}
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
add(i,t,b[i]),add(t,i,0);
sum+=b[i];
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
int k,c1,c2;
scanf("%d%d%d",&k,&c1,&c2);
sum+=c1+c2;
add(s,cnt+1,c1),add(cnt+1,s,0);
add(cnt+2,t,c2),add(t,cnt+2,0);
for(int j=1,x;j<=k;j++){
scanf("%d",&x);
add(cnt+1,x,inf),add(x,cnt+1,0);
add(x,cnt+2,inf),add(cnt+2,x,0);
}
cnt+=2;
}
ll flow=0;
while(bfs()){
flow+=dinic(s,inf);
}
printf("%lld\n",sum-flow);
return 0;
}
$\ $
- P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查
最小割连边的板子模型之一
\(S\) 投 \(0\),\(T\) 投 \(1\),每个人向自己的意愿连边，朋友之间连流量为 \(1\) 的边。
要么割意愿边，满足朋友投了同一种票；要么割朋友边，满足自己的意愿但发生冲突。
#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=2e5+10,inf=1e9;
int n,m,s,t,ans,cnt,cur[N],d[N];
int ver[M<<1],head[N],tot=1,Next[M<<1],edge[M<<1];
void add(int x,int y,int z){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
edge[tot]=z;
ver[++tot]=x;
Next[tot]=head[y];
head[y]=tot;
edge[tot]=z;
}
bool bfs(){
for(int i=1;i<=cnt;i++)cur[i]=head[i],d[i]=0;
d[s]=1;
queue<int>q;
q.push(s);
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!d[y]&&edge[i]){
d[y]=d[x]+1;
q.push(y);
}
}
}
return (d[t]!=0);
}
int dinic(int x,int limit){
if(x==t||!limit)return limit;
int flow=0,f;
for(int &i=cur[x];i;i=Next[i]){
int y=ver[i];
if(d[y]==d[x]+1&&(f=dinic(y,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^1]+=f;
if(!limit)break;
}
}
return flow;
}
int main()
{
scanf("%d%d",&n,&m);
s=n+1,t=cnt=n+2;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
if(x==1)add(i,t,1);
else add(s,i,1);
}
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y,1),add(y,x,1);
}
int flow=0;
while(bfs()){
flow+=dinic(s,inf);
}
printf("%d\n",flow);
return 0;
}
$\ $
- P2762 太空飞行计划问题
源点向实验连边，实验向对应仪器连边，仪器向汇点连边，初始统计所有实验的价值
割掉实验表示不选这场实验，割掉仪器表示付出仪器的代价完成实验
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
const ll inf=1e18;
int m,n,c[N],s,t,d[N],cur[N],p[N],a[N],cnt,vis[N];
int ver[N<<1],head[N],tot=1,Next[N<<1];
ll edge[N<<1],ans;
void add(int x,int y,ll z){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
edge[tot]=z;
ver[++tot]=x;
Next[tot]=head[y];
head[y]=tot;
edge[tot]=0;
}
bool bfs(){
for(int i=1;i<=t;i++)cur[i]=head[i],d[i]=0;
d[s]=1;
queue<int>q;
q.push(s);
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!d[y]&&edge[i]){
d[y]=d[x]+1;
q.push(y);
}
}
}
return (d[t]!=0);
}
ll dinic(int x,ll limit){
if(x==t||!limit)return limit;
ll flow=0,f;
for(int &i=cur[x];i;i=Next[i]){
int y=ver[i];
if(d[y]==d[x]+1&&(f=dinic(y,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^1]+=f;
if(!limit)break;
}
}
return flow;
}
int main()
{
scanf("%d%d",&m,&n);
s=n+m+1,t=n+m+2;
for(int i=1;i<=m;i++){
scanf("%d",&c[i]);
ans+=c[i];
add(s,i,c[i]);
char tools[10000];
memset(tools,0,sizeof tools);
cin.getline(tools,10000);
int ulen=0,tool;
while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
{//tool是该实验所需仪器的其中一个
//这一行，你可以将读进来的编号进行储存、处理，如连边。
add(i,m+tool,inf);
if (tool==0)
ulen++;
else {
while (tool) {
tool/=10;
ulen++;
}
}
ulen++;
}
}
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
add(i+m,t,p[i]);
// printf("i:%d p:%d\n",i,p[i]);
}
ll flow=0;
while(bfs()){
flow+=dinic(s,inf);
}
for(int i=1;i<=m;i++)if(d[i])printf("%d ",i);
printf("\n");
for(int i=1;i<=n;i++)if(d[m+i])printf("%d ",i);
printf("\n%lld\n",ans-flow);
return 0;
}
$\ $
费用流
用SPFA代替bfs的部分，\(d[y]=d[x]+1\)改成\(d[y]=(d[x]+cost[i])_{min}\)
因为有负边权，所以在 \(dinic\) 里也要注意用 \(vis\) 来标记该点是否在栈中
$\ $
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=5e4+10,inf=2147483647;
int n,m,s,t,ans,cur[N],d[N],vis[N];
int ver[M<<1],head[N],tot=1,Next[M<<1],edge[M<<1],cost[M<<1];
void add(int x,int y,int z,int c){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
edge[tot]=z;
cost[tot]=c;
ver[++tot]=x;
Next[tot]=head[y];
head[y]=tot;
edge[tot]=0;
cost[tot]=-c;
}
bool bfs(){
for(int i=1;i<=n;i++)cur[i]=head[i],d[i]=inf,vis[i]=0;
queue<int>q;
d[s]=1;
q.push(s);
while(q.size()){
int x=q.front();
q.pop();
vis[x]=0;
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(d[y]>d[x]+cost[i]&&edge[i]){
d[y]=d[x]+cost[i];
if(!vis[y]){
vis[y]=1;
q.push(y);
}
}
}
}
return (d[t]!=inf);
}
int dinic(int x,int limit){
if(x==t||!limit)return limit;
int flow=0,f;
vis[x]=1;
for(int &i=cur[x];i;i=Next[i]){
int y=ver[i];
if(!vis[y]&&d[y]==d[x]+cost[i]&&(f=dinic(y,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^1]+=f;
ans+=f*cost[i];
if(!limit)break;
}
}
vis[x]=0;
return flow;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1,x,y,z,c;i<=m;i++){
scanf("%d%d%d%d",&x,&y,&z,&c);
add(x,y,z,c);
}
int flow=0;
while(bfs()){
flow+=dinic(s,inf);
}
printf("%d %d\n",flow,ans);
return 0;
}
$\ $
继续学习ing……