「JoyOI1517」飘飘乎居士的乌龟
背景 Background
飘飘乎居士养了乌龟。当然，这些乌龟是用来出售赚取利润的。
描述 Description
飘飘乎居士的乌龟被安置在了m个窝中。现在，飘飘乎居士已经接到了n个人的定购通知，他们会按顺序在来挑选乌龟，其中，第i个人会在pi个窝中挑选乌龟，但最多只想买xi只乌龟。另外，在第i个人购买完乌龟以后，飘飘乎居士会将指定的qi个窝中的龟进行调整，他可以任意调换指定的qi个窝中乌龟数量。飘飘乎希望知道，在n个人购买完乌龟后，他最多可以出售多少只乌龟？
输入格式 InputFormat
输入格式：第一行，两个正整数n、m。
接下来一行m个整数（可能为0），第i个整数表示第i个窝中乌龟的数量。
接下来输入分为n组，每组3行输入，第i组表示第i个人的信息：
第一行一个整数xi，表示第i个人最多购买的乌龟数量
第二行一个整数pi以及pi整数，表示该顾客会在pi个指定的窝中挑选乌龟
第三行一个整数qi（qi可能为0）以及跟着的qi个正整数，表示在第i个人购买完乌龟后，飘飘乎居士会调整这qi个窝中乌龟的数量。
输出格式 OutputFormat
输出格式：一行，表示飘飘乎居士最多出售乌龟的数量。
样例输入 SampleInput [复制数据]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
输入样例1： 2 4 2 2 5 0 3 1 3 2 1 4 10 2 4 3 0 输入样例2： 2 4 1 2 3 3 3 2 1 4 2 4 3 4 1 3 4 1 2 3 4 |
数据范围和注释 Hint
Hint：样例一解释：飘飘乎居士4个窝，初始时，第一个窝里有2只乌龟，第二个窝里有2只乌龟，第三个窝里有5只乌龟；第四窝里没有乌龟，共有2位顾客来购买乌龟。
在第一位顾客到来时，他想在3号窝中挑选乌龟，最多只想买3只乌龟。飘飘乎居士将3号窝中的乌龟出售。出售以后，3号窝剩下2只乌龟，飘飘乎居士可以调整1、4号窝中乌龟的数量，将1号窝中的2只乌龟转入4号窝中，这样，1号窝没有乌龟，3号窝2只乌龟，4号窝有2只乌龟。
在第二个顾客来时，他想要在3 4号窝中挑选最多10只乌龟，飘飘乎居士将从1号窝调整到4号窝中的2只乌龟以及3号窝剩下的2只乌龟卖出。共卖出7只乌龟，也就是最后的答案。
数据范围：0<n、m<=10
每个窝初始时乌龟的数量以及每位顾客购买乌龟的数量<=100000
0<=Pi、qi<=n
数据保证输入的正确性。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define T 201 #define inf 0x7fffffff using namespace std; int n,m,cnt=1,ans; int q[205],h[205],head[205],cur[205]; struct data{int to,next,v;}e[100001]; void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,0);} bool bfs() { int t=0,w=1; for(int i=0;i<=T;i++)h[i]=-1; q[0]=0;h[0]=0; while(t!=w) { int now=q[t];t++;if(t==6005)t=0; for(int i=head[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[w++]=e[i].to;if(w==6005)w=0; } } if(h[T]==-1)return 0; return 1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=cur[x];i;i=e[i].next) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(e[i].v,w)); e[i].v-=w; if(e[i].v)cur[x]=i; e[i^1].v+=w; used+=w;if(used==f)return f; } } if(!used)h[x]=-1; return used; } void dinic() {while(bfs()){for(int i=0;i<=T;i++)cur[i]=head[i];ans+=dfs(0,inf);}} int main() { int x,y,t[25]; scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) {scanf("%d",&x);insert(0,n*(i-1)+1,x);} for(int i=1;i<=m;++i) for(int j=1;j<n;++j) insert(n*(i-1)+j,n*(i-1)+j+1,inf); for(int i=1;i<=n;++i) { scanf("%d",&x); insert(n*m+i,T,x); scanf("%d",&x); for(int j=1;j<=x;++j) { scanf("%d",&y); insert(n*(y-1)+i,n*m+i,inf); } scanf("%d",&x); for(int j=1;j<=x;++j) scanf("%d",t+j); if(i<n) for(int j=1;j<x;++j) { insert(n*(t[j]-1)+i+1,n*(t[j+1]-1)+i+1,inf); insert(n*(t[j+1]-1)+i+1,n*(t[j]-1)+i+1,inf); } } dinic(); printf("%d",ans); return 0; } |
OI 课件=>
