签到题，暴力
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn = 1e5 + 10;
4 int rt[maxn], ls[maxn], rs[maxn], val[maxn], cnt;
5
6 void add(int x, int v) {
7 if(v < val[x]) {
8 if(ls[x]) add(ls[x], v);
9 else {
10 ls[x] = ++cnt;
11 val[cnt] = v;
12 return;
13 }
14 }
15 else {
16 if(rs[x]) add(rs[x], v);
17 else {
18 rs[x] = ++cnt;
19 val[cnt] = v;
20 return;
21 }
22 }
23 }
24
25 bool check(int x, int y) {
26 bool ret = true;
27 if(ls[x] && !ls[y] || !ls[x] && ls[y]) return false;
28 if(ls[x]) ret &= check(ls[x], ls[y]);
29 if(rs[x] && !rs[y] || !rs[x] && rs[y]) return false;
30 if(rs[x]) ret &= check(rs[x], rs[y]);
31 return ret;
32 }
33
34 int main() {
35 int n, k;
36 scanf("%d %d", &n, &k);
37 for(int i = 1; i <= n; ++i) {
38 int x;
39 scanf("%d", &x);
40 rt[i] = ++cnt, val[cnt] = x;
41 for(int j = 2; j <= k; ++j) {
42 scanf("%d", &x);
43 add(rt[i], x);
44 }
45 for(int j = 1; j < i; ++j) {
46 if(check(rt[i], rt[j])) {
47 i--; n--; break;
48 }
49 }
50 }
51 printf("%d\n", n);
52 return 0;
53 }
Aguin
EOJ大鱼吃小鱼
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn = 1e6 + 10;
4 typedef long long ll;
5 int a[maxn], b[maxn], id[maxn];
6
7 bool cmp(int i, int j) {
8 if(a[i] <= b[i] && a[j] > b[j]) return true;
9 if(a[i] > b[i] && a[j] <= b[j]) return false;
10 if(a[i] <= b[i]) return a[i] < a[j];
11 return b[i] > b[j];
12 }
13
14 int main() {
15 int n;
16 scanf("%d", &n);
17 for(int i = 1; i <= n; ++i) {
18 scanf("%d %d", a + i, b + i);
19 id[i] = i;
20 }
21 sort(id + 1, id + 1 + n, cmp);
22 ll ex = 0, ans = 0;
23 for(int i = 1; i <= n; ++i) {
24 int o = id[i];
25 if(a[o] > ex) ans += a[o] - ex, ex += a[o] - ex;
26 ex -= a[o] - b[o];
27 }
28 printf("%lld\n", ans);
29 return 0;
30 }
Aguin
枚举1e6内基数，否则不会超过四位可以解三次方程，系数都是正的单调可以二分
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4
5 inline double dcal(int i, int j, int p, int q, ll x) {
6 double y = 0. + x;
7 return i * y * y * y + j * y * y + p * y + q;
8 }
9
10 inline ll cal(int i, int j, int p, int q, ll x) {
11 return i * x * x * x + j * x * x + p * x + q;
12 }
13
14 int main() {
15 ll y, l, ans = 10;
16 scanf("%lld %lld", &y, &l);
17 for(int i = 0; i <= 9; ++i) {
18 for(int j = 0; j <= 9; ++j) {
19 for(int p = 0; p <= 9; ++p) {
20 for(int q = 0; q <= 9; ++q) {
21 if(1000 * i + 100 * j + 10 * p + q < l) continue;
22 ll lb = 11, rb = 1e18;
23 while(lb < rb) {
24 ll mid = (lb + rb) / 2;
25 if(dcal(i, j, p, q, mid) > y + 1 || cal(i, j, p, q, mid) >= y) rb = mid;
26 else lb = mid + 1;
27 }
28 if(cal(i, j, p, q, rb) == y) ans = max(ans, rb);
29 }
30 }
31 }
32 }
33 for(ll b = 11; b <= 1000000; ++b) {
34 int ok = 1;
35 ll t = y, x = 1, s = 0;
36 while(t) {
37 ll r = t % b;
38 if(r >= 10) {ok = 0; break;}
39 t /= b;
40 s += x * r;
41 x *= 10;
42 }
43 if(ok && s >= l) ans = max(ans, b);
44 }
45 printf("%lld\n", ans);
46 return 0;
47 }
Aguin
枚举端点极角排序扫一遍
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2222;
5 ll x[2][maxn], y[maxn];
6 int vis[maxn];
7
8 struct point {
9 ll x, y, id;
10 point(ll _x = 0, ll _y = 0, ll _id = 0) {
11 x = _x, y = _y, id = _id;
12 }
13 };
14
15 bool cmp(point A, point B) {
16 return A.x * B.y > A.y * B.x;
17 }
18
19 int main() {
20 int n;
21 scanf("%d", &n);
22 for(int i = 1; i <= n; ++i) {
23 scanf("%lld %lld %lld", x[0] + i, x[1] + i, y + i);
24 if(x[0][i] > x[1][i]) swap(x[0][i], x[1][i]);
25 }
26 ll ans = 0;
27 for(int i = 1; i <= n; ++i) {
28 for(int oi = 0; oi < 2; ++oi) {
29 ll xo = x[oi][i], yo = y[i];
30 vector<point> p;
31 for(int j = 1; j <= n; ++j) {
32 if(j == i) continue;
33 for(int oj = 0; oj < 2; ++oj) {
34 ll xj = x[oj][j] - xo, yj = y[j] - yo;
35 if(yj == 0) continue;
36 if(yj < 0) xj = -xj, yj = -yj;
37 p.emplace_back(point(xj, yj, j));
38 }
39 }
40 sort(p.begin(), p.end(), cmp);
41 memset(vis, 0, sizeof(vis));
42 int sz = int(p.size());
43 ll tmp = x[1][i] - x[0][i];
44 ans = max(ans, tmp);
45 for(int j = 0; j < sz; ++j) {
46 int k = j;
47 while(k + 1 < sz && !cmp(p[k], p[k + 1])) ++k;
48 for(int r = j; r <= k; ++r) {
49 ll id = p[r].id;
50 if(!vis[id]) {
51 vis[id] = 1;
52 tmp += x[1][id] - x[0][id];
53 p[r].id = 0;
54 }
55 }
56 ans = max(ans, tmp);
57 for(int r = j; r <= k; ++r) {
58 ll id = p[r].id;
59 if(vis[id]) {
60 vis[id] = 0;
61 tmp -= x[1][id] - x[0][id];
62 }
63 }
64 j = k;
65 }
66 }
67 }
68 printf("%lld\n", ans);
69 return 0;
70 }
Aguin
合法的一定可以看成是中间一堆单个的形式
1 #include <bits/stdc++.h>
2 using namespace std;
3 int a[111];
4
5 int main() {
6 int n, sum = 0;
7 scanf("%d", &n);
8 for(int i = 1; i <= n; ++i) {
9 scanf("%d", a + i);
10 sum += a[i];
11 }
12 if(sum & 1) puts("no quotation");
13 else {
14 int ans = 1;
15 for(int i = 100; i > 1; --i) {
16 int l = 1, r = n, usedl = 0, usedr = 0, ok = 1;
17 for(int j = i; j >= 1; --j) {
18 if(l == r) {
19 if(usedl + 2 * j > a[l]) {ok = 0; break;}
20 usedl = usedr += 2 * j;
21 }
22 else {
23 if(usedl + j > a[l]) {ok = 0; break;}
24 usedl += j;
25 if(usedl == a[l]) {
26 l++;
27 if(l == r) usedl = usedr;
28 else usedl = 0;
29 }
30 if(usedr + j > a[r]) {ok = 0; break;}
31 usedr += j;
32 if(l == r) usedl += j;
33 if(r > l && usedr == a[r]) r--, usedr = 0;
34 }
35 }
36 if(ok) {ans = i; break;}
37 }
38 if(ans == 1 && sum != 2) puts("no quotation");
39 else printf("%d\n", ans);
40 }
41 return 0;
42 }
Aguin
决策单调性于是分治
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 vector<int> g[2][5555], d[2][5555];
5 ll sum[5555], f[5555][5555];
6
7 const int inf = 1e9;
8 typedef pair<int, int> pii;
9 int dist[5555], sumd[5555];
10 void dijkstra(vector<int> g[], vector<int> d[], int s) {
11 priority_queue<pii> pq;
12 for(int i = 0; i < 5555; ++i) dist[i] = inf;
13 dist[s] = 0;
14 pq.push(pii(0, s));
15 while (!pq.empty()) {
16 pii tmp = pq.top();
17 pq.pop();
18 int x = tmp.second;
19 if (dist[x] < -tmp.first) continue;
20 for (int i = 0; i < g[x].size(); ++i) {
21 int to = g[x][i], cost = d[x][i];
22 if (dist[to] > dist[x] + cost) {
23 dist[to] = dist[x] + cost;
24 pq.push(pii(-dist[to], to));
25 }
26 }
27 }
28 }
29
30 void solve(int i, int l, int r, int pl, int pr) {
31 int p = -1;
32 int m = (l + r) / 2;
33 for(int j = pl; j <= min(pr, m - 1); ++j) {
34 ll tmp = f[i - 1][j] + (m - j - 1) * (sum[m] - sum[j]);
35 if(tmp < f[i][m]) f[i][m] = tmp, p = j;
36 }
37 if(m > l) solve(i, l, m - 1, pl, p);
38 if(m < r) solve(i, m + 1, r, p, pr);
39 }
40
41 int main() {
42 int n, b, s, r;
43 scanf("%d %d %d %d", &n, &b, &s, &r);
44 for(int i = 1; i <= r; ++i) {
45 int u, v, w;
46 scanf("%d %d %d", &u, &v, &w);
47 g[0][u].push_back(v), d[0][u].push_back(w);
48 g[1][v].push_back(u), d[1][v].push_back(w);
49 }
50 int S = b + 1;
51 for(int i = 0; i < 2; ++i) {
52 dijkstra(g[i], d[i], S);
53 for(int j = 1; j <= b; ++j) sumd[j] += dist[j];
54 }
55 sort(sumd + 1, sumd + 1 + b);
56 for(int i = 1; i <= b; ++i) sum[i] = sum[i - 1] + sumd[i];
57 for(int i = 0; i < 5555; ++i)
58 for(int j = 0; j < 5555; ++j)
59 f[i][j] = 1e18;
60 f[0][0] = 0;
61 for(int i = 1; i <= s; ++i)
62 solve(i, i, b, i - 1, b - 1);
63 printf("%lld\n", f[s][b]);
64 return 0;
65 }
Aguin
把不能吃，能吃但不必须吃，必须吃的边界搞出来，必须吃个数必须小于等于1，如果没有必须吃就从能吃里拿一个最左的，没有能吃的就gg了
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 1e5 + 10;
5 ll a[maxn], b[maxn], num[maxn];
6
7 typedef pair<ll, ll> pll;
8 set<pll> cant, can;
9 set<int> must;
10
11 int main() {
12 int m, k, c, sum = 0;
13 scanf("%d %d", &m, &k);
14 for(int i = 1; i <= m; ++i) scanf("%lld", a + i), sum += a[i];
15 for(int i = 1; i <= k; ++i) {
16 scanf("%lld", b + i);
17 num[b[i]] += 1;
18 }
19 for(int i = 1; i <= m; ++i) {
20 // n * (a[i] / sum) - 1 < num[i] < n * (a[i] / sum) + 1
21 // can't eat
22 // (n + 1) * (a[i] / sum) - 1 < num[i] < (n + 1) * (a[i] / sum) + 1
23 // (num[i] - 1) * sum / a[i] < n + 1 <= num[i] * sum / a[i]
24 // can eat
25 // (n + 1) * (a[i] / sum) - 1 < num[i] + 1 < (n + 1) * (a[i] / sum) + 1
26 // num[i] * sum / a[i] < n + 1 < (num[i] + 1) * sum / a[i]
27 // must eat
28 // (num[i] + 1) * sum / a[i] <= n + 1 < (num[i] + 2) * sum / a[i]
29 if(k + 1 <= (num[i] * sum) / a[i]) cant.insert(pll((num[i] * sum) / a[i], i));
30 else if(k + 1 < ((num[i] + 1) * sum + a[i] - 1) / a[i]) can.insert(pll(((num[i] + 1) * sum + a[i] - 1) / a[i], i));
31 else must.insert(i);
32 }
33 for(c = k + 1; c <= k + sum; ++c) {
34 while(!cant.empty()) {
35 auto it = cant.begin();
36 if(c > (*it).first) {
37 int x = (*it).second;
38 cant.erase(*it);
39 can.insert(pll(((num[x] + 1) * sum + a[x] - 1) / a[x], x));
40 }
41 else break;
42 }
43 while(!can.empty()) {
44 auto it = can.begin();
45 if(c >= (*it).first) {
46 int x = (*it).second;
47 can.erase(pll(((num[x] + 1) * sum + a[x] - 1) / a[x], x));
48 must.insert(x);
49 }
50 else break;
51 }
52 if(must.size() > 1) break;
53 if(must.empty()) {
54 if(can.empty()) break;
55 auto it = can.begin();
56 int x = (*it).second;
57 can.erase(pll(((num[x] + 1) * sum + a[x] - 1) / a[x], x));
58 must.insert(x);
59 }
60 auto it = must.begin();
61 int x = *it;
62 must.erase(*it);
63 num[x] += 1;
64 cant.insert(pll((num[x] * sum) / a[x], x));
65 }
66 if(c == k + sum + 1) puts("forever");
67 else printf("%d\n", c - k - 1);
68 return 0;
69 }
Aguin
快乐画图每一天
1 #include <bits/stdc++.h>
2 using namespace std;
3 char ti[24 * 60][7][22];
4 char g[111][7][22];
5
6 char ept[7][5] = {
7 "....",
8 "....",
9 "....",
10 "....",
11 "....",
12 "....",
13 "...."
14 };
15
16 char col[7][4] = {
17 "...",
18 "...",
19 ".X.",
20 "...",
21 ".X.",
22 "...",
23 "..."
24 };
25
26 char non[7][22] = {
27 ".XX...XX.....XX...XX.",
28 "X..X.X..X...X..X.X..X",
29 "X..X.X..X.X.X..X.X..X",
30 ".XX...XX.....XX...XX.",
31 "X..X.X..X.X.X..X.X..X",
32 "X..X.X..X...X..X.X..X",
33 ".XX...XX.....XX...XX."
34 };
35
36 char digit[10][7][5] = {
37
38 // 0
39 ".XX.",
40 "X..X",
41 "X..X",
42 "....",
43 "X..X",
44 "X..X",
45 ".XX.",
46
47 // 1
48 "....",
49 "...X",
50 "...X",
51 "....",
52 "...X",
53 "...X",
54 "....",
55
56 // 2
57 ".XX.",
58 "...X",
59 "...X",
60 ".XX.",
61 "X...",
62 "X...",
63 ".XX.",
64
65 // 3
66 ".XX.",
67 "...X",
68 "...X",
69 ".XX.",
70 "...X",
71 "...X",
72 ".XX.",
73
74 // 4
75 "....",
76 "X..X",
77 "X..X",
78 ".XX.",
79 "...X",
80 "...X",
81 "....",
82
83 // 5
84 ".XX.",
85 "X...",
86 "X...",
87 ".XX.",
88 "...X",
89 "...X",
90 ".XX.",
91
92 // 6
93 ".XX.",
94 "X...",
95 "X...",
96 ".XX.",
97 "X..X",
98 "X..X",
99 ".XX.",
100
101 // 7
102 ".XX.",
103 "...X",
104 "...X",
105 "....",
106 "...X",
107 "...X",
108 "....",
109
110 // 8
111 ".XX.",
112 "X..X",
113 "X..X",
114 ".XX.",
115 "X..X",
116 "X..X",
117 ".XX.",
118
119 // 9
120 ".XX.",
121 "X..X",
122 "X..X",
123 ".XX.",
124 "...X",
125 "...X",
126 ".XX."
127 };
128
129 inline void draw(char g[][22], int c, int w, char fig[][5]) {
130 for(int i = 0; i < 7; ++i) {
131 for(int j = c; j < c + w; ++j) {
132 g[i][j] = fig[i][j - c];
133 }
134 }
135 }
136
137 inline void drawcol(char g[][22]) {
138 for(int i = 0; i < 7; ++i) {
139 for(int j = 9; j < 12; ++j) {
140 g[i][j] = col[i][j - 9];
141 }
142 }
143 }
144
145 bool on[7][22], off[7][22], work[7][22];
146 int cnt_on[7][22], cnt_off[7][22];
147 bool check(char g[][22], char fig[][22]) {
148 for(int i = 0; i < 7; ++i) {
149 for(int j = 0; j < 21; ++j) {
150 if(fig[i][j] == '.' && g[i][j] == 'X') on[i][j] = true;
151 if(fig[i][j] == 'X' && g[i][j] == '.') off[i][j] = true;
152 }
153 }
154 }
155
156 int main() {
157 for(int h = 0; h < 24; ++h) {
158 for(int m = 0; m < 60; ++m) {
159 int t = 60 * h + m;
160 if(h < 10) draw(ti[t], 0, 4, ept);
161 else draw(ti[t], 0, 4, digit[h / 10]);
162 drawcol(ti[t]);
163 draw(ti[t], 5, 4, digit[h % 10]);
164 draw(ti[t], 12, 4, digit[m / 10]);
165 draw(ti[t], 17, 4, digit[m % 10]);
166 }
167 }
168 int n, cnt = 0;
169 scanf("%d", &n);
170 for(int i = 0; i < n; ++i)
171 for(int j = 0; j < 7; ++j)
172 scanf("%s", g[i][j]);
173 for(int st = 0; st < 24 * 60; ++st) {
174 memset(on, 0, sizeof(on));
175 memset(off, 0, sizeof(off));
176 for(int i = 0; i < n; ++i) {
177 check(g[i], ti[(st + i) % (24 * 60)]);
178 }
179 int ok = 1;
180 for(int i = 0; i < n; ++i) {
181 for(int j = 0; j < 7; ++j) {
182 for(int k = 0; k < 21; ++k) {
183 if(on[j][k] && g[i][j][k] == '.') ok = 0;
184 if(off[j][k] && g[i][j][k] == 'X') ok = 0;
185 }
186 }
187 }
188 if(ok) {
189 cnt += 1;
190 for(int i = 0; i < 7; ++i) {
191 for(int j = 0; j < 21; ++j) {
192 if(on[i][j]) cnt_on[i][j] += 1;
193 if(off[i][j]) cnt_off[i][j] += 1;
194 }
195 }
196 }
197 }
198 for(int i = 1; i < n; ++i) {
199 for(int j = 0; j < 7; ++j) {
200 for(int k = 0; k < 21; ++k) {
201 if(g[i][j][k] != g[i - 1][j][k]) work[j][k] = 1;
202 }
203 }
204 }
205 if(!cnt) puts("impossible");
206 else {
207 for(int i = 0; i < 7; ++i) {
208 for(int j = 0; j < 21; ++j) {
209 if(non[i][j] == '.') putchar('.');
210 else if(cnt_on[i][j] == cnt) putchar('1');
211 else if(cnt_off[i][j] == cnt) putchar('0');
212 else if(work[i][j] && !cnt_on[i][j] && !cnt_off[i][j]) putchar('W');
213 else putchar('?');
214 }
215 puts("");
216 }
217 }
218 return 0;
219 }
Aguin
距离从大到小枚举叶子，如果一个子树里最短的距离都比这个大，至少有一个河会更长，就放弃这条河直接把海水引过来
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const ll inf = 1e18;
5 const int maxn = 1e6 + 10;
6 vector<int> g[maxn];
7 char s[maxn][22];
8 int f[maxn];
9 ll d[maxn];
10
11 ll dis[maxn], mi[maxn];
12 void dfs(int x) {
13 mi[x] = inf;
14 for(auto y: g[x]) {
15 dis[y] = dis[x] + d[y];
16 dfs(y), mi[x] = min(mi[x], mi[y]);
17 }
18 if(mi[x] == inf) mi[x] = 0;
19 mi[x] += d[x];
20 }
21
22 bool cmpnd(int i, int j) {
23 return mi[i] > mi[j];
24 }
25
26 bool cmplf(int i, int j) {
27 return dis[i] > dis[j];
28 }
29
30 int lf[maxn], nd[maxn], vis[maxn], used[maxn], ans[maxn];
31 int main() {
32 int n, m;
33 scanf("%d %d", &n, &m);
34 for(int i = 1; i <= n; ++i) {
35 scanf("%s %d %lld", s[m + i], f + m + i, d + m + i);
36 g[f[m + i]].push_back(m + i);
37 lf[m + i] = nd[m + i] = m + i;
38 }
39 for(int i = 1; i <= m; ++i) {
40 scanf("%d %lld", f + i, d + i);
41 g[f[i]].push_back(i);
42 nd[i] = i;
43 }
44 dfs(0);
45 sort(nd + 1, nd + n + m + 1, cmpnd);
46 sort(lf + m + 1, lf + n + m + 1, cmplf);
47 int p = 0, tmp = 1;
48 for(int i = m + 1; i <= n + m; ++i) {
49 while(p < n + m && mi[nd[p + 1]] > dis[lf[i]]) {
50 int t = nd[p + 1];
51 while(t && !vis[t]) {
52 vis[t] = 1;
53 if(!used[t]) tmp++;
54 if(vis[f[t]] && !used[f[t]]) tmp--;
55 used[f[t]] = 1;
56 t = f[t];
57 }
58 ++p;
59 }
60 ans[lf[i]] = tmp;
61 }
62 for(int i = m + 1; i <= n + m; ++i) printf("%s %d\n", s[i], ans[i]);
63 return 0;
64 }
Aguin
把每条路时间当变量就是线性规划
1 #include <bits/stdc++.h>
2 using namespace std;
3 int g[33][33];
4
5 const double eps = 1e-8;
6 int cmp(const double &x) {
7 return x < -eps ? -1 : x > eps;
8 }
9 const int maxn = 444, maxm = 888, inf = 1e9;
10 double a[maxm][maxn], b[maxm];
11 double ca[maxm][maxn], cb[maxm];
12 int idn[maxn], idm[maxm];
13 int n, m;
14 void pivot(int x,int y) {
15 swap(idm[x], idn[y]);
16 double k = a[x][y];
17 for (int j = 1; j <= n; ++j)a[x][j] /= k;
18 b[x] /= k;
19 a[x][y] = 1 / k;
20 for (int i = 0; i <= m; ++i)
21 if (i != x) {
22 k = a[i][y];
23 if (!cmp(k))continue;
24 b[i] -= k * b[x];
25 a[i][y] = 0;
26 for (int j = 1; j <= n; ++j)a[i][j] -= a[x][j] * k;
27 }
28 }
29 void simplex() {
30 idn[0] = inf;
31 while (1) {
32 int y = 0;
33 for (int j = 1; j <= n; ++j)
34 if (cmp(a[0][j]) > 0 && idn[j] < idn[y])y = j;
35 if (!y)break;
36 int x = 0;
37 for (int i = 1; i <= m; ++i)
38 if (cmp(a[i][y]) > 0) {
39 if (!x)x = i;
40 else {
41 int t = cmp(b[i] / a[i][y] - b[x] / a[x][y]);
42 if (t < 0 || (t == 0 && idm[i] < idm[x]))x = i;
43 }
44 }
45 if (!x) {
46 puts("Unbounded");
47 exit(0);
48 }
49 pivot(x, y);
50 }
51 }
52 void init() {
53 idm[0] = inf;
54 idn[0] = inf;
55 while (1) {
56 int x = 0;
57 for (int i = 1; i <= m; ++i)
58 if (cmp(b[i]) < 0 && idm[i] < idm[x])x = i;
59 if (!x)break;
60 int y = 0;
61 for (int j = 1; j <= n; ++j)
62 if (cmp(a[x][j]) < 0 && idn[j] < idn[y])y = j;
63 if (!y) {
64 puts("Infeasible");
65 exit(0);
66 }
67 pivot(x, y);
68 }
69 }
70
71 int N;
72 vector<int> get_path(int s, int t) {
73 if(s == t) return vector<int>(1, s);
74 for(int i = 0; i < N; ++i) {
75 if(g[s][i] && g[i][t] && g[s][i] + g[i][t] == g[s][t]) {
76 vector<int> pre = get_path(s, i);
77 vector<int> suf = get_path(i, t);
78 for(int j = 1; j < suf.size(); ++j) pre.push_back(suf[j]);
79 return pre;
80 }
81 }
82 return vector<int>{s, t};
83 }
84
85 int id[33][33];
86 int main() {
87 int R, Q;
88 scanf("%d", &N);
89 for(int i = 0; i < N; ++i) {
90 for(int j = 0; j < N; ++j) {
91 scanf("%d", &g[i][j]);
92 if(i != j && g[i][j] != -1) {
93 id[i][j] = ++n;
94 ++m;
95 a[m][n] = 1, b[m] = g[i][j] + g[i][j];
96 ++m;
97 a[m][n] = -1, b[m] = -g[i][j];
98 }
99 if(g[i][j] == -1) g[i][j] = inf;
100 }
101 }
102 for(int k = 0; k < N; ++k)
103 for(int i = 0; i < N; ++i)
104 for(int j = 0; j < N; ++j)
105 g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
106 scanf("%d", &R);
107 for(int i = 1; i <= R; ++i) {
108 int s, t, d;
109 scanf("%d %d %d", &s, &t, &d);
110 vector<int> path = get_path(s, t);
111 ++m;
112 for(int j = 0; j < path.size() - 1; ++j) {
113 a[m][id[path[j]][path[j + 1]]] = 1;
114 }
115 b[m] = d;
116 ++m;
117 for(int j = 0; j < path.size() - 1; ++j) {
118 a[m][id[path[j]][path[j + 1]]] = -1;
119 }
120 b[m] = -d;
121 }
122 memcpy(ca, a, sizeof(ca));
123 memcpy(cb, b, sizeof(cb));
124 scanf("%d", &Q);
125 while(Q--) {
126 int s, t;
127 scanf("%d %d", &s, &t);
128 printf("%d %d ", s, t);
129 vector<int> path = get_path(s, t);
130 memcpy(a, ca, sizeof(a));
131 memcpy(b, cb, sizeof(b));
132 for(int j = 1; j <= n; ++j) idn[j] = j;
133 for(int i = 1; i <= m; ++i) idm[i] = n + i;
134 for(int i = 0; i < path.size() - 1; ++i) a[0][id[path[i]][path[i + 1]]] = -1;
135 init();
136 simplex();
137 printf("%.9f ", b[0]);
138 memcpy(a, ca, sizeof(a));
139 memcpy(b, cb, sizeof(b));
140 for(int j = 1; j <= n; ++j) idn[j] = j;
141 for(int i = 1; i <= m; ++i) idm[i] = n + i;
142 for(int i = 0; i < path.size() - 1; ++i) a[0][id[path[i]][path[i + 1]]] = 1;
143 init();
144 simplex();
145 printf("%.9f\n", -b[0]);
146 }
147 return 0;
148 }
Aguin