题目大意
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) {
this->n=m;
this->m=n;
}
void pivot(int in,int out) {
for(int i=0; i<=m; i++)
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 ;
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;
}
|
