四川省建设工程信息网站,网站开发下载哪个,长春做网站推荐选吉网传媒好,建设银行河北省分行官方网站★★☆ 输入文件#xff1a;stall4.in 输出文件#xff1a;stall4.out 简单对比 时间限制#xff1a;1 s 内存限制#xff1a;128 MB USACO/stall4(译by Felicia Crazy)描述 农夫约翰上个星期刚刚建好了他的新牛棚#xff0c;他使用了最新的挤奶技术。不幸的是stall4.in 输出文件stall4.out 简单对比 时间限制1 s 内存限制128 MB USACO/stall4(译by Felicia Crazy) 描述 农夫约翰上个星期刚刚建好了他的新牛棚他使用了最新的挤奶技术。不幸的是由于工程问题每个牛栏都不一样。第一个星期农夫约翰随便地让奶牛们进入牛栏但是问题很快地显露出来每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期农夫约翰刚刚收集到了奶牛们的爱好的信息每头奶牛喜欢在哪些牛栏产奶。一个牛栏只能容纳一头奶牛当然一头奶牛只能在一个牛栏中产奶。 给出奶牛们的爱好的信息计算最大分配方案。 格式 PROGRAM NAME: stall4 INPUT FORMAT: (file stall4.in) 第一行 两个整数N (0 N 200)和M (0 M 200)。N是农夫约翰的奶牛数量M是新牛棚的牛栏数量。 第二行到第N1行 一共N行每行对应一只奶牛。第一个数字(Si)是这头奶牛愿意在其中产奶的牛栏的数目(0 Si M)。后面的Si个数表示这些牛栏的编号。牛栏的编号限定在区间(1..M)中在同一行一个牛栏不会被列出两次。 OUTPUT FORMAT: (file stall4.out) 只有一行。输出一个整数表示最多能分配到的牛栏的数量。 SAMPLE INPUT (file stall4.in) 5 5 2 2 5 3 2 3 4 2 1 5 3 1 2 5 1 2 SAMPLE OUTPUT (file stall4.out) 4 思路 最大流 代码实现 1 #includecstdio2 #includecstring3 using namespace std;4 const int maxn1e5;5 inline int min_(int x,int y){return xy?x:y;}6 int n,m,s,t,ans;7 int a,b;8 int h[maxn],hs1,ew[maxn],et[maxn],en[maxn];9 void add(int u,int v){
10 hs,et[hs]v,ew[hs]1,en[hs]h[u],h[u]hs;
11 hs,et[hs]u,ew[hs]0,en[hs]h[v],h[v]hs;
12 }
13 int q[maxn],head,tail;
14 int d[maxn];
15 void SPFA(int s){
16 memset(d,0,sizeof(d));
17 headtail0;
18 q[head]s,d[s]1;
19 while(headtail){
20 aq[tail];
21 for(int ih[a];i;ien[i])
22 if(!d[et[i]]ew[i]){
23 d[et[i]]d[a]1;
24 if(et[i]t) return;
25 q[head]et[i];
26 }
27 }
28 }
29 int ap(int k,int nw){
30 if(kt) return nw;
31 int bwnw;
32 for(int ih[k];i;ien[i])
33 if(ew[i]d[et[i]]d[k]1){
34 int dwap(et[i],min_(bw,ew[i]));
35 if(dw) ew[i]-dw,ew[i^1]dw,bw-dw;
36 else d[et[i]]0;
37 }
38 return nw-bw;
39 }
40 void Dinic(){while(SPFA(s),d[t]) ansap(s,n);}
41 int main(){
42 freopen(stall4.in,r,stdin);
43 freopen(stall4.out,w,stdout);
44 scanf(%d%d,n,m);
45 snm1,ts1;
46 for(int i1;in;i) add(s,i);
47 for(int i1;im;i) add(ni,t);
48 for(int i1;in;i){
49 scanf(%d,a);
50 for(int j1;ja;j){
51 scanf(%d,b);
52 add(i,nb);
53 }
54 }
55 Dinic();
56 printf(%d\n,ans);
57 return 0;
58 } 转载于:https://www.cnblogs.com/J-william/p/7041209.html
