用随机化算法通过网络流
Hukaidi8566
·
·
算法·理论
头一天在日本作家结城浩所著的《数学女孩4，随机算法》看到了 3-SAT 的 O(1.334^n) 做法，第二天恰好做到了这题，想到了一个随机化算法。
观察问题
题目传送门
简析题意：要想使第 x 个球队获得冠军，须使第 x 个球队赢下其他所有球队，并且能够构造一种方案使其他队伍的获胜场次小于等于第 x 个球队的获胜场次。
设 s_i 为第 i 个球队剩余的总场次，则有一个很浅显的结论：若 a_x+s_x<a_i，那么第 x 个球队一定不可能成为冠军。
我们发现，对于每个 x，如果暴力枚举除 x 以外的每场比赛的结果，复杂度实际上并不高，那么就可以尝试使用随机化算法解决。
如果对于任意的 i\ne x，都有 a_x+s_x \ge a_i，那么就试图构造一种方案使第 x 个球队成为冠军。这里我们采用单向正确的随机化算法，若程序返回“找到方案可以成为冠军”，那么输出 x；否则程序返回“未找到方案大概不可以成为冠军”，那么我们认为第 x 个球队不可能成为冠军。
考虑构造方案
引入一个 汉明距离 的概念：汉明距离（Hamming Distance）是用于衡量两个等长字符串（在数据通信中通常是二进制串）之间差异程度的一个度量。它计算的是两个字符串在相同位置上不同字符（或比特）的数量。
设 A 为第 x 个球队能够成为冠军的一个方案，且有关 x 的比赛 x 全赢。
设 B 是我们随机构造的一个方案，满足有关 x 的比赛 x 全赢，其他关于 i 和 j 比赛随机决定 i , j 各赢几场。
先来探讨一个问题，记 dis 为 A 和 B 的距离，其计算方式如下：
$$dis=\sum_{1\le i < j \le n , i,j \ne x} \lvert f_{i,j} - g_{i,j} \rvert $$
问 $dis$ 最坏情况下的期望值是多少？
期望可以看作平均，最坏情况是 $a_{i,j}=10$，$f_{i,j}=0$，此时 $g_{i,j}$ 的期望值为 $5$，$dis=24 \times 23 \times 5=2760$。
到这里，就会发现可以写出一种与 3-SAT 的 $O(1.334^n)$ 做法类似的实现方案，写一个 $Check$ 函数，见下：
1. 从 $1$ 循环到 $n$ ，设 $op=a_x+s_x$，如果发现 $op<a_i$，返回 $0$。
2. 随机构造一种方案 $B$，并求出 $g$ 数组。
3. 检查此时是否有队伍获胜次数超过 $x$ 的获胜次数，如果没有，返回 $1$。
4. 在获胜次数超过 $x$ 的队伍中随机寻找一个队伍 $i$。
5. 在满足 $g_{i,j} \ne 0$ 且 $j \ne x$ 的 $j$ 中随机取一个 $j$，修改 $i$ 和 $j$ 的比赛情况，具体地，让 $j$ 多赢 $i$ 一场，即 $g_{i,j}$ 减掉 $1$，$g_{j,i}$ 加上 $1$。
6. 执行 3~5 步 $5000$ 遍。
7. 回到第二步，第二步总共执行 $100$ 次。
8. 返回 $0$，表示第 $x$ 个球队不可能成为冠军。
### 对下界的评估
随机化算法的时间计算关键在于，在有解的情况下单次循环能够找到答案的概率。在本算法中，就是每一次从第二步开始能够返回 $1$ 的概率。
这里给出两种评估方案：
- $dis$ 最坏情况下期望为 $2760$，每一次调整会使 $dis$ 增加或减少 $1$。实际上 $A$ 很可能有多个，因此实际的效率会比这个小很多。
- 记 $s_i$ 为第 $i$ 个球队当前状态下赢的总场数，$dis'$ 为其他 $s_i$ 超过 $op$ 的总和，即有
$$ dis'=\sum_{1\le i \le n,s_i>op,i\ne x} (s_i-op) $$
每次操作只有可能使 $dis'$ 减少 $1$ 或不变，我能想到的比较极端的情况是 $dis'=210$（期望值是 $105$），每次有 $\frac{1}{23}$ 的概率使 $dis'$ 减小。
很抱歉的是我并不能更加准确地评估出它的下界，只能这样了。
### code
（码风非常不好，又臭又长）
```cpp
#include<cstdio>
#include<algorithm>
#include<time.h>
using namespace std;
const int nn=30;
int n;
int a[nn],b[nn];
int c[nn][nn];
int sumc[nn];
bool Check(int);
int s2[nn];
bool cmpd(int,int);
int main()
{
unsigned int seed=(unsigned)time(NULL);
srand(seed);
// printf("seed=%u\n",seed);//
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
{
scanf("%d",&c[i][j]);
sumc[i]+=c[i][j];
}
bool ans[nn];
for(int i=1;i<=n;i++) ans[i]=Check(i);
for(int i=1;i<=n;i++) if(ans[i]) printf("%d ",i);
return 0;
}
bool Check(int x)
{
int c2[nn][nn];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) c2[i][j]=c[i][j];
s2[i]=sumc[i];
}
int op=a[x]+s2[x];
for(int i=1;i<=n;i++)
{
s2[i]-=c2[i][x];
c2[i][x]=c2[x][i]=0;
}
for(int i=1;i<=n;i++) if(a[i]>op&&i!=op) return 0;
for(int qw1=0;qw1<=100;qw1++)
{
int s3[nn],c3[nn][nn];
for(int i=0;i<nn;i++) s3[i]=a[i];
for(int i=1;i<=n;i++)
{
if(i==x) continue;
for(int j=i+1;j<=n;j++)
{
if(j==x) continue;
c3[i][j]=rand()%(c2[i][j]+1);
c3[j][i]=c2[i][j]-c3[i][j];
s3[i]+=c3[i][j];
s3[j]+=c3[j][i];
}
}
for(int qw2=0;qw2<=5000;qw2++)
{
int team1[nn],tail1=0;
for(int i=1;i<=n;i++)
if(s3[i]>op&&i!=x) team1[tail1++]=i;
if(!tail1) return 1;
int i=team1[rand()%tail1];
int team2[nn],tail2=0;
for(int j=1;j<=n;j++)
if(c3[i][j]&&j!=x) team2[tail2++]=j;
int j=team2[rand()%tail2];
s3[i]--,s3[j]++;
c3[i][j]--,c3[j][i]++;
}
}
return 0;
}
bool cmpd(int x,int y)
{
return s2[x]>s2[y];
}
```