USACO DEC09 Cow Toll Paths

这题的难点在于如何处理点的权值对最小费用路径的影响。本人也是在看了题解后才弄明白的。

需要用到两个二维数组:cost,dist
dist[i][j]表示i到j的传统意义上的距离
cost[i][j]表示i到j的费用

那么就有cost[i][j] = dist[i][j] + 路径上点的C最大值。

然而，我们并不能在求出最短路前预先知道路径上那个点的C最大啊。既然这样不行，那么我们就指定一个C最大的点吧。

因此，把所有点按照C从小到大排序。然后，对Floyd进行如下修改：让最外层循环的点k的C保持递增，那么对于内层的i和j，max(C[i],C[j],C[k])就是当前路径上C的最大值了。不断更新dist和cost数组。最后读入请求输出对应cost中的值即可。

这个算法用到了Floyd的一个很有趣性质，本人将在以后的文章中进行更深入的探究。

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 260
#define INF 1000000000

long dist[MAXN][MAXN];
long cost[MAXN][MAXN];
long c[MAXN],v[MAXN];
int N,M,K;

void init()
{
   int i,j,a,b;
   long t;
   scanf("%d%d%d",&N,&M,&K);
   for(i = 1;i <= N;i ++)
       for(j = 1;j <= N;j ++)
           dist[i][j] = cost[i][j] = INF;
   for(i = 1;i <= N;i ++)
   {
       scanf("%ld",&c[i]);
       v[i] = i;
   }
   for(i = 1;i <= M;i ++)
   {
       scanf("%d%d%ld",&a,&b,&t);
       if(dist[a][b] > t)
           dist[a][b] = dist[b][a] = t;
   }
   for(i = 1;i <= N;i ++)
       for(j = i + 1;j <= N;j ++)
           if(c[v[i]] > c[v[j]])
           {
               t = v[i];v[i] = v[j];v[j] = t;
           }
}

inline long getmax(long a,long b)
{
   if(a > b)    return a;
   return b;
}

void floyd()
{
   int i,j,t,k;
   for(t = 1;t <= N;t ++)
   {
       k = v[t];
       for(i = 1;i <= N;i ++)
           for(j = 1;j <= N;j ++)
           {
               if(dist[i][j] > dist[i][k] + dist[k][j])
                   dist[i][j] = dist[i][k] + dist[k][j];
               if(cost[i][j] > dist[i][j] + getmax(getmax(c[i],c[j]),c[k]))
                   cost[i][j] = dist[i][j] + getmax(getmax(c[i],c[j]),c[k]);
           }
   }
}

void output()
{
   int i,a,b;
   for(i = 1;i <= K;i ++)
   {
       scanf("%d%d",&a,&b);
       printf("%ld\n",cost[a][b]);
   }
}

int main()
{
   freopen("toll.in","r",stdin);
   freopen("toll.out","w",stdout);
   init();
   floyd();
   output();
   fclose(stdout);
   return 0;
}

USACO DEC09 Dizzy Cows

题目的大意就是确定输入的无向边的方向，使得所有无向边加入后依然是一个有向无环图。

思路很直接，先把所有的有向边加入图中，运行一次拓扑排序。如果不能排序，那么原图就有环，输出“-1” 并退出。然后，读入每条无向边(a,b)，若在拓扑序列中a在b前面，则方向为a指向b，否则为b指向a。

由于有多个解，USACO只给了输入数据，没有给输出数据。故本人增加了一个函数check，用于检查程序输出是否正确。

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 100010

typedef struct node
{
   long v;
   struct node *next;
}node;

long in[MAXN] = {};  //入度
long Q[MAXN];
long N,M,K;
node space[MAXN];
long empty = 0;
node *first[MAXN];

long pos[MAXN];   //点在拓扑序中的位置

void init()
{
   scanf("%ld%ld%ld\n",&N,&M,&K);
   long i,a,b;
   for(i = 0;i < M;i ++)
   {
       scanf("%ld%ld\n",&a,&b);
       space[empty].v = b;
       space[empty].next = first[a];
       first[a] = space + empty;
       empty ++;
       in[b] ++;
   }
}

void toposort()
{
   node *p;
   long i,head,tail;
   head = tail = 0;
   for(i = 1;i <= N;i ++)
       if(in[i] == 0)    Q[tail ++] = i;
   while(head < tail)
   {
       i = Q[head ++];
       for(p = first[i];p != NULL;p = p->next)
       {
           in[p->v] --;
           if(in[p->v] == 0)
               Q[tail ++] = p->v;
       }
   }
   if(tail < N)
   {
       printf("-1\n");
       exit(0);
   }
   for(i = 0;i < tail;i ++)
       pos[Q[i]] = i;
}

void add(long a,long b)   //用于测试
{
   node *p = malloc(sizeof(node));
   p->v = b;
   p->next = first[a];
   first[a] = p;
}

void check()   //用于测试
{
   node *p;
   int i,head,tail;
   memset(in,0,sizeof(in));
   for(i = 1;i <= N;i ++)
       for(p = first[i];p != NULL;p = p->next)
           in[p->v] ++;
   head = tail = 0;
   for(i = 1;i <= N;i ++)
       if(in[i] == 0)    Q[tail ++] = i;
   while(head < tail)
   {
       i = Q[head ++];
       for(p = first[i];p != NULL;p = p->next)
       {
           in[p->v] --;
           if(in[p->v] == 0)
               Q[tail ++] = p->v;
       }
   }
   if(head == N && tail == N)    fprintf(stderr,"Correct!\n");
   else    fprintf(stderr,"Wrong!\n");
}

void arrange()
{
   long i,a,b;
   for(i = 0;i < K;i ++)
   {
       scanf("%ld%ld",&a,&b);
       if(pos[a] < pos[b])
       {
           printf("%ld %ld\n",a,b);
           add(a,b);
       }
       else
       {
           printf("%ld %ld\n",b,a);
           add(b,a);
       }
   }
}

int main()
{
   freopen("dizzy.in","r",stdin);
   freopen("dizzy.out","w",stdout);
   init();
   toposort();
   arrange();
   check();
   fclose(stdin);
   fclose(stdout);
   return 0;
}

USACO NOV09 Lights

由于灯的上限是35个，因此可以用一个64位整型表示整个状态，二进制1表示灯亮，0表示灯灭。那么，初始状态就是0,目标状态(target)就是(1 << N)-1.
同样，也可以把每个开关改变的灯记录在一个64位整型数组op里，按下开关i后的新状态就等于当前状态xor op[i].

由于xor具有自反性和交换性，因此无需考虑按开关的顺序，每个开关也最多只按一次，否则效果就抵消了。因此很容易写出下面的搜索函数：

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

void dfs(unsigned long long s,int p,int i)
{
   if(success)     return;
   if(p == depth)        //p表示按下开关的数量
   {
       if(s == target)      success = 1;
       return;
   }
   if(i == N)
       return;
   dfs(s,p,i + 1);   //不按开关
   dfs(s ^ op[i],p + 1,i + 1);     //按开关
}

依次增加depth，并运行dfs(0,0,0)，直到success为真，此时的depth就是答案。不过，这个DFS的复杂度是2^N方的，在N=20以下都可以迅速出解，当N=30时就严重超时了。

如何降低复杂度呢？我们要寻找的是一个满足0 xor op[t1] xor op[t2] xor .... xor op[tk] = target的序列，根据xor的交换律和结合律，我们可以把这个序列分成两半求解。本题的关键就在这里。

USACO All Latin Squares

这是一道相当令人不爽的一道题目。容易看出核心算法是DFS，可是，需要剪枝...

最直观的剪枝：
当前面N-1行都确定后，最后一行也就确定了，因此，可以直接回溯。
使用这个剪枝后，在N=6时耗时约0.9s，勉强通过。N=7时，用了20min也没有算出来。T_T

有一定技巧的剪枝：
以N=5为例，有下面一个解：

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

那么，如果我们把第2行和第4行交换，根据题义，得到的方形也是满足要求的。
因此，只要算出一种情况，然后把总数×(N-1)！就可以得出解了。
如何做到这种效果呢？
这里用到了一个方法——化无序为有序：把第一列强制设定为1、2、3、4、5，然后DFS即可。
当和第一个剪枝一起使用时，N=6时耗时接近0s，不过N=7依然要耗费约20s。需要进一步改进。

奇异的剪枝：
经本人尝试，可以在DFS前填充（2,2）位置的数字，第一次填1，做一遍DFS后改成3，根据两个数据就可以求出总数了。
这个剪枝可以把N=7的运行时间缩短到6s左右。

离奇的剪枝：
带有一点记忆化的思想，貌似和置换群有些关系，本人也是看了题解才知道的，详见代码了。

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N;
int row[10],col[10];
int map[10];   //the second row
int t;
long long tmp_cnt;
long long cnt[10][10] = {};
long long ans = 0;
int cycle_cnt,cycle_product;
int idx;

void calc_idx()
{
   int l,k,j;
   static int v[10];
   cycle_cnt = 0;
   cycle_product = 1;
   memset(v,0,sizeof(v));
   for(k = 1;k <= N;k ++)
   {
       if(v[k])    continue;
       v[k] = 1;
       l = 1;
       for(j = map[k];j != k;j = map[j])
       {
           v[j] = 1;
           l ++;
       }
       cycle_cnt ++;
       cycle_product *= l;
   }
}

void dfs(int r,int c)
{
   if(r == N)
   {
       tmp_cnt ++;
       return;
   }
   int i;
   for(i = 1;i <= N;i ++)
   {
       if((((row[r] | col[c]) >> i) & 1) == 0)
       {
           row[r] |= (1 << i);
           col[c] |= (1 << i);
           if(c == N)
           {
               dfs(r + 1,2);
           }
           else
           {
               dfs(r,c + 1);
           }
           col[c] ^= (1 << i);
           row[r] ^= (1 << i);
       }
   }
}

void map_init()
{
   int i;
   for(i = 1;i <= N;i ++)
   {
       col[i] = 1 << i;
       row[i] = 1 << i;
   }
   col[1] = 0xFFFF;
   row[1] = 0xFFFF;
   map[1] = 2;
}

long long fac(int n)
{
   long long a = 1;
   while(n > 1)
   {
       a *= n;
       n --;
   }
   return a;
}

void pre(int k)
{
   int i;
   if(k == N + 1)
   {
       calc_idx();
       if(cnt[cycle_cnt][cycle_product] > 0)
       {
           ans += cnt[cycle_cnt][cycle_product];
       }
       else
       {
           tmp_cnt = 0;
           dfs(3,2);
           cnt[cycle_cnt][cycle_product] = tmp_cnt;
           ans += tmp_cnt;
       }
       return;
   }
   for(i = 1;i <= N;i ++)
   {
       if((((row[2] | col[k]) >> i) & 1) == 0)
       {
           row[2] |= (1 << i);
           col[k] |= (1 << i);
           map[k] = i;
           pre(k + 1);
           row[2] ^= (1 << i);
           col[k] ^= (1 << i);
       }
   }
}

int main()
{
   freopen("latin.in","r",stdin);
   freopen("latin.out","w",stdout);
   scanf("%d",&N);
   map_init();
   if(N >= 5)
   {
       pre(2);
       printf("%lld\n",ans * fac(N - 1));
   }
   else
   {
       tmp_cnt = 0;
       dfs(2,2);
       printf("%lld\n",tmp_cnt * fac(N - 1));
   }
   return 0;
}

USACO MAR11 Bovine Bridge Battle

Problem 8: Bovine Bridge Battle [Richard Ho, 2007]

Each of Farmer John's N (4 <= N <= 1,000) cows is patiently waiting
in the main pasture with cow i at point with integer coordinates
(X_i, Y_i) (-1,000,000,000 <= X_i <= 1,000,000,000; -1,000,000,000
<= Y_i <= 1,000,000,000).

The cows wish to form into groups of four in order to play Bridge,
their new favorite card game. Each group must satisfy an important
constraint: four cows are allowed to team up if and only if there
exists some point X somewhere in the plane (and not coincident with
any of the four points of the potential group of four) such that
rotating any of the group's cows 180 degrees about that point X
gives the position of some other cow in the group.

Please help the cows determine the number of sets of four cows that
can form a Bridge group.

By way of example, suppose eight cows are standing at eight points:

                  |
                 f*
                  |             a = (-3, 1)    e = (-1, 1)
           b*     |             b = (-2, 2)    f = ( 0, 3)
        a      e  |             c = (-3, 0)    g = ( 2, 0)
         *     *  |             d = (-2, 0)    h = ( 3, 0)
         c  d     |     g  h
---------*--*-----+-----*--*---------
                  |

Then the three legal sets of four cows are {a, b, e, d} (they rotate
around point (-2, 1)), {b, c, e, f} (around the point (-1.5, 1.5)),
and {c, d, g, h} (around (0,0)).

The supplied locations of the cows given are all distinct, although
they are supplied in no particular order. Furthermore, the answer
will fit into a signed 32-bit integer.

PROBLEM NAME: rotsym

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: X_i
        and Y_i

SAMPLE INPUT (file rotsym.in):

8
-3 0
-2 0
-1 1
0 3
2 0
-3 1
3 0
-2 2

OUTPUT FORMAT:

* Line 1: A single integer that is the number of sets of 4 cows that
        form valid groups for bridge.

SAMPLE OUTPUT (file rotsym.out):

3

**********************************************************************

显然，直接4个for嵌套是绝对超时的。题目要求转180度后对称，那么，我们可以求出每两点之间连线的中点坐标，如果两个线段的中点坐标相等，那么它们上面的4点就满足条件。

由于计算中点坐标时需要用到除以2的操作，因此可能造成0.5出现。由于我们需要的不是中点坐标，只要中点坐标相等的线段，因此除以2可以直接忽略。

本人最初使用Hash表把点映射到正整数，然后用数组cnt[i]记录以标号i的点为中点的线段条数。那么答案就是Sigma{cnt[i] * (cnt[i] - 1) / 2}。不过Hash表消耗的内存较大，超过了16MB的限制。后来改用排序后扫描的办法，就顺利通过了。

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

06 
07 #include <stdio.h>
08 #include <stdlib.h>
09 #include <string.h>
10 #include <math.h>
11 
12 typedef struct
13 {
14     long x,y;
15 }POINT;
16 
17 int N;
18 POINT pos[1002];
19 POINT c[1002 * 1002 / 2];
20 
21 int pcmp(const void *a,const void *b)
22 {
23     POINT *m,*n;
24     m = (POINT *)a;n = (POINT *)b;
25     if(m->x > n->x)    return 1;
26     if(m->x == n->x && m->y > n->y)    return 1;
27     return -1;
28 }
29 
30 void solve()
31 {
32     long i,j;
33     long ans = 0;
34     long t = 0;
35     for(i = 0;i < N;i ++)
36         for(j = 0;j < i;j ++)
37         {
38             c[t].x = (pos[i].x + pos[j].x);
39             c[t].y = (pos[i].y + pos[j].y);
40             t ++;
41         }
42     //sort and then figure how many are the same
43     qsort(c,t,sizeof(POINT),pcmp);
44     long cnt = 1;
45     for(i = 1;i < t;i ++)   //be careful with cnt here
46     {
47         if(c[i].x == c[i - 1].x && c[i].y == c[i - 1].y)
48             cnt ++;
49         else
50         {
51             ans += cnt * (cnt - 1) / 2;
52             cnt = 1;
53         }
54     }
55     printf("%ld\n",ans);
56 }
57 
58 int main()
59 {
60     freopen("rotsym.in","r",stdin);
61     freopen("rotsym.out","w",stdout);
62     scanf("%d\n",&N);
63     int i;
64     for(i = 0;i < N;i ++)
65         scanf("%ld%ld\n",&pos[i].x,&pos[i].y);
66     solve();
67     fclose(stdout);
68     return 0;
69 }

USACO OPEN11 Learning Languages

Farmer John's N (2 <= N <= 10,000) cows, conveniently numbered 1..N,
are fluent in some M (1 <= M <= 30,000) languages, also conveniently
numbered from 1..M. Cow i can speak in K_i (1 <= K_i <= M) languages,
namely L_i1, L_i2,..., L_{iK_i} (1 <= L_ij <= M). FJ's cows aren't
THAT smart, so the sum of K_i over all cows i is at most 100,000.

Two cows can't directly talk to each other unless both speak a
common language. However, cows can pass messages along, translating
if necessary. In other words, cows A and B can have a conversation
if and only if there exists a sequence of cows T_1, T_2, ..., T_k
such that A and T_1 share a language, T_1 and T_2 share a language,
etc., and T_k and B share a language.

Farmer John wishes that his cows could be even more social, so he
wants all his cows to be able to socialize with any other cow. He
can buy books to teach any one of his cows any language he pleases.
Being a fairly frugal farmer, FJ wants to purchase the minimum
number of books necessary to enable all of his cows to speak to
each other. Help him determine:

    * The minimum number of books he must purchase

    * Any set of books assigned to cows in any order which will
      help him meet this goal; a program will grade your output.

By way of example, suppose there are three cows named Alberta,
Bessie, and Contessa along with three languages denoted as #1, #2,
and #3. Alberta can speak languages #2 and #3, Bessie can speak
language #2, and Contessa can speak language #1. Currently, Alberta
and Bessie can talk to each other, but Contessa is left alone.

                   #1   #2   #3
       Alberta           x    x
       Bessie            x
       Contessa     x

FJ wants to fix this situation, so he can buy Contessa a book to
teach her language #2. This will ensure all cows speak the same
language, so they can all communicate with one another.

Note that an alternate solution exists: instead, FJ could buy
Contessa a book to teach her language #3. Not all cows would speak
the same language, but this would still be a valid solution because
Contessa could communicate through Alberta (who also speaks language
#3) if she wants to talk to Bessie. Other alternatives exist, and any
valid alternate solution will also be accepted.

PROBLEM NAME: llang

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes the languages that cow i can speak
        with (K_i)+1 space-separated integers: K_i, L_i1,
        L_i2,...,L_i{K_i}.

SAMPLE INPUT (file llang.in):

3 3
2 3 2
1 2
1 1

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of books that FJ
        must purchase.

* Lines 2..B+1: Line i+1 contains two space-separated integers: the
        language id # and the id # of the cow to receive book i. If
        multiple solutions exist, print any one.

SAMPLE OUTPUT (file llang.out):

1
2 3

**********************************************************************

本人使用并查集解决这个问题。

先用M个链表保存会某个语言的牛的编号。然后把会相同语言的牛全部merge掉。最后

统计联通分量的个数ccnt。所需要的最少的书本数就是ccnt-1.

对于安排书本，本人是这样解决的。由上一步可知，不同联通分量之间一定不不存在

相同的语言。因此，任意选取一个被某个联通分量中的牛掌握的语言，然后把ccnt-1

本书分别安排到其他每个联通分量中。 

处理无向图联通性的问题经常使用到并查集。

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAXN 100005
05
06 typedef struct node
07 {
08    struct node *next;
09    long v;
10 }node;
11
12 long N,M;
13 long fa[MAXN];   //并查集
14 node *head[30002] = {};   //链表
15 _Bool vis[MAXN] = {};    //辅助数组，判断某个联通分量是否被访问过
16
17 void add(long lang,long v)
18 {
19    node *p = malloc(sizeof(node));
20    p->v = v;
21    p->next = head[lang];
22    head[lang] = p;
23 }
24
25 long getfa(long x)
26 {
27    if(fa[x] != x)
28        fa[x] = getfa(fa[x]);
29    return fa[x];
30 }
31
32 void init()
33 {
34    scanf("%ld%ld\n",&N,&M);
35    long i,k,lang;
36    for(i = 1;i <= N;i ++)
37    {
38        scanf("%ld",&k);
39        while(k --)
40        {
41            scanf("%ld",&lang);
42            add(lang,i);
43        }
44    }
45 }
46
47 void solve()
48 {
49    long i,x,first;
50    long ccnt = 0;
51    node *p;
52    for(i = 1;i <= N;i ++)
53        fa[i] = i;
54    for(i = 1;i <= M;i ++)
55    {
56        if(head[i] != NULL)
57            x = getfa(head[i]->v);
58        for(p = head[i];p != NULL;p = p->next)
59            fa[getfa(p->v)] = x;
60    }
61    for(i = 1;i <= N;i ++)
62    {
63        x = getfa(i);
64        if(!vis[x])
65        {
66            vis[x] = 1;
67            ccnt ++;
68        }
69    }
70    printf("%ld\n",ccnt - 1);
71    for(x = 1;x <= M && head[x] == NULL;x ++);  //find the first lang known by at least one cow
72    first = getfa(head[x]->v);
73    memset(vis,0,sizeof(vis));
74    vis[first] = 1;
75    for(i = 1;i <= N;i ++)
76        if(!vis[getfa(i)])
77        {
78            vis[getfa(i)] = 1;
79            printf("%ld %ld\n",x,i);
80        }
81 }
82
83 int main()
84 {
85    freopen("llang.in","r",stdin);
86    freopen("llang.out","w",stdout);
87    init();
88    solve();
89    fclose(stdout);
90    return 0;
91 }