隐藏
「AHOI2014」支线剧情 - 单纯形 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「AHOI2014」支线剧情 - 单纯形

题目大意

    JYY现在所玩的RPG游戏中,一共有$N$个剧情点,由$1$到$N$编号,第$i$个剧情点可以根据JYY的不同的选择,而经过不同的支线剧情,前往$K_i$种不同的新的剧情点。当然如果为$0$,则说明$i$号剧情点是游戏的一个结局了。
    JYY观看一个支线剧情需要一定的时间。JYY一开始处在$1$号剧情点,也就是游戏的开始。显然任何一个剧情点都是从$1$号剧情点可达的。此外,随着游戏的进行,剧情是不可逆的。所以游戏保证从任意剧情点出发,都不能再回到这个剧情点。由于JYY过度使用修改器,导致游戏的“存档”和“读档”功能损坏了,
    所以JYY要想回到之前的剧情点,唯一的方法就是退出当前游戏,并开始新的游戏,也就是回到$1$号剧情点。JYY可以在任何时刻退出游戏并重新开始。不断开始新的游戏重复观看已经看过的剧情是很痛苦,JYY希望花费最少的时间,看完所有不同的支线剧情。


题目分析

网上全都是上下界费用流的题解啊,但是bzoj一堆$60ms$的人啊。
上下界费用流还要建超级源汇,超恶心的啊,那我就第一个来发单纯形的题解吧。


考虑上图,每个点出边经过次数之和应该$\ge$其入边经过次数之和。

设$x$是每条边经过的次数,因此得出限制条件:

目标函数为:

我们发现有这样$x_j\ge1$一个条件,这并不是标准型的非负限制,怎么办呢?
我们不妨给每一个$x_j$都减$1$,则问题转化为:

最小化:

满足约束:

其中$\left|s\right|$表示$s$集合的大小。

其中第一个约束可以移项得到:

用矩阵简化上面的线性规划问题:

最小化:

满足约束:

通过对偶问题转化为标准型:

最大化:

满足约束:

转置松弛型矩阵得到对偶问题,使用单纯形算法解决。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=5005,maxm=305;
const double eps=1e-6;

int dcmp(double x) {
if(fabs(x)<=eps)return 0;
return x>eps?1:-1;
}

struct Simplex {
int n,m;
double a[maxn][maxm];
void init(int m,int n) { //a矩阵m行n列
this->n=m;
this->m=n;
}
void pivot(int in,int out) {
for(int i=0; i<=m; i++) //重置out约束
if(i!=in)a[out][i]/=-a[out][in];
a[out][in]=1/a[out][in];
for(int i=0; i<=n; i++) { //重新计算其他约束
if(i==out||dcmp(a[i][in])==0)continue;
double t=a[i][in];
a[i][in]=0;
for(int j=0; j<=m; j++)a[i][j]+=t*a[out][j];
}
}
double Solve() {
while(true) {
int in=0,out=0;
double Min=1e18;
for(int i=1; i<=m; i++)
if(dcmp(a[0][i])>0) {
in=i;
break;
}
if(!in)return a[0][0];
for(int i=1; i<=n; i++)
if(dcmp(a[i][in])<0&&a[i][0]/-a[i][in]<Min) {
Min=a[i][0]/-a[i][in];
out=i;
}
if(!out)throw ; //unbounded
pivot(in,out);
}
}
} fst;

vector<int>edges[305],in[305],out[305];
int n,id[305][305],cnt=0,rows=0,ans=0;
bool vst[305];

void AddEdge(int x,int y) {
edges[x].push_back(y);
out[x].push_back(cnt);
in[y].push_back(cnt);
}

void Dfs(int Now) {
if(vst[Now])return;
vst[Now]=1;
if(Now!=1) {
rows++;
for(int pre:in[Now])fst.a[pre][rows]=-1;
for(int suc:out[Now])fst.a[suc][rows]=1;
fst.a[0][rows]=int(out[Now].size())-int(in[Now].size());
}
for(int Next:edges[Now])Dfs(Next);
}

int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
int k=Get_Int();
while(k--) {
int x=Get_Int();
id[x][i]=id[i][x]=++cnt;
AddEdge(i,x);
fst.a[cnt][0]=Get_Int();
ans+=fst.a[cnt][0];
}
}
Dfs(1);
fst.init(cnt,rows);
printf("%d\n",int(fst.Solve())+ans);
return 0;
}
姥爷们赏瓶冰阔落吧~