一个奇怪的取数游戏

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

USACO TeleCowmunication

这是一道和联通性有关的题目，USACO Chapter 4有介绍过解决这个题目的思路：

This is equivalent to the minimum node cut problem. The two given machines can be arbitrarily labeled the source and sink. The wires are bidirectional. Split each node into an in-node and an out-node, so that we limit the flow through any given machine to 1. Now, the maximum flow across this network is equivalent to the minimum node cut.（max-flow min-cut theorem, wikipedia）

To actually determine the cut, iterative remove the nodes until you find one which lowers the capacity of the network.

这个算法用到了“拆点”。在理解上述算法的前提下（后面说的一些概念是建立在“拆点”的图上的），仔细分析会发现，不“拆点”也可以，只需要修改一下最大流算法——找到增广路后直接删除路径上的点（除了始末两个），重复直到找不到增广路。这种算法的实质和上面的相同，复杂度也相同，不过实际运行会快一点。

得到了最大流后，以此尝试移除某个点，如果此时的最大流正好等于原来-1,那么这个点就是一个“关键点”。

最后，由于题目要输出排序最小的点集，于是进行一次DFS，然后移除点测试联通性即可。

上面说的相当混乱，看代码吧：

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 int N,M,source,sink;
006 int cap[101][101] = {};
007 int tmp[101][101];
008 int queue[200];
009 int head,tail;
010 int exclude[101];
011 int oncut[101] = {};
012 int max;
013 int isdown[101] = {};
014
015 void enqueue(int node)
016 {
017     queue[tail ++] = node;
018 }
019
020 int dequeue()
021 {
022     return queue[head ++];
023 }
024
025 void init()
026 {
027     int a,b;
028     scanf("%d%d%d%d\n",&N,&M,&source,&sink);
029     while(M --)
030     {
031         scanf("%d%d\n",&a,&b);
032         cap[a][b] = cap[b][a] = 1;
033     }
034 }
035
036 int getmin(int a,int b)
037 {
038     if(a < b)    return a;
039     return b;
040 }
041
042 int prev[101];
043 int visit[101];
044 int flow[101];
045 int bfs()   //find augmenting path
046 {
047     int i,j;
048     head = tail = 0;
049     memset(flow,0,sizeof(flow));
050     memset(prev,0,sizeof(prev));
051     memset(visit,0,sizeof(visit));
052     enqueue(source);
053     visit[source] = 1;
054     flow[source] = 32000;
055     while(head < tail)
056     {
057         i = dequeue();
058         if(i == sink)
059             return flow[sink];
060         for(j = 1;j <= N;j ++)
061             if(tmp[i][j] > 0 && !visit[j] && !exclude[j])
062             {
063                 visit[j] = 1;
064                 flow[j] = getmin(flow[i],tmp[i][j]);
065                 prev[j] = i;
066                 enqueue(j);
067             }
068     }
069     return 0;
070 }
071
072 int solve()   //ford-fulkerson
073 {
074     int maxflow = 0;
075     int add,i;
076     memcpy(tmp,cap,sizeof(tmp));
077     while(1)
078     {
079         add = bfs();
080         if(add == 0)    break;
081         maxflow += add;
082         for(i = prev[sink];i != source;i = prev[i])   //exclude nodes on path
083             exclude[i] = 1;
084     }
085     return maxflow;
086 }
087
088 int reachable()   //whether source and sink are connected
089 {
090     int i,j;
091     head = tail = 0;
092     memset(visit,0,sizeof(visit));
093     enqueue(source);
094     visit[source] = 1;
095     while(head < tail)
096     {
097         i = dequeue();
098         if(i == sink)    return 1;
099         for(j = 1;j <= N;j ++)
100             if(cap[i][j] && !visit[j] && !isdown[j])
101             {
102                 visit[j] = 1;
103                 enqueue(j);
104             }
105     }
106     return 0;
107 }
108
109 void dfs(int node,int tot)
110 {
111     if(tot == max)
112     {
113         if(!reachable())
114         {
115             int i;
116             int flag = 1;
117             for(i = 1;i <= N;i ++)
118                 if(isdown[i])
119                 {
120                     if(flag)
121                     {
122                         flag = 0;
123                         printf("%d",i);
124                     }
125                     else
126                         printf(" %d",i);
127                 }
128             printf("\n");
129             exit(0);
130         }
131         return;
132     }
133     if(node > N)    return;
134     if(oncut[node])
135     {
136         isdown[node] = 1;
137         dfs(node + 1,tot + 1);
138         isdown[node] = 0;
139     }
140     dfs(node + 1,tot);
141 }
142
143 int main()
144 {
145     int i;
146     freopen("telecow.in","r",stdin);
147     freopen("telecow.out","w",stdout);
148     init();
149     max = solve();
150     printf("%d\n",max);
151     for(i = 1;i <= N;i ++) //find all "critical nodes"
152     {
153         if(i == source || i == sink)    continue;
154         memset(exclude,0,sizeof(exclude));
155         exclude[i] = 1;
156         if(solve() < max)
157             oncut[i] = 1;
158     }
159     dfs(1,0);
160     return 0;
161 }

同样附上“拆点”的代码，这个更方便理解：

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define INFINITY 32000
005
006 int N,M,source,sink;
007 int adj[101][101] = {};
008 int cap[210][210] = {};
009 int tmp[210][210];
010 int queue[210];
011 int head,tail;
012 int oncut[210] = {};
013 int max;
014 int isdown[210] = {};
015
016 void enqueue(int node)
017 {
018     queue[tail ++] = node;
019 }
020
021 int dequeue()
022 {
023     return queue[head ++];
024 }
025
026 void init()
027 {
028     int a,b;
029     scanf("%d%d%d%d\n",&N,&M,&source,&sink);
030     int i;
031     for(i = 1;i <= N;i ++)   split nodes----one in, one out
032         cap[i][N + i] = cap[N + i][i] = 1;   //split nodes
033     while(M --)
034     {
035         scanf("%d%d\n",&a,&b);
036         adj[a][b] = adj[b][a] = 1;
037         cap[a + N][b] = INFINITY;
038         cap[b + N][a] = INFINITY;
039     }
040 }
041
042 int getmin(int a,int b)
043 {
044     if(a < b)    return a;
045     return b;
046 }
047
048 int prev[210];
049 int visit[210];
050 int flow[210];
051 int bfs()
052 {
053     int i,j;
054     head = tail = 0;
055     memset(flow,0,sizeof(flow));
056     memset(prev,0,sizeof(prev));
057     memset(visit,0,sizeof(visit));
058     enqueue(source);
059     visit[source] = 1;
060     flow[source] = INFINITY;
061     while(head < tail)
062     {
063         i = dequeue();
064         if(i == sink)
065             return flow[sink];
066         for(j = 1;j <= N * 2;j ++)
067             if(tmp[i][j] > 0 && !visit[j])
068             {
069                 visit[j] = 1;
070                 flow[j] = getmin(flow[i],tmp[i][j]);
071                 prev[j] = i;
072                 enqueue(j);
073             }
074     }
075     return 0;
076 }
077
078 int solve()   //standard ford-fulkerson
079 {
080     int maxflow = 0;
081     int add,i;
082     memcpy(tmp,cap,sizeof(tmp));
083     while(1)
084     {
085         add = bfs();
086         if(add == 0)    break;
087         maxflow += add;
088         for(i = sink;i != source + N;i = prev[i])
089         {
090             tmp[prev[i]][i] -= add;
091             tmp[i][prev[i]] += add;
092         }
093     }
094     return maxflow;
095 }
096
097 int reachable()
098 {
099     int i,j;
100     head = tail = 0;
101     memset(visit,0,sizeof(visit));
102     enqueue(source);
103     visit[source] = 1;
104     while(head < tail)
105     {
106         i = dequeue();
107         if(i == sink)    return 1;
108         for(j = 1;j <= N;j ++)
109         {
110             if(adj[i][j] && !visit[j] && !isdown[j])
111             {
112                 visit[j] = 1;
113                 enqueue(j);
114             }
115         }
116     }
117     return 0;
118 }
119
120 void dfs(int node,int tot)
121 {
122     if(tot == max)
123     {
124         if(!reachable())
125         {
126             int i;
127             int flag = 1;
128             for(i = 1;i <= N;i ++)
129                 if(isdown[i])
130                 {
131                     if(flag)
132                     {
133                         flag = 0;
134                         printf("%d",i);
135                     }
136                     else
137                         printf(" %d",i);
138                 }
139             printf("\n");
140             exit(0);
141         }
142         return;
143     }
144     if(node > N)    return;
145     if(oncut[node])
146     {
147         isdown[node] = 1;
148         dfs(node + 1,tot + 1);
149         isdown[node] = 0;
150     }
151     dfs(node + 1,tot);
152 }
153
154 int main()
155 {
156     int i;
157     freopen("telecow.in","r",stdin);
158     freopen("telecow.out","w",stdout);
159     init();
160     max = solve();
161     printf("%d\n",max);
162     for(i = 1;i <= N;i ++)
163     {
164         if(i == sink || i == source)    continue;
165         cap[i][i + N] = cap[i + N][i] = 0;
166         if(solve() < max)
167             oncut[i] = 1;
168         cap[i][i + N] = cap[i + N][i] = 1;
169     }
170     dfs(1,0);
171     return 0;
172 }