USACO Network of Schools

本题是关于有向图联通性的问题，对于第一问，很容易想到下面的算法：

先提取出所给图中的所有强联通分量（维基百科），然后把在同一个SCC中的点都视为一个点（因为SCC内部的点都可以互相联通），建立一个新的图（这个步骤也叫做“缩点（contraction）”）。缩点的时候要注意排除自环和重边。
接着，检查新图中的所有点，如果发现入度为0的点，那么一定要给这个学校（或者叫学校组）送一份软件。因此，任务A的答案就是入度为0的点的个数。

对于B任务，就需要动一些脑筋了。我们可以换一种方式描述B任务：
对缩点后的图进行操作，添加最少的边，让图中的所有点可以相互联通。
这不就是要我们添加最少的边，让这个图变成一个强联通图。

所以，如果原来的图已经是强联通图（缩点后只有一个点），则输出0即可。那么对于还不是强联通的图呢？

先让我们看一看一强联通图都有什么性质：
要是某个点可以到达所有其他点，那么这个点的出度一定不为0；
同理，每个点的入度也不能为0。

那么，是不是说对于一个缩点后的图（图中已经没有联通分量了）只要满足上面的条件就可以成为强联通图呢？答案是肯定的，读者可以自行验证（Linux下没有比较好的免费做图工具）。

就此，B任务的算法也很明白了：
用两个变量分别存储新图中出度为0、入度为0的点的个数。然后输出较大的那个即可。

B任务的算法要感谢BYVoid的文章。

代码中的Kosaraju算法是参考维基百科的伪代码写的，那个栈是完全没有必要的。
更简单的算法请看NOCOW。

关于B任务算法的正确性粗略证明：
根据强联通分量的性质，缩点后的图一定不存在强联通分量了，因此，也不存在环。所以，缩点后的图是一个或者多个有向无还图（还可能含有孤点），因此，只要让每个点都有入度和出度就可以实现全部强联通。

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #include <assert.h>
005 #define MAXNODE 102
006
007 typedef struct node
008 {
009     int v;
010     struct node *next;
011 }NODE;
012
013 NODE *first[MAXNODE],*reverse[MAXNODE];   //adjcent list
014 int N;
015 int scc[MAXNODE];  //SCC
016 int visit[MAXNODE];   //for DFS use
017 int stack[MAXNODE];
018 int instack[MAXNODE];
019 int top;
020 int cnt;  //scc number
021 int adj[MAXNODE][MAXNODE];   //SCC matrix
022 int indeg[MAXNODE],outdeg[MAXNODE];  //in/outdegree of every component
023
024 void addedge(NODE **arr,int u,int v)  //edge from u to v
025 {
026     NODE *p;
027     p = malloc(sizeof(NODE));
028     p->v = v;
029     p->next = arr[u];
030     arr[u] = p;
031 }
032
033 void init()
034 {
035     scanf("%d\n",&N);
036     int i,v;
037     for(i = 1;i <= N;i ++)
038         while(1)
039         {
040             scanf("%d",&v);
041             if(v == 0)    break;
042             addedge(first,i,v);
043             addedge(reverse,v,i);
044         }
045 }
046
047 void push(int v)
048 {
049     stack[top ++] = v;
050 }
051
052 int pop()
053 {
054     assert(top > 0);
055     return stack[--top];
056 }
057
058 void dfs_1(int v)
059 {
060     NODE *p;
061     visit[v] = 1;
062     for(p = first[v];p != NULL;p = p->next)
063         if(!visit[p->v])    dfs_1(p->v);
064     push(v);  //put into stack when all finished
065     instack[v] = 1;
066 }
067
068 void dfs_2(int v)
069 {
070     NODE *p;
071     visit[v] = 1;
072     instack[v] = 0;
073     scc[v] = cnt;
074     for(p = reverse[v];p != NULL;p = p->next)
075         if(!visit[p->v])
076             dfs_2(p->v);
077 }
078
079 void debug2()
080 {
081     int i;
082     for(i = 1;i <= N;i ++)
083         fprintf(stderr,"%d->%d\n",i,scc[i]);
084 }
085
086 void ptnode(NODE **arr,int v)   //debug use
087 {
088     NODE *p;
089     printf("%d -> ",v);
090     for(p = arr[v];p != NULL;p = p->next)
091         printf("%d ",p->v);
092     printf("\n");
093 }
094
095 void newgraph()    //taking SSC as a node, create a new graph
096 {
097     int i,j;
098     NODE *p;
099     memset(adj,0,sizeof(adj));
100     memset(indeg,0,sizeof(indeg));
101     for(i = 1;i <= N;i ++)
102         for(p = first[i];p != NULL;p = p->next)
103         {
104             if(scc[i] != scc[p->v] && adj[scc[i]][scc[p->v]] == 0)
105             {
106                 adj[scc[i]][scc[p->v]] = 1;
107                 outdeg[scc[i]] ++;
108                 indeg[scc[p->v]] ++;
109             }
110         }
111     /*
112     for(i = 1;i <= cnt;i ++)
113         for(j = 1;j <= cnt;j ++)
114             if(adj[i][j])    fprintf(stderr,"%d->%d\n",i,j);
115     */
116 }
117
118 void task_1()
119 {
120     int i;
121     int ans = 0;
122     for(i = 1;i <= cnt;i ++)
123     {
124         //fprintf(stderr,"INDEG[%d]=%d\n",i,indeg[i]);
125         if(indeg[i] == 0)    ans ++;
126     }
127     printf("%d\n",ans);
128 }
129
130 void dfs_mark(int v)
131 {
132     visit[v] = 1;
133     int i;
134     for(i = 1;i <= cnt;i ++)
135         if(adj[v][i] && !visit[i])    dfs_mark(i);
136 }
137
138 void task_2()
139 {
140     if(cnt == 1)
141         {printf("0\n");return;}
142     int i,ans;
143     int in,out;
144     in = out = 0;
145     for(i = 1;i <= cnt;i ++)
146     {
147         if(indeg[i] == 0)    in ++;
148         if(outdeg[i] == 0)    out ++;
149     }
150     if(in > out)    ans = in;
151     else ans = out;
152     printf("%d\n",ans);
153 }
154
155 int main()
156 {
157     int i;
158     freopen("schlnet.in","r",stdin);
159     freopen("schlnet.out","w",stdout);
160     init();
161     top = cnt = 0;
162     memset(visit,0,sizeof(visit));
163     for(i = 1;i <= N;i ++)
164         if(!visit[i])    dfs_1(i);
165     memset(visit,0,sizeof(visit));
166     while(top > 0)  //while stack is not empty
167     {
168         i = pop();
169         if(instack[i] == 0)    continue;
170         cnt ++;
171         dfs_2(i);
172     }
173     newgraph();
174     task_1();
175     task_2();
176     return 0;
177 }

USACO Big Barn

看到这个题目，最先想到的就是使用动态规划了，不过动态规划也要选合适的状态表示法。

本人最初这样表示状态：

用havetree[i][j][l]（实际上只要i，j）表示以（i，j）为左上角，l为边长的正方形内是否有树。

那么转移方程就是

if(havetree[i][j][l] == 1)     havetree[i][j][l + 1] = 1

else if(新扩展的两个边都没有树)             havetree[i][j][l + 1] = 1

最后输出有 havetree[i][j][l]=0的l的最大值即可。

然而，上面的算法只能通过前9个测试点。想到如果在一个正方形的右、下、右下方分别放置同样大小的正方形，可以把边长扩大为2×l。因此，代码中就多了一段Fast expand的过程。

代码如下：

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 _Bool bak[1001][1001] = {};
006 _Bool havetree[1001][1001] = {};
007 _Bool map[1001][1001] = {};
008 int N,T;
009
010 void init()
011 {
012     int i,j;
013     scanf("%d%d\n",&N,&T);
014     while(T --)
015     {
016         scanf("%d%d\n",&i,&j);
017         map[i - 1][j - 1] = 1;
018     }
019 }
020
021 int check_edge(int i,int j,int l)
022 {
023     int k;
024     for(k = i;k < i + l - 1;k ++)
025     {
026         if(map[k][j + l - 1] == 1)    return 1;
027     }
028     for(k = j;k <= j + l - 1;k ++)
029     {
030         if(map[i + l - 1][k] == 1)    return 1;
031     }
032     return 0;
033 }
034
035 void debug()
036 {
037     int i,j;
038     for(i = 0;i < N;i ++)
039     {
040         for(j = 0;j < N;j ++)    printf("%2d",(int)havetree[i][j]);
041         putchar('\n');
042     }
043 }
044
045 void terminate()
046 {
047     fclose(stdin);
048     fclose(stdout);
049     exit(0);
050 }
051
052 int main()
053 {
054     freopen("bigbrn.in","r",stdin);
055     freopen("bigbrn.out","w",stdout);
056     init();
057     int l,i,j;
058     int success;
059     int max = 0;
060     //max = 0 or 1 exception
061     for(i = 0;i < N;i ++)
062         for(j = 0;j < N;j ++)
063         {
064             if(map[i][j] == 0)    max = 1;
065             havetree[i][j] = map[i][j];
066         }
067     if(max == 0)    {printf("%d\n",max);terminate();}
068     //Fast expand
069     for(l = 2;l <= N;l *= 2)
070     {
071         memcpy(bak,havetree,sizeof(bak));
072         success = 0;
073         for(i = 0;i < N;i ++)
074         {
075             if(i + l - 1>= N)    continue;
076             for(j = 0;j < N;j ++)
077             {
078                 if(j + l - 1 >= N)    continue;
079                 if(havetree[i][j])    continue;
080                 if(havetree[i + (l >> 1)][j] || havetree[i + (l >> 1)][j + (l >> 1)] || havetree[i][j + (l >> 1)])
081                     havetree[i][j] = 1;
082                 else
083                 {
084                     max = l;
085                     success = 1;
086                 }
087             }
088         }
089         if(!success)  //all extensions failed
090         {
091             memcpy(havetree,bak,sizeof(havetree));
092             break;
093         }
094     }
095     fprintf(stderr,"%d\n",max);
096     for(l = max + 1;l <= N;l ++)
097     {
098         success = 0;
099         for(i = 0;i < N;i ++)
100         {
101             if(i + l - 1>= N)    continue;
102             for(j = 0;j < N;j ++)
103             {
104                 if(j + l - 1 >= N)    continue;
105                 if(havetree[i][j])    continue;
106                 if(check_edge(i,j,l))
107                     havetree[i][j] = 1;
108                 else
109                 {
110                     max = l;
111                     success = 1;
112                 }
113             }
114         }
115         if(!success)    break;
116     }
117     //debug();
118     printf("%d\n",max);
119     return 0;
120 }

可是呢，上面的代码只能通过前10个测试点，因为上面的算法在极端情况下会达到n^4的时间规模。于是放弃上面的状态表示法。忍不住看了题解后，采用max[i][j]表示以(i,j)为左上顶点的没有树的正方形的最大边长。

因此有转移方程：
if((i,j)不是树)
    max[i][j] = min(max[i-1][j],max[i][j-1],max[i-1][j-1]) + 1;
顺利通过全部数据。

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04
05 int max[1002][1002] = {};
06 _Bool map[1002][1002] = {};
07 int N,T;
08
09 void init()
10 {
11     int i,j;
12     scanf("%d%d\n",&N,&T);
13     while(T --)
14     {
15         scanf("%d%d\n",&i,&j);
16         map[i][j] = 1;
17     }
18 }
19
20 void dp()
21 {
22     int i,j;
23     int tmp;
24     for(i = 1;i <= N;i ++)
25         for(j = 1;j <= N;j ++)
26         {
27             if(map[i][j])    max[i][j] = 0;
28             else max[i][j] = 1;
29         }
30     for(i = N;i > 0;i --)
31         for(j = N;j > 0;j --)
32             if(map[i][j] == 0)
33             {
34                 tmp = N + 1;
35                 if(max[i + 1][j] < tmp)    tmp = max[i + 1][j];
36                 if(max[i][j + 1] < tmp)    tmp = max[i][j + 1];
37                 if(max[i + 1][j + 1] < tmp)    tmp = max[i + 1][j + 1];
38                 max[i][j] = tmp + 1;
39             }
40     int ans = 0;
41     for(i = 0;i < N;i ++)
42         for(j = 0;j < N;j ++)
43             if(max[i][j] > ans)    ans = max[i][j];
44     printf("%d\n",ans);
45 }
46
47 int main()
48 {
49     freopen("bigbrn.in","r",stdin);
50     freopen("bigbrn.out","w",stdout);
51     init();
52     dp();
53     fclose(stdout);
54     return 0;
55 }

USACO Milk Measuring

首先，对输入的pail从小到大排序。
然后，使用DFSID，不断加深搜索深度（即使用pail的个数）。当深度为0时，用动态规划（也就是完全背包算法）检查DFS得到的pail是否可以量出Q的牛奶，如果可以就输出当前使用的pail。

程序的最长运行时间约0.2s。如果在枚举DFS深度时使用二分可以进一步优化。
 

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAX_LENGTH 10001
05 #define MAX_MILK 20001
06
07 int Q,P;
08 int pail[100];
09 _Bool use[100];
10 _Bool solution[100];
11 int success;
12
13 void init()
14 {
15     static _Bool avail[MAX_LENGTH];
16     memset(avail,0,sizeof(avail));
17     scanf("%d\n%d\n",&Q,&P);
18     int i,t;
19     for(i = 0;i < P;i ++)
20     {
21         scanf("%d\n",&t);
22         avail[t] = 1;
23     }
24     int p;
25     for(p = i = 0;i < MAX_LENGTH;i ++)
26         if(avail[i])    pail[p ++] = i;
27 }
28
29 int try()
30 {
31     static _Bool can[MAX_MILK];   //similar to knapsack problem
32     int i,j;
33     memset(can,0,sizeof(can));
34     can[0] = 1;
35     for(i = 0;i < Q;i ++)
36         if(can[i])
37             for(j = 0;j < P;j ++)
38                 if(use[j] && i + pail[j] <= Q)    can[i + pail[j]] = 1;
39     return (int)can[Q];
40 }
41
42 void dfs(int k,int d)
43 {
44     if(success)    return;
45     if(d == 0)
46     {
47         if(try())
48         {
49             memcpy(solution,use,sizeof(solution));
50             success = 1;
51         }
52         return;
53     }
54     if(k == P)    return;
55     use[k] = 1;
56     dfs(k + 1,d - 1);
57     use[k] = 0;
58     if(k <= P - d)    dfs(k + 1,d);
59 }
60
61 void single()
62 {
63     int i;
64     for(i = 0;i < P;i ++)
65         if(Q % pail[i] == 0)
66         {
67             printf("1 %d\n",pail[i]);
68             fclose(stdout);
69             exit(0);
70         }
71 }
72
73 int main()
74 {
75     int d;
76     freopen("milk4.in","r",stdin);
77     freopen("milk4.out","w",stdout);
78     init();
79     single();   //try if just one pail meets the needs
80     for(d = 2;d <= P;d ++)
81     {
82         success = 0;
83         memset(use,0,sizeof(use));
84         dfs(0,d);
85         if(success)
86         {
87             printf("%d",d);
88             break;
89         }
90     }
91     int i;
92     for(i = 0;i < P;i ++)
93         if(solution[i])    printf(" %d",pail[i]);
94     printf("\n");
95     fclose(stdout);
96     return 0;
97 }