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;
}

一个有关最小生成树的问题

题目来源：NOI导刊，NOIP模拟试题九

题目描述：输入一个联通的无向图，对于每条边，判断这条边是属于这张图的任意一个MST、至少一个MST还是不属于任何一个MST。对应输出"any","at least one","none"。

这个问题看上去有些复杂，不过，可以确定这一点：无向图中的桥一定在每个MST中。

接着，让我们从Kruskal算法的角度分析一下。Kruskal先把边按照边权递增排序，使用并查集记录每个点属于的联通分量，如果扫描到一条边的两个点不属于同一个联通分量，那么就把这条边加入MST中，并合并两个顶点所在的联通分量。

可见，对于同一个无向图，Kruskal给出的MST的结果很大程度上取决于排序的结果，如果使用稳定的排序算法对边表排序，那么Kruskal输出的结果是唯一的。如果使用随机化快排，当存在权值相等的边时，Kruskal给出的MST就不是一成不变的了。

我们就从这里下手。

新建一张空图G。在边表中找出所有边权为w的边，保存在list中，用Kruskal合并所有边权小于w的安全边。然后，依次扫描list中的所有边(i,j)，如果i和j在同一个联通分量中，那么，显然这条边一定不属于任何一MST。否则，这条边就属于某个MST，并把这条边（两端点要改成原端点所属的联通分量）加入G中。

接着，用Tarjan算法求出G中所有的桥，这些桥必然存在任意一个MST。

按照上面的方法对所有w都运行一遍，就可以获得结果了。

代码实现：

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 100005
#define MAXE 100005

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

typedef struct edge
{
   long u,v,w,ord;
}edge;

long N,M;
edge e[MAXE];

node *first[MAXN];
node space[MAXE * 3];
long empty;

long fa[MAXN];   //disjoint set
long dfsn[MAXN],low[MAXN];
long T;   //DFS time
int type[MAXE];

int ecmp(const void *a,const void *b)
{
   if(((edge *)a)->w > ((edge *)b)->w)    return 1;
   return -1;
}

inline void init_fa()
{
   long i;
   for(i = 1;i <= N;i ++)
       fa[i] = i;
}

long getfa(long x)
{
   if(fa[x] != x)
       fa[x] = getfa(fa[x]);
   return fa[x];
}

inline long getmin(long a,long b)
{
   if(a < b)    return a;
   return b;
}

void init()
{
   long i;
   scanf("%ld%ld",&N,&M);
   for(i = 0;i < M;i ++)
   {
       scanf("%ld%ld%ld",&e[i].u,&e[i].v,&e[i].w);
       e[i].ord = i;
   }
}

inline void addedge(long a,long b,long ord)
{
   space[empty].next = first[a];
   space[empty].v = b;
   space[empty].ord = ord;
   first[a] = space + empty;
   empty ++;
}

void tarjan(long x,long f)   //find bridges
{
   node *p;
   T ++;
   dfsn[x] = low[x] = T;
   for(p = first[x];p != NULL;p = p->next)
       if(p->ord != f)
       {
           if(dfsn[p->v] == 0)   //not visited yet
           {
               tarjan(p->v,p->ord);
               low[x] = getmin(low[x],low[p->v]);
               if(dfsn[x] < low[p->v])
                   type[p->ord] = 2;
           }
           else
               low[x] = getmin(low[x],dfsn[p->v]);
       }
}

void solve()
{
   long i,j,k,a,b;
   long addcnt = 0;
   qsort(e,M,sizeof(edge),ecmp);
   init_fa();
   for(i = 0;i < M && addcnt < N - 1;)
   {
       for(j = i;e[j].w == e[i].w;j ++);
       //e[i to j].w are the same
       for(k = i;k < j;k ++)
       {
           a = getfa(e[k].u);
           b = getfa(e[k].v);
           if(a != b)    //it's a safe edge
           {
               type[e[k].ord] = 1;   //in at least one MST
               first[a] = first[b] = NULL;   //make space for new graph
               dfsn[a] = dfsn[b] = low[a] = low[b] = 0;  //init for tarjan
           }
       }
       T = empty = 0;
       for(k = i;k < j;k ++)   //build new graph for tarjan to find bridges
       {
           if(type[e[k].ord] == 0)    continue;
           a = getfa(e[k].v);
           b = getfa(e[k].u);
           addedge(a,b,e[k].ord);
           addedge(b,a,e[k].ord);
       }
       for(k = i;k < j;k ++)
           if(dfsn[getfa(e[k].u)] == 0)  //not visited yet
               tarjan(getfa(e[k].u),-1);
       for(k = i;k < j;k ++)   //kruskal merge
       {
           a = getfa(e[k].u);
           b = getfa(e[k].v);
           if(a != b)
           {
               fa[a] = b;
               addcnt ++;
           }
       }
       i = j;
   }
}

void output()
{
   long i;
   for(i = 0;i < M;i ++)
   {
       switch(type[i])
       {
           case 1:printf("at least one\n");break;
           case 0:printf("none\n");break;
           case 2:printf("any\n");
       }
   }
}

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

实际代码为了提高效率，重复利用了结果，并没有完全按照前面的方法设计程序。
起初本人图方便，建空图时直接memset整个first数组，导致最后三个数据超时，改成first[a] = first[b] = NULL就全部通过了。可见虽然memset速度很快，但如果只要重置某几个数值，还是直接赋值更好。

Tarjan算法寻找无向图中的桥（割边）

桥的定义：
对于一个无向图，如果移除某一条边后，它的联通块的数量增加了，那么这条边就叫做桥，或者叫割边。也可以这么说，在无向图中，如果移除一条边之后，原来可以互达的两个点不再可达了，那么这个边就叫做桥。

根据定义，在联通的无向图中，要判断一条边是否是桥，只需要把这条边移除，然后从某个点遍历全图，如果遍历后还有点没有访问，那么这条边就是桥。这个算法的复杂度取决于遍历的复杂度，如果使用邻接表+BFS，则复杂度为O(|V| + |E|) .

同样的，要找出一张联通无向图的所有桥，可以用以上方法依次测试每条边。不过，复杂度就提升到O(|E|^2 + |V||E|)了，对于边数超过10000的图就不再适用了。

Tarjan算法可以在O(|E| + |V|) 的时间内求出无向图中所有的桥。基本框架如下：

ord表示一条边的标号，一条无向边拆成的两条有向边的ord相同。

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

void tarjan(long x,long f)
{
   node *p;
   T ++;
   dfsn[x] = low[x] = T;
   for(p = first[x];p != NULL;p = p->next)
       if(p->ord != f)
       {
           if(dfsn[p->v] == 0)   //还未访问
           {
               tarjan(p->v,p->ord);
               low[x] = getmin(low[x],low[p->v]);
               if(dfsn[x] < low[p->v])
                   cut[p->ord] = 1;
           }
           else
               low[x] = getmin(low[x],dfsn[p->v]);
       }
}

需要注意的是，上面函数的第二个参数f记录的是到达x点的边的标号，这样，即使存在重边，Tarjan也可以正常工作。如果f表示的是走到x的前一个点，那么重边会被误判为桥。

对于Tarjan算法是如何找出桥的，读者可以自己模拟。

下面是本人的思路：
由于使用DFS，因此遍历过的一定是一棵树。如果两个联通块之间只有一条路径（桥），那么DFS走过去之后就一定不会再走回来（除非退回来），并且由于Tarjan不允许直接从父亲更新（p->ord != f）。故桥两端的点i，j就会出现dfsn[i] < low[j]的情况。

一个奇怪的取数游戏

这是NOI导刊上的一道题目，题目是这么说的：

输入N个整数（它们的范围在-1000~+1000），它们顺次围成一个环。
在这N个数中取出M个数，条件是任意两个取出的数不能相邻，求它们的和的最大值。
如果不能按要求取出M个数，则输出Error!
N的范围是[10,200000]，M一定小于N。

显然，当M > N div 2时，就不能取出M个数了，因此直接退出。

容易想到一个动态规划的解法：
用f[i][j][0]表示不取第i个数，前i个数一共取出了j个数获得的和的最大值；
用f[i][j][1]表示取第i个数，前i个数一共取出了j个数获得的和的最大值。

显然
f[i][j][0] = max{f[i - 1][j][1],f[i - 1][j][0]}
f[i][j][1] = f[i - 1][j - 1][0]
稍微处理下环和边界情况就OK了。

不过呢，这个动态规划的时间复杂度是N^2级别的，对于200000的N是显然行不通的。

==================================================

导刊上给出了一个诡异的解法，用最大堆和双向链表。
首先，用双向链表记录每个位置前后的数的位置，构成一个环形链表。
与此同时，把所有数的编号加入最大堆。
然后，进行M次如下操作：

x = heap[0]
ans += value[x]
value[x] = value[left[x]] + value[right[x]] - value[x]
维护堆
把left[x]和right[x]从堆和双向链表中删去，并维护堆。

最后输出ans

其中value[x] = value[left[x]] + value[right[x]] - value[x]这句话是最关键的，请注意里面的减号，这说明如果某个值被加到了ans里面，在后面的操作中它还有可能被再次减去。就像用Ford-Fulkerson求最大流一样，某些边的流量反而会减小，但是S到T的流量是增加的。

如果按照这个算法，这道题完全可以转化成费用流解，关于如何转化本人还要思考下。

在编写这个程序的时候还有一个小插曲，起初只通过了一半的数据，检查发现每次修改堆中数据后，必须“马上”对堆进行调整，否则会破坏堆的结构。

按照惯例，给出代码：

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 400005
#define pa(x)    (((x) - 1) / 2)
#define lc(x)    ((x) * 2 + 1)
#define rc(x)    ((x) * 2 + 2)

long N,M;
long v[MAXN],heap[MAXN],heapsize,pos[MAXN];
long l[MAXN],r[MAXN];

void moveup(long x)   //x:the index in heap
{
   long tmp;
   while(x > 0 && v[heap[x]] > v[heap[pa(x)]])
   {
       tmp = heap[x];
       heap[x] = heap[pa(x)];
       heap[pa(x)] = tmp;
       tmp = pos[heap[x]];
       pos[heap[x]] = pos[heap[pa(x)]];
       pos[heap[pa(x)]] = tmp;
       x = pa(x);
   }
}

void movedown(long x)
{
   long s,tmp;
   s = x;
   while(1)
   {
       if(lc(x) < heapsize && v[heap[lc(x)]] > v[heap[s]])    s = lc(x);
       if(rc(x) < heapsize && v[heap[rc(x)]] > v[heap[s]])    s = rc(x);
       if(s != x)
       {
           tmp = heap[x];
           heap[x] = heap[s];
           heap[s] = tmp;
           tmp = pos[heap[x]];
           pos[heap[x]] = pos[heap[s]];
           pos[heap[s]] = tmp;
           x = s;
       }
       else break;
   }
}

int main()
{
   freopen("compile.in","r",stdin);
   freopen("compile.out","w",stdout);
   scanf("%ld%ld",&N,&M);
   if(M > N / 2)
   {
       printf("Error!\n");
       fclose(stdout);
       exit(0);
   }
   long i;
   long ans = 0;
   heapsize = 0;
   for(i = 0;i < N;i ++)
   {
       scanf("%ld",&v[i]);
       heap[heapsize] = i;
       pos[i] = heapsize;
       moveup(heapsize);
       heapsize ++;
       l[i] = i - 1;
       r[i] = i + 1;
   }
   l[0] = N - 1;
   r[N - 1] = 0;
   while(M --)
   {
       i = heap[0];
       ans += v[i];
       v[i] = v[l[i]] + v[r[i]] - v[i];
       movedown(0);
       v[l[i]] = -1000000000;    //same effect as removal
       movedown(pos[l[i]]);
       v[r[i]] = -1000000000;
       movedown(pos[r[i]]);
       l[i] = l[l[i]];
       r[i] = r[r[i]];
       l[r[i]] = i;
       r[l[i]] = i;
   }
   printf("%ld\n",ans);
   fclose(stdout);
   return 0;
}