USACO Job Processing

可以看出，这道题是一个任务调度问题，对于A任务，很容易想到用贪心算法解决，即针对每个任务，选择完成时间最早的机器处理。那么，最后一个任务的结束时间就是完成所有A任务的最短时间。

然而，B任务，情况就不同了。B任务必须在有中间产物时才可以开始，因此，必须在第一个A任务结束后才可以开始。容易知道，当A全部完成后，B还需要花费时间加工，如果可以把这段时间缩短，就可以缩短总体时间。（读者也可以从“对称性”的角度分析）

于是，我们先用A的方法，计算在中间产物充足时完成每个B任务的时间。然后把这个时间逆序，把其中每一项和完成A任务的时间相加得到一个新的数组，这个数组的最大值就是完成所有工序的最短时间。

上面一段话写得有点乱。上面说到的方法其实是Johnson's Algorithm，wikipedia和这个页面上有更详细的介绍。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <limits.h>
04 #define MAX_MACHINE 33
05 #define MAX_TIME 21
06
07 int na,nb,job;
08 int ta[MAX_MACHINE],tb[MAX_MACHINE];
09 long finish[2][1001];
10
11 int cmp(const void *a,const void *b)
12 {
13     return (*(int *)a - *(int *)b);
14 }
15
16 void init()
17 {
18     int i;
19     scanf("%d %d %d\n",&job,&na,&nb);
20     for(i = 0;i < na;i ++)
21         scanf("%d",&ta[i]);
22     for(i = 0;i < nb;i ++)
23         scanf("%d",&tb[i]);
24     qsort(ta,na,sizeof(int),cmp);
25     qsort(tb,nb,sizeof(int),cmp);
26 }
27
28 void solve_a()
29 {
30     int busy_until[MAX_MACHINE] = {};
31     int i,j;
32     int min,assignto;
33     for(i = 1;i <= job;i ++)
34     {
35         min = INT_MAX;
36         for(j = 0;j < na;j ++)
37         {
38             if(ta[j] + busy_until[j] < min)
39             {
40                 min = ta[j] + busy_until[j];
41                 assignto = j;
42             }
43         }
44         busy_until[assignto] = min;
45         finish[0][i] = min;
46         //printf("%d %ld\n",assignto,finish[0][i]);
47     }
48     printf("%ld ",finish[0][job]);
49 }
50
51 void solve_b()
52 {
53     int busy_until[MAX_MACHINE] = {};
54     int i,j;
55     int min,assignto;
56     for(i = 1;i <= job;i ++)
57     {
58         min = INT_MAX;
59         for(j = 0;j < nb;j ++)
60         {
61             if(tb[j] + busy_until[j] < min)
62             {
63                 min = tb[j] + busy_until[j];
64                 assignto = j;
65             }
66         }
67         busy_until[assignto] = min;
68         finish[1][i] = min;
69         //printf("%d %ld\n",assignto,finish[0][i]);
70     }
71     //printf("%ld ",finish[1][job]);
72 }
73
74 void combine()   //Johnson's Algorithm
75 {
76     int i;
77     long max = 0;
78     for(i = 1;i <= job;i ++)
79     {
80         if(finish[0][i] + finish[1][job - i + 1] > max)
81             max = finish[0][i] + finish[1][job - i + 1];
82     }
83     printf("%ld\n",max);
84 }
85
86 int main()
87 {
88     freopen("job.in","r",stdin);
89     freopen("job.out","w",stdout);
90     init();
91     solve_a();
92     solve_b();
93     combine();
94     return 0;
95 }

USACO The Perfect Stall

容易看出，cow和stall可以构成一个二分图，如果一个cow可以在某个stall中产奶，那么他它们之间就有一条边。
题目要求就是这个二分图的最大匹配。
由于点数很小，直接用Ford-Fulkerson算法就可以了。
不过求解二分图最大匹配还有一个匈牙利算法（wikipedia），有兴趣的读者可以自行学习。本人曾经学过，不过忘的差不多了。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define MXN (410)
005
006 int M,N;
007 int cap[MXN][MXN];
008 int source = 0;   //virtual source and sink
009 int sink;
010 //used in BFS
011 int queue[MXN];
012 int visit[MXN];
013 int prev[MXN];
014 int flow[MXN];  //the new find flow to each node
015 int head,tail;
016 //
017
018 void init()
019 {
020     scanf("%d%d\n",&N,&M);
021     int i,t,s;
022     for(i = 1;i <= N;i ++)
023     {
024         scanf("%d",&t);
025         while(t --)
026         {
027             scanf("%d",&s);
028             cap[i][s + N] = 1;
029         }
030     }
031     sink = M + N + 1;
032     for(i = 1;i <= N;i ++)
033         cap[source][i] = 1;
034     for(i = 1;i <= M;i ++)
035         cap[i + N][sink] = 1;
036 }
037
038 void enqueue(int n)
039 {
040     queue[tail ++] = n;
041 }
042
043 int dequeue()
044 {
045     return queue[head ++];
046 }
047
048 int get_min(int a,int b)
049 {
050     if(a < b)    return a;
051     return b;
052 }
053
054 int bfs()    //find an argument path
055 {
056     int now,i;
057     memset(visit,0,sizeof(visit));
058     head = tail = 0;
059     flow[source] = MXN;
060     enqueue(source);
061     visit[source] = 1;
062     while(head < tail)
063     {
064         now = dequeue();
065         for(i = sink;i >= source;i --)
066         {
067             if(cap[now][i] > 0 && !visit[i])
068             {
069                 enqueue(i);
070                 flow[i] = get_min(flow[now],cap[now][i]);
071                 visit[i] = 1;
072                 prev[i] = now;
073                 if(i == sink)
074                 {
075                     return flow[sink];
076                 }
077             }
078         }
079     }
080     return 0;
081 }
082
083 void solve()
084 {
085     int i;
086     int newflow;
087     int totmax = 0;
088     while(1)
089     {
090         newflow = bfs();
091         if(newflow == 0)    break;
092         for(i = sink;i > 0;i = prev[i])
093         {
094             cap[prev[i]][i] -= newflow;
095             cap[i][prev[i]] += newflow;
096         }
097         totmax += newflow;
098     }
099     printf("%d\n",totmax);
100 }
101
102 int main()
103 {
104     freopen("stall4.in","r",stdin);
105     freopen("stall4.out","w",stdout);
106     init();   
107     solve();
108     return 0;
109 }

USACO Drainage Ditches

基本的网络流。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define MAXNODE 210
005 #define INF (10000000+10)
006
007 typedef struct Qelement
008 {
009     int node;
010     long flow;
011 }Qelement;
012
013 unsigned long cap[MAXNODE][MAXNODE] = {};
014 int M,N;
015
016 void init()
017 {
018     scanf("%d%d\n",&N,&M);
019     int i;
020     int s,e;
021     long c;
022     for(i = 0;i < N;i ++)
023     {
024         scanf("%d%d%ld\n",&s,&e,&c);
025         cap[s][e] += c;   //+=可以解决多条边的问题
026     }
027 }
028
029 int prev[MAXNODE];   //BFS时前一个点的编号
030 Qelement queue[10 * MAXNODE];
031 _Bool visit[MAXNODE];
032 int head,tail;
033
034 void enqueue(int n,int f)
035 {
036     queue[tail].node = n;
037     queue[tail].flow = f;
038     tail ++;
039 }
040
041 Qelement dequeue()
042 {
043     return queue[head ++];
044 }
045
046 unsigned long get_min(unsigned long a,unsigned long b)
047 {
048     if(a < b)    return a;
049     return b;
050 }
051
052 long bfs()    //BFS找增广路
053 {
054     int i;
055     Qelement now;
056     head = tail = 0;
057     memset(visit,0,sizeof(visit));
058     enqueue(1,INF);
059     visit[1] = 1;
060     while(head < tail)
061     {
062         now = dequeue();
063         for(i = 1;i <= M;i ++)
064         {
065             if(!visit[i] && cap[now.node][i] > 0)
066             {
067                 visit[i] = 1;
068                 prev[i] = now.node;
069                 enqueue(i,get_min(cap[now.node][i],now.flow));
070                 if(i == M)
071                 {
072                     return get_min(cap[now.node][i],now.flow);
073                 }
074             }
075         }
076     }
077     return 0;
078 }
079
080
081 void solve_max_flow()
082 {
083     int i;
084     unsigned long maxflow;
085     unsigned long totmax = 0;
086     while(1)
087     {
088         maxflow = bfs();
089         if(maxflow == 0)    break;   //没有增广路，结束
090         totmax += maxflow;
091         for(i = M;i != 1;i = prev[i])
092         {
093             cap[prev[i]][i] -= maxflow;
094             cap[i][prev[i]] += maxflow;
095         }
096     }
097     printf("%ld\n",totmax);
098 }
099
100 int main()
101 {
102     freopen("ditch.in","r",stdin);
103     freopen("ditch.out","w",stdout);
104     init();
105     solve_max_flow();
106     return 0;
107 }

USACO Fence Rails

首先，要弄明白题目的意思，简单说就是有N个背包，每个有一定的重量限制，有R件物品（每件物品都不可分割），每件有一定的重量，求这些背包可以装下的物品的最大数量。题目中有一句话容易引起误解：There is no need to manufacture more rails (or more of any kind of rail) than called for the list of required rails.本人最初认为必须“恰好”把背包装满（NOCOW上的样例解释也是这样的），因此折腾了好长一段时间。实际上没有这个限制。

既然要装下尽可能多的物品，那么就应该先选入小的物品。所以，先把物品按照重量递增排序。那么：
1）如果前k物品不能装入背包，那么即使把其中一个物品P换成k+1~R中的一个物品Q，由于Q的重量大于P，因此也绝对不可能成功装入背包。
2）如果前k个物品可以装入背包，那么前k-1个物品也一定能装入背包。
3）如果前k个物品不能装入背包，那么前k+1个物品也一定不能装入背包。
这样，一个最值问题就转化成了判定性问题，只要枚举出可行的最大k值就可以了。从2、3两个结论中还可以得知可行性与k的关系是“单调”的，因此，可以使用二分查找优化枚举(貌似不二分也可以通过所有数据)。

因此，只要构建一个函数，用来判断前k个物品是否可以装入，程序就完成了一大半。

最朴素的方法(检测第0～index号物品是否可以装入)：

C语言: 高亮代码由发芽网提供

01 int dfs_check(int index)
02 {
03     int i;
04     if(index < 0)      //成功装入背包
05         return 1;
06    
07     for(i = 0;i < N;i ++)
08     {
09         if(board[i] >= rail[index])    //把rail[index]放入背包
10         {
11             board[i] -= rail[index];
12             r = dfs_check(index - 1);
13             board[i] += rail[index];
14             if(r == 1)    return 1;   //我们只需要“一个解”，故发现之后立即返回
15         }
16     }
17     return 0;   //放入失败
18 }

可是，这个dfs的速度是非常慢的，因此，需要“剪枝”。为方便起见，记所有背包的容量和为boardsum，前k个物品重量和为railsum[k]。

1）重量大于最大背包容量的物品可以直接删去，容量小于最小物品重量的背包也可以直接删去。（这不算剪枝，应该是预处理）
2）如果可以把前k个物品全部装入，那么浪费掉的容量waste一定是boardsum-railsum[k]。当一个背包的剩余容量小于物品重量的最小值，即不能装入任何物品时，把剩余的容量加到current_waste中，一旦current_waste > waste,就说明这种情况一定不能找到解，应该回溯（比较强大）。
3）如果存在两个物品p1,p2的重量相等，因此可以把他们看作是一样的，所以可以直接固定p2的顺序，把它放在p1后面（非常强大）。
4）如果railsum[k]>boardsum,那么这k个物品一定不能放入背包。
5）改变搜索顺序也可以加快速度，由于放入较大的物品是比较难的，因此dfs的时候可以从大的物品开始。（这点很容易被忘记，但有些时候改变顺序的确很有效）

第1个剪枝是本人自己想到的。2，3，4都是从NOCOW和google上搜到的，真的很难想到，尤其是第三个。

此外，在写二分的时候要小心，不要进入死循环。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 int N,R;
006 int rail[1024];
007 int board[50];
008 int boardsum;
009 int railsum[1024];
010
011 int cmp1(const void *a,const void *b)  //large to small
012 {
013     return(*(int *)a < *(int *)b);
014 }
015
016 int cmp2(const void *a,const void *b)  //small to large
017 {
018     return(*(int *)a > *(int *)b);
019 }
020
021 void init()
022 {
023     scanf("%d",&N);
024     int i;
025     for(i = 0;i < N;i ++)
026     {
027         scanf("%d",&board[i]);
028         boardsum += board[i];
029     }
030     qsort(board,N,sizeof(int),cmp1);
031     scanf("%d\n",&R);
032     for(i = 0;i < R;i ++)
033     {
034         scanf("%d",&rail[i]);
035     }
036     qsort(rail,R,sizeof(int),cmp2);
037     //ignore impossible boards and rails
038     while(rail[R - 1] > board[0] && R > 0)    R --;
039     while(N > 0 && board[N - 1] < rail[0])    N --;
040     if(R == 0 || N == 0)   //无解的特殊情况
041     {
042         printf("0\n");
043         fclose(stdout);
044         exit(0);
045     }
046     railsum[0] = rail[0];
047     for(i = 1;i < R;i ++)
048     {
049         railsum[i] = railsum[i - 1] + rail[i];
050     }
051 }
052
053 int cut_rail_from[1030];
054 int max_waste,cur_waste;
055 int dfs_check(int index)
056 {
057     int start,i,r;
058     if(cur_waste > max_waste)    return 0;
059     if(index < 0)
060     {
061         return 1;
062     }
063     if(rail[index] == rail[index + 1])
064     {
065         start = cut_rail_from[index + 1];
066     }
067     else start = 0;
068    
069     for(i = start;i < N;i ++)
070     {
071         if(board[i] >= rail[index])
072         {
073             board[i] -= rail[index];
074             cut_rail_from[index] = i;
075             if(board[i] < rail[0])    cur_waste += board[i];
076             r = dfs_check(index - 1);
077             if(board[i] < rail[0])    cur_waste -= board[i];
078             board[i] += rail[index];
079             cut_rail_from[index] = -1;
080             if(r == 1)    return 1;
081         }
082     }
083     return 0;
084 }
085
086 void binary()
087 {
088     int i;
089     for(i = 0;i < R;i ++)
090         cut_rail_from[i] = -1;
091     int l,r,mid;
092     l = 0;
093     r = R - 1;
094     for(r = R - 1;r >= 0 && railsum[r] > boardsum;r --);
095     while(l < r)
096     {
097         mid = (l + r + 1) / 2;       //向上取整
098         max_waste = boardsum - railsum[mid];
099         cur_waste = 0;
100         if(dfs_check(mid))
101             l = mid;
102         else    r = mid - 1;
103     }
104     printf("%d\n",l + 1);
105 }
106
107 int main()
108 {
109     freopen("fence8.in","r",stdin);
110     freopen("fence8.out","w",stdout);
111     init();
112     binary();
113     return 0;
114 }