【输入文件示例】shuttle.in
2 3 10 1 2 25 2 3 5 6 7
【输出文件示例】shuttle.out
1 2 1 2 3 17
网络流一眼题。(最大闭合权图)
#include<cstdio> #include<iostream> using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int N=1e5+10; const int inf=0x7fffffff; struct node{ int v,next,cap; }e[N*10];int tot=1; int n,m,ans,S,T,a[N],b[N],head[N],dis[N],q[N*10]; bool vis[N]; void add(int x,int y,int z){ e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot; e[++tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot; } bool bfs(){ for(int i=S;i<=T;i++) dis[i]=inf; int h=0,t=1;q[t]=S;dis[S]=0; while(h!=t){ int x=q[++h]; for(int i=head[x],v;i;i=e[i].next){ if(e[i].cap&&dis[v=e[i].v]>dis[x]+1){ dis[v]=dis[x]+1; if(v==T) return 1; q[++t]=v; } } } return 0; } int dfs(int x,int f){ if(x==T) return f; int used=0,t; for(int i=head[x],v;i;i=e[i].next){ if(e[i].cap&&dis[v=e[i].v]==dis[x]+1){ t=dfs(v,min(f,e[i].cap)); e[i].cap-=t;e[i^1].cap+=t; used+=t;f-=t; if(!f) return used; } } if(!used) dis[x]=0; return used; } int dinic(){ int res=0; while(bfs()) res+=dfs(S,inf); return res; } void DFS(int x){ for(int i=head[x],v;i;i=e[i].next){ if(!vis[v=e[i].v]&&e[i].cap){ vis[v]=1; DFS(v); } } } char ch; int main(){ freopen("shuttle.in","r",stdin); freopen("shuttle.out","w",stdout); n=read();m=read();S=0;T=n+m+1; for(int i=1,x,c;i<=n;i++){ x=read();ans+=x;c=0; add(S,i,x); while(1){ while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') c=c*10+ch-'0',ch=getchar(); add(i,c+n,inf);c=0; if(ch==' ') break;//Linux请注意 } } for(int i=1,x;i<=m;i++){ x=read();add(i+n,T,x); } int flow=dinic(); DFS(S); for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i);printf(" "); for(int i=n+1;i<=n+m;i++) if(vis[i]) printf("%d ",i-n);printf(" "); printf("%d ",ans-flow); return 0; }