「网络流24题」 2. 太空飞行计划问题

最大权闭合子图。

源点与实验连边权为实验费用的有向边；

仪器与汇点连边权为仪器费用的有向边；

实验与仪器之间连边权为INF的有向边。

答案为所有与源点相连的边的边权和减去图的最小割。

证明见国集队员胡伯涛论文《最小割模型在信息学竞赛中的应用》。

输出路径时，最后一次层次图中：

与源点相连的点即选做的实验；与汇点相连的点即选用的仪器。

注意

• 读入数据时，读到空格继续，否则停止。

• 仪器部分的点权+50，避免两部点权相同。

#include <algorithm> #include <cctype> #include <climits> #include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXN=120,MAXM=3000; bool vis[MAXN]; int m,n,S,T,cnt,ans,head[MAXN],dis[MAXN],cur[MAXN]; struct edges { int nxt,to,w; }e[MAXM]; void AddEdge(int x,int y,int w) { e[++cnt].nxt=head[x]; e[cnt].to=y; e[cnt].w=w; head[x]=cnt; } void AddEdges(int x,int y,int w) { AddEdge(x,y,w); AddEdge(y,x,0); } bool Read(int &x) { char c=getchar(); while(!isdigit(c)) c=getchar(); x=c^48; c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); return c==' '?1:0; } bool BFS(int S) { queue<int> q; memset(dis,0,sizeof dis); memset(vis,0,sizeof vis); q.push(S); vis[S]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x],t;i;i=e[i].nxt) if(e[i].w && !vis[t=e[i].to]) { dis[t]=dis[x]+1; q.push(t); vis[t]=1; } if(vis[T]) return 1; } return 0; } int DFS(int x,int k) { if(x==T) return k; int tmp=0; for(int i=cur[x],t,f;i;i=e[i].nxt) if(e[i].w && dis[t=e[i].to]==dis[x]+1 && (f=DFS(t,min(k,e[i].w)))) { cur[x]=i; e[i].w-=f; e[((i-1)^1)+1].w+=f; k-=f; tmp+=f; } if(!tmp) dis[x]=0; return tmp; } void Dinic(void) { int f; while(BFS(S)) while(memcpy(cur,head,sizeof cur),f=DFS(S,INT_MAX)) ans-=f; } int main(int argc,char *argv[]) { scanf("%d %d",&m,&n); S=0,T=n+51; for(int i=1,w,k;i<=m;++i) { scanf("%d",&w); AddEdges(S,i,w),ans+=w; bool r=0; do { r=Read(k); AddEdges(i,k+50,INT_MAX); } while(r); } for(int i=1,w;i<=n;++i) { scanf("%d",&w); AddEdges(i+50,T,w); } Dinic(); for(int i=1;i<=m;++i) if(dis[i]) printf("%d ",i); putchar('\n'); for(int i=1;i<=n;++i) if(dis[i+50]) printf("%d ",i); printf("\n%d\n",ans); return 0; }

谢谢阅读。

转载于:https://www.cnblogs.com/Capella/p/8098740.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/97474288

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。