博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
网络流24题 洛谷 2763 试题库问题
阅读量:4491 次
发布时间:2019-06-08

本文共 2060 字,大约阅读时间需要 6 分钟。

代码风格迥异 ……

#include
const int N=1000+4,M=1000000+10,K=30+5;using namespace std;queue
q;int head[M],flt[M],nxt[M],to[M],cn=1;int ans[K][N],dis[N],num[K];int n,k,x,tmp,src,sink,inf=1e8+7;bool vis[N];int minx(int a,int b){ return a < b ? a : b ;}void create(int u,int v,int f){ cn++; to[cn]=v; flt[cn]=f; nxt[cn]=head[u]; head[u]=cn; cn++; to[cn]=u; flt[cn]=0; nxt[cn]=head[v]; head[v]=cn; }bool bfs(){ int v; memset(dis,0,sizeof(dis)); memset(vis,false,sizeof(vis)); q.push(src); vis[src]=true; while(!q.empty()){ tmp=q.front(); for(int i=head[tmp];i;i=nxt[i]){ v=to[i]; if(flt[i] && !vis[v]){ dis[v]=dis[tmp]+1; q.push(v); vis[v]=true; } } q.pop(); } return dis[sink]>0;}int dinic(int u,int delta){ if(u==sink) return delta; int res=0,v; for(int i=head[u];i && delta;i=nxt[i]){ v=to[i]; if(flt[i] && dis[v]==dis[u]+1){ int dd=dinic(v,minx(flt[i],delta)); flt[i]-=dd; delta-=dd; flt[i^1]+=dd; res+=dd; } } return res;}int main(){ ios::sync_with_stdio(false); cin>>k>>n; for(int i=1+n;i<=k+n;i++) cin>>num[i]; src=0;sink=k+n+1; for(int i=1;i<=n;i++) create(src,i,1); for(int i=1;i<=n;i++){ cin>>x; for(int j=1;j<=x;j++){ cin>>tmp; create(i,tmp+n,1); } } for(int i=n+1;i<=n+k;i++) create(i,sink,num[i]); while(bfs()) dinic(src,inf); for(int i=1;i<=n;i++){ for(int j=head[i];j;j=nxt[j]){ int v=to[j]; if(!flt[j]) ans[v][++ans[v][0]]=i; } } for(int i=1;i<=k;i++){ cout<
<<": "; for(int j=1;j<=ans[i+n][0];j++) cout<
<<" "; cout<
Ans

转载于:https://www.cnblogs.com/horsepower2001/p/8970355.html

你可能感兴趣的文章
Spark项目之电商用户行为分析大数据平台之(七)数据调研--基本数据结构介绍...
查看>>
原来fb可以在一个工程里面输出多个swf模块
查看>>
Codeforces Round #271 (Div. 2) E. Pillars 线段树优化dp
查看>>
Codeforces Round #FF (Div. 2) D. DZY Loves Modification 优先队列
查看>>
【学习】logger
查看>>
Delphi APP 開發入門(十)REST Client 開發
查看>>
elk
查看>>
.net 模糊匹配路径
查看>>
用包来组织模型
查看>>
ORA-29857: 表空间中存在域索引和/或次级对象
查看>>
LeetCode58 Length of Last Word
查看>>
Python基础语法 系统学习
查看>>
推荐15款好用的JS开发工具
查看>>
ios开发之数据的持久化存储机制
查看>>
poj 3264
查看>>
图标跟着摄像机(Camera)orthographicSize的值改变大小
查看>>
LeetCode 386——字典序排数
查看>>
Learn day1 变量/数据类型
查看>>
go安装和开发工具安装
查看>>
【Scala】Scala技术栈
查看>>