洛谷 - P2762 - 太空飞行计划问题 - 最小割

https://www.luogu.org/problemnew/solution/P2762

最小割对应的点,在最后一次更新中dinic的bfs会把他的dep重置掉。所以可以根据这个性质复原最小割。

#include<bits/stdc++.h>
using namespace std;
#define ll long long /* dinic begin */ const int MAXN=;
const int MAXM=;
const int INF=0x3f3f3f3f;
struct Edge{
int to,next,cap,flow;
}edge[MAXM]; int tol;
int head[MAXN]; void init(){
tol=;
memset(head,-,sizeof(head));
} void addedge(int u,int v,int w){
edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=;
edge[tol].next=head[u];head[u]=tol++;
edge[tol].to=u;edge[tol].cap=;edge[tol].flow=;
edge[tol].next=head[v];head[v]=tol++;
} int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
bool bfs(int s,int t,int n){
int front=,tail=;
memset(dep,-,sizeof(dep[])*(n+));
dep[s]=;
Q[tail++]=s;
while(front<tail){
int u=Q[front++];
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(edge[i].cap>edge[i].flow&&dep[v]==-){
dep[v]=dep[u]+;
if(v==t)
return true;
Q[tail++]=v;
}
}
}
return false;
} int dinic(int s,int t,int n){
//n最后一个节点的编号的下一个编号
int maxflow=;
while(bfs(s,t,n)){
for(int i=;i<n;i++)cur[i]=head[i];
int u=s,tail=;
while(cur[s]!=-){
if(u==t){
int tp=INF;
for(int i=tail-;i>=;i--){
tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow); }
maxflow+=tp;
for(int i=tail-;i>=;i--){
edge[sta[i]].flow+=tp;
edge[sta[i]^].flow-=tp;
if(edge[sta[i]].cap-edge[sta[i]].flow==)
tail=i;
}
u=edge[sta[tail]^].to; }
else if(cur[u]!=-&&edge[cur[u]].cap>edge[cur[u]].flow
&&dep[u]+==dep[edge[cur[u]].to]){
sta[tail++]=cur[u];
u=edge[cur[u]].to;
}
else{
while(u!=s&&cur[u]==-){
u=edge[sta[--tail]^].to;
}
cur[u]=edge[cur[u]].next;
}
}
}
return maxflow;
} /* dinic end */ int m,n;
int main(){
init();
scanf("%d%d",&m,&n);
char buf[];
fgets(buf,,stdin); int s=,t=m+n+;
int sum=;
for(int i=;i<=m;i++){
fgets(buf,,stdin);
stringstream ss(buf);
int w;
ss>>w;
//cout<<w<<endl;
sum+=w;
addedge(s,i,w);
int j;
while(ss>>j){
//cout<<j<<endl;
addedge(i,j+m,INF);
}
} for(int i=;i<=n;i++){
int w;
scanf("%d",&w);
//cout<<"w="<<w<<endl;
addedge(i+m,t,w);
} int maxflow=dinic(s,t,t); vector<int> v1;
for(int u=;u<=m;u++){
if(dep[u]!=-){
v1.push_back(u);
//最后一次dinic还有dep的边说明没有被割掉
}
} vector<int>v2;
for(int u=;u<=n;u++){
if(dep[u+m]!=-){
v2.push_back(u);
//最后一次dinic还有dep的边说明没有被割掉
}
} for(int i=;i<v1.size();i++){
printf("%d%c",v1[i]," \n"[i==v1.size()-]);
} for(int i=;i<v2.size();i++){
printf("%d%c",v2[i]," \n"[i==v2.size()-]);
} printf("%d\n",sum-maxflow); }
上一篇:HTML5 中 40 个最重要的技术点


下一篇:[网络流24题] 太空飞行计划问题 (最大流->最大权闭合图)