[COCI2008-2009#6]SLICICE
2022/7/14 23:21:47
本文主要是介绍[COCI2008-2009#6]SLICICE,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
link
一道可以认为是很简单的题目。
每次比赛所有孩子的总卡片数都会加二,所以考虑建立比赛节点和孩子节点,孩子节点连汇点上界是最后的卡片数(流量太多就是孩子赢得太多,那么多余的卡片去哪了呢?细思极恐),比赛节点连源点上界是二。然后就很简单了,跑完之后找出每个孩子在那些比赛中得到的卡片,然后剩下的卡片咋构造都能构造出来不过多阐释了。
#include<bits/stdc++.h> //#define feyn const int N=5010; const int M=5e6; const int maxn=1e9; using namespace std; inline void read(int &wh){ wh=0;int f=1;char w=getchar(); while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();} while(w>='0'&&w<='9'){wh=wh*10+w-'0';w=getchar();} wh*=f;return; } struct edge{ int t,v,next; }e[M]; int head[N],esum=1; inline void adde(int fr,int to,int val){ e[++esum]=(edge){to,val,head[fr]};head[fr]=esum; } inline void add(int fr,int to,int val){ adde(fr,to,val);adde(to,fr,0); } int m,n,a[N],b[N],ss,tt,cnt,aa[N],ab[N],ac[N]; int q[N],ll,rr,d[N],t[N],nt; inline bool check(){ q[ll=rr=1]=ss;t[ss]=++nt;d[ss]=1; while(ll<=rr){ int wh=q[ll++]; for(int i=head[wh],th;i;i=e[i].next){ if(e[i].v==0||t[th=e[i].t]==nt)continue; t[th]=nt,d[th]=d[wh]+1,q[++rr]=th; } } return t[tt]==nt; } inline int dinic(int wh,int val){ if(wh==tt)return val; int used=0; for(int i=head[wh],th;i;i=e[i].next){ if(e[i].v==0||d[th=e[i].t]!=d[wh]+1)continue; int now=dinic(th,min(val,e[i].v)); if(now)used+=now,val-=now,e[i].v-=now,e[i^1].v+=now; if(val==0)break; } if(val)d[wh]=-1;return used; } signed main(){ #ifdef feyn freopen("in.txt","r",stdin); #endif read(m);read(n);int num=0; ss=++cnt,tt=++cnt; for(int i=1;i<=m;i++){ //printf("working\n"); b[i]=++cnt;read(ac[i]);add(b[i],tt,ac[i]);num+=ac[i]; } for(int i=1;i<=n;i++){ a[i]=++cnt;add(ss,a[i],2);read(aa[i]);read(ab[i]); add(a[i],b[aa[i]],2);add(a[i],b[ab[i]],2); } printf("%d\n",num/2); while(check())dinic(ss,maxn); for(int i=1;i<=n;i++){ printf("%d %d ",aa[i],ab[i]); for(int j=head[a[i]];j;j=e[j].next){ if(e[j].t==b[aa[i]]){ printf("%d\n",2-e[j].v); ac[aa[i]]-=(2-e[j].v),ac[ab[i]]-=e[j].v; break; } } } int last=0; for(int i=1;i<=m;i++){ if(ac[i]>=2){ printf("%d %d %d\n",i,i==1?2:1,2); ac[i]-=2;i--; } else if(ac[i]==1){ if(last){ printf("%d %d %d\n",last,i,1); last=0; } else last=i; } } return 0; }
这篇关于[COCI2008-2009#6]SLICICE的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升