USACO 4.2

P2740 [USACO4.2]草地排水Drainage Ditches

题目背景

在农夫约翰的农场上,每逢下雨,贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间。因此,农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼(不用担心,雨水会流向附近的一条小溪)。作为一名一流的技师,农夫约翰已经在每条排水沟的一端安上了控制器,这样他可以控制流入排水沟的水流量。

题目描述

农夫约翰知道每一条排水沟每分钟可以流过的水量,和排水系统的准确布局(起点为水潭而终点为小溪的一张网)。需要注意的是,有些时候从一处到另一处不只有一条排水沟。
根据这些信息,计算从水潭排水到小溪的最大流量。对于给出的每条排水沟,雨水只能沿着一个方向流动,注意可能会出现雨水环形流动的情形。

输入输出格式

输入格式:

第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫John已经挖好的排水沟的数量,M是排水沟交叉点的数量。交点1是水潭,交点M是小溪。
第二行到第N+1行: 每行有三个整数,Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点,雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。

输出格式:

输出一个整数,即排水的最大流量。

输入输出样例

输入样例#1:

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

输出样例#1:

50

说明

题目翻译来自NOCOW。
USACO Training Section 4.2

题解

最大流,我用EK水过去的

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
87
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
int n,m;
int mi;
int i;
int l,r;
int x,y,z;
int c[210][210];//容量
int f[210][210];//目前排水管内水量
int q[210];//bfs的时候标记用的
int flag;
struct node
{
int p;//上一个点在队列中的编号
int d;//点的编号
}a[20000];
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&z);
c[x][y]+=z;//x→y不止一条排水沟,所以加上去
}
flag=1;//标记有没有增广路径
while (flag)//反复找直到找不到增广路
{
flag=0;//先标记为没有增广路
for (i=1;i<=m;i++) q[i]=1;//把所有的点标记为没走过
l=0;r=1;
a[1].p=0;//起点入队
a[1].d=1;
while (l<r)
{
l++;
x=a[l].d;//队首出队
for (i=1;i<=m;i++)
if (q[i]&&(c[x][i]>f[x][i]||f[i][x]>0))
//没走过 而且 容量大于目前水量 或者 有水从i流到x
{
q[i]=0;//入队
r++;
a[r].d=i;
a[r].p=l;
//cout<<i<<" ";
if (i==m)//所以搜完了
{
//puts("23333");
flag=1;//标记
break;//退出
}
}
//cout<<endl;
if (flag==1) break;//这个循环也要退出
}
//puts("23333");
if (flag==0) break;//找不到增广路了
mi=1000000001;
i=r;
while (a[i].p)
{
//puts("23333");
x=a[i].d;//自己编号
y=a[a[i].p].d;//上一个点的编号
if (c[y][x]>f[y][x]&&c[y][x]-f[y][x]<mi)mi=c[y][x]-f[y][x];
if (f[x][y]>0&&f[x][y]<mi) mi=f[x][y];
i=a[i].p;
}
i=r;
while (a[i].p)
{
x=a[i].d;//自己编号
y=a[a[i].p].d;//上一个点的编号
if (c[y][x]>f[y][x]) f[y][x]+=mi;
if (f[x][y]>0) f[x][y]-=mi;
i=a[i].p;
}
}
int ans=0;
for (i=1;i<=n;i++) ans+=f[1][i];//统计输出
printf("%d\n",ans);
return 0;
}

P1894 [USACO4.2]完美的牛栏The Perfect Stall

题目描述

农夫约翰上个星期刚刚建好了他的新牛棚,他使用了最新的挤奶技术。不幸的是,由于工程问题,每个牛栏都不一样。第一个星期,农夫约翰随便地让奶牛们进入牛栏,但是问题很快地显露出来:每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期,农夫约翰刚刚收集到了奶牛们的爱好的信息(每头奶牛喜欢在哪些牛栏产奶)。一个牛栏只能容纳一头奶牛,当然,一头奶牛只能在一个牛栏中产奶。
给出奶牛们的爱好的信息,计算最大分配方案。

输入输出格式

输入格式:

第一行 两个整数,N (0 <= N <= 200) 和 M (0 <= M <= 200) 。N 是农夫约翰的奶牛数量,M 是新牛棚的牛栏数量。
第二行到第N+1行 一共 N 行,每行对应一只奶牛。第一个数字 (Si) 是这头奶牛愿意在其中产奶的牛栏的数目 (0 <= Si <= M)。后面的 Si 个数表示这些牛栏的编号。牛栏的编号限定在区间 (1..M) 中,在同一行,一个牛栏不会被列出两次。

输出格式:

只有一行。输出一个整数,表示最多能分配到的牛栏的数量.

输入输出样例

输入样例#1:

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

输出样例#1:

4

说明

N (0 <= N <= 200)
M (0 <= M <= 200)

题解

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

/*
ID: ylx14271
PROG: stall4
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,m;//n个牛栏
int i,j;
int vis[610];
int link[610];
int a[610];
int ans;
int f[610][610];
bool dfs(int aa)
{
int j;
for (j=1;j<=m;j++)
{
if (f[aa][j]==1&&vis[j]!=1)//可以连到并且没有匹配过
{
vis[j]=1;//标记
if (!link[j]||dfs(link[j]))
//点j没有被匹配过或者匹配点j的点又找到点可以匹配了
{
link[j]=aa;//存起来
return 1;
}
}
}
return 0;
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
ans=0;
memset(f,0,sizeof(f));
memset(link,0,sizeof(link));
for (i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
while (x--)//用邻接矩阵
{
int xx;
scanf("%d",&xx);
f[i][xx]=1;
}
}
for (int ii=1;ii<=n;ii++)
{
memset(vis,0,sizeof(vis));//清0
if (dfs(ii))//统计结果
{
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}

P2751 [USACO4.2]工序安排Job Processing

题目描述

一家工厂的流水线正在生产一种产品,这需要两种操作:操作A和操作B。每个操作只有一些机器能够完成。

上图显示了按照下述方式工作的流水线的组织形式。A型机器从输入库接受工件,对其施加操作A,得到的中间产品存放在缓冲库。B型机器从缓冲库接受中间产品,对其施加操作B,得到的最终产品存放在输出库。所有的机器平行并且独立地工作,每个库的容量没有限制。每台机器的工作效率可能不同,一台机器完成一次操作需要一定的时间。

给出每台机器完成一次操作的时间,计算完成A操作的时间总和的最小值,和完成B操作的时间总和的最小值。

注:1、机器在一次操作中干掉一个工件; 2、时间总和的意思是最晚时间点

输入输出格式

输入格式:

第一行 三个用空格分开的整数:N,工件数量 (1<=N<=1000);M1,A型机器的数量 (1<=M1<=30);M2,B型机器的数量 (1<=M2<=30)。
第二行…等 M1个整数(表示A型机器完成一次操作的时间,1..20),接着是M2个整数(B型机器完成一次操作的时间,1..20)

输出格式:

只有一行。输出两个整数:完成所有A操作的时间总和的最小值,和完成所有B操作的时间总和的最小值(A操作必须在B操作之前完成)。

输入输出样例

输入样例#1:

5 2 3
1 1 3 1 4

输出样例#1:

3 5

说明

题目翻译来自NOCOW。
USACO Training Section 4.2

题解

所以这道题贪心
开始从前往后贪,根据完成时间选择加工每件物品的机器(完成时间=等待时间+加工时间)
然后第二问从后往前贪,让最后一个完成操作A的物品 用效率最高的机器完成操作B
嗯代码挺详细的。

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdlib>
#include<list>
#include<map>
#include<set>
#include<list>
#include<stack>
using namespace std;
int n,A,B;//n:
int m;
int i,j;
struct node
{
int s;//目前这台机器 完成目前物品 结束的时间
int v;//该机器速度
bool operator<(node k)const
{
return s>k.s;
} //小根堆
};
priority_queue<node> q;
int t[2000];
int ans;
int main()
{
freopen("job.in","r",stdin);
freopen("job.out","w",stdout);
scanf("%d%d%d",&n,&A,&B);
node x;
for (i=1;i<=A;i++)
{
scanf("%d",&x.v);
x.s=x.v;
q.push(x);//把速度压入优先队列中
}
for (i=1;i<=n;i++)
{
x=q.top();//取出最小值
q.pop();//把最小值弹出
t[i]=x.s;//t[i]存的是第i个物品完成操作A 结束的时间
x.s+=x.v;//然后下一个物品要用这台机器 结束的时间就要+x.v
q.push(x);//再次压入栈
}
while (!q.empty()) q.pop();
for (i=B;i>=1;i--)
{
scanf("%d",&x.v);
x.s=x.v;
q.push(x);
}
ans=0;
for (i=n;i>=1;i--)
{
x=q.top();//取出最小值
q.pop();//把最小值弹出
if (x.s+t[i]>ans) ans=x.s+t[i];//求最晚结束时间
x.s+=x.v;//然后下一个物品要用这台机器 结束的时间就要+x.v
//然而似乎开始用这台机器的操作该物品时候,可能上一个物品用这台
//机器已经完成任务了,然而这并不影响QAQ
q.push(x);
}
printf("%d %d\n",t[n],ans);
return 0;
}