Ncik

20.7万

Brokenheart100
lym.
xiaojia

zero096
tomousw
1eave

ACG2021
WangJY
lindi530
Narity
NULL_20
arthur15
Hanasaki

Ncik
1天前
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;

inline void chmin(int& x, int y) { if (x > y) x = y; }

int main() {
int n, m, q;
cin >> n >> m >> q;

const int INF = 1001001001;
vector d(n, vector<int>(n, INF));
rep(i, n) d[i][i] = 0;
rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
chmin(d[a][b], c);
}

rep(k, n)rep(i, n)rep(j, n) {
chmin(d[i][j], d[i][k]+d[k][j]);
}

rep(qi, q) {
int a, b;
cin >> a >> b;
--a; --b;
int ans = d[a][b];
if (ans > INF/2) puts("impossible");
else cout << ans << '\n';
}

return 0;
}


Ncik
1天前
// Dinic 板子
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include  <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i <  (n); ++i)
#define INF 1e18

using namespace std;
using ll = long long;

template <typename Cap>
struct dinic{
struct edge{
int to, rev;
Cap cap;
edge(int to, int rev, Cap cap): to(to), rev(rev), cap(cap) {}
};
int N;
vector<vector<edge>> G;
dinic() {}
dinic(int N): N(N), G(N) {}
void add_edge(int from, int to, Cap cap){
G[from].push_back(edge(to, G[to].size(), cap));
G[to].push_back(edge(from, G[from].size() - 1, 0));
}
Cap dfs(vector<int> &d, vector<int> &iter, int v, int t, Cap f){
if (v == t){
return f;
}
while (iter[v] < G[v].size()){
int w = G[v][iter[v]].to;
if (G[v][iter[v]].cap > 0 && d[v] < d[w]){
Cap f2 = dfs(d, iter, w, t, min(f, G[v][iter[v]].cap));
if (f2 > 0){
G[v][iter[v]].cap -= f2;
G[w][G[v][iter[v]].rev].cap += f2;
return f2;
}
}
iter[v]++;
}
return 0;
}
Cap max_flow(int s, int t){
Cap flow = 0;
while (true){
vector<int> d(N, -1);
d[s] = 0;
queue<int> Q;
Q.push(s);
while (!Q.empty()){
if (d[t] != -1){
break;
}
int v = Q.front();
Q.pop();
for (auto &e : G[v]){
int w = e.to;
if (e.cap > 0 && d[w] == -1){
d[w] = d[v] + 1;
Q.push(w);
}
}
}
if (d[t] == -1){
break;
}
vector<int> iter(N, 0);
while (true){
Cap f = dfs(d, iter, s, t, INF);
if (f == 0){
break;
}
flow += f;
}
}
return flow;
}
};

int main() {
cin.tie(nullptr) -> sync_with_stdio(false);

int n, m, s, t;
cin >> n >> m >> s >> t;
--s; --t;

dinic<ll> g(n);
rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
}

ll ans = g.max_flow(s, t);
cout << ans << '\n';

return 0;
}


Ncik
1天前

### 算法

#### C++ 代码

#include  <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i <  (n); ++i)
#define INF 1e9

using namespace std;

template <typename Cap>
struct dinic{
struct edge{
int to, rev;
Cap cap;
edge(int to, int rev, Cap cap): to(to), rev(rev), cap(cap) {}
};
int N;
vector<vector<edge>> G;
dinic() {}
dinic(int N): N(N), G(N) {}
void add_edge(int from, int to, Cap cap){
G[from].push_back(edge(to, G[to].size(), cap));
G[to].push_back(edge(from, G[from].size() - 1, 0));
}
Cap dfs(vector<int> &d, vector<int> &iter, int v, int t, Cap f){
if (v == t){
return f;
}
while (iter[v] < G[v].size()){
int w = G[v][iter[v]].to;
if (G[v][iter[v]].cap > 0 && d[v] < d[w]){
Cap f2 = dfs(d, iter, w, t, min(f, G[v][iter[v]].cap));
if (f2 > 0){
G[v][iter[v]].cap -= f2;
G[w][G[v][iter[v]].rev].cap += f2;
return f2;
}
}
iter[v]++;
}
return 0;
}
Cap max_flow(int s, int t){
Cap flow = 0;
while (true){
vector<int> d(N, -1);
d[s] = 0;
queue<int> Q;
Q.push(s);
while (!Q.empty()){
if (d[t] != -1){
break;
}
int v = Q.front();
Q.pop();
for (auto &e : G[v]){
int w = e.to;
if (e.cap > 0 && d[w] == -1){
d[w] = d[v] + 1;
Q.push(w);
}
}
}
if (d[t] == -1){
break;
}
vector<int> iter(N, 0);
while (true){
Cap f = dfs(d, iter, s, t, INF);
if (f == 0){
break;
}
flow += f;
}
}
return flow;
}
};

int main() {
int n, f, d;
cin >> n >> f >> d;

// 0~n-1: 食物一侧的牛
// n~2n-1: 饮料一侧的牛
// 2n~2n+f-1: 食物
// 2n+f~2n+f+d-1: 饮料
int sv = f+d+n*2, tv = sv+1;
dinic<int> g(tv+1);
// 在源点和食物之间连边
// 在饮料和汇点之间连边
// 在食物一侧的牛和饮料一侧的牛之间连边
rep(i, n) {
int cf, cd, x;
cin >> cf >> cd;

// 在食物和食物一侧的牛连边
while (cf--) {
cin >> x;
--x;
}

// 在饮料一侧的牛和饮料连边
while (cd--) {
cin >> x;
--x;
}
}

int ans = g.max_flow(sv, tv);
cout << ans << '\n';

return 0;
}


Ncik
2天前
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using std::istream;
using std::ostream;
using ll = long long;

//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}

// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}

// combination mod prime
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
} comb(100005);

int main() {
int n;
cin >> n;

rep(i, n) {
int a, b;
cin >> a >> b;
cout << comb(a, b) << '\n';
}

return 0;
}


Ncik
2天前
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using std::istream;
using std::ostream;
using ll = long long;

//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}

// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}

// combination mod prime
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
} comb(2005);

int main() {
int n;
cin >> n;

rep(i, n) {
int a, b;
cin >> a >> b;
cout << comb(a, b) << '\n';
}

return 0;
}


Ncik
2天前

### 算法

##### (期望、组合数学)

• 固定一个数作为所选数中的最大值，那么它的贡献就是从剩余数里取 $k-1$ 个数的方案数
• 先对序列进行升序排序
• 然后分别将序列的后 $N-K+1$ 个数作为最大数，对于其他 $K-1$ 个数，最大数之后的数就不用考虑了，只需在前面剩下的数里取即可
• 求出这些数的贡献之和，再将它与概率做乘积即可得到最大期望

#### C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;
using mint = modint998244353;

// combination mod prime
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
} comb(200005);

int main() {
int n, k;
cin >> n >> k;

vector<int> a(n);
rep(i, n) cin >> a[i];

sort(a.begin(), a.end());

mint s_max;
for (int i = n-1; i >= k-1; --i) {
s_max += a[i]*comb(i, k-1);
}
mint s_min;
rep(i, n-k+1) {
s_min += a[i]*comb(n-1-i, k-1);
}

mint ans = s_max - s_min;
ans /= comb(n, k);
cout << ans.val() << '\n';

return 0;
}


Ncik
2天前

### 算法

#### C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define INF 1e18

using namespace std;
using ll = long long;

template <typename Cap, typename Cost>
struct primal_dual {
struct edge{
int to, rev;
Cap cap;
Cost cost;
edge(int to, int rev, Cap cap, Cost cost): to(to), rev(rev), cap(cap), cost(cost) {}
};
int N;
vector<vector<edge>> G;
primal_dual(){}
primal_dual(int N): N(N), G(N){}
void add_edge(int from, int to, Cap cap, Cost cost){
int id1 = G[from].size();
int id2 = G[to].size();
G[from].push_back(edge(to, id2, cap, cost));
G[to].push_back(edge(from, id1, 0, -cost));
}
pair<Cap, Cost> min_cost_flow(int s, int t, Cap F=INF){
Cap flow = 0;
Cost cost = 0;
vector<Cost> h(N, 0);
while (flow < F){
vector<Cap> m(N, INF);
vector<Cost> d(N, INF);
vector<int> pv(N, -1);
vector<int> pe(N, -1);
vector<bool> used(N, false);
priority_queue<pair<Cost, int>, vector<pair<Cost, int>>, greater<pair<Cost, int>>> pq;
pq.push(make_pair(0, s));
d[s] = 0;
while (!pq.empty()){
int v = pq.top().second;
pq.pop();
if (!used[v]){
used[v] = true;
if (v == t){
break;
}
int cnt = G[v].size();
for (int i = 0; i < cnt; i++){
int w = G[v][i].to;
if (!used[w] && G[v][i].cap > 0){
Cost tmp = G[v][i].cost - h[w] + h[v];
if (d[w] > d[v] + tmp){
d[w] = d[v] + tmp;
m[w] = min(m[v], G[v][i].cap);
pv[w] = v;
pe[w] = i;
pq.push(make_pair(d[w], w));
}
}
}
}
}
if (!used[t]){
break;
}
for (int i = 0; i < N; i++){
if (used[i]){
h[i] -= d[t] - d[i];
}
}
Cap c = min(m[t], F - flow);
for (int i = t; i != s; i = pv[i]){
G[pv[i]][pe[i]].cap -= c;
G[i][G[pv[i]][pe[i]].rev].cap += c;
}
flow += c;
cost += c * (-h[s]);
}
return make_pair(flow, cost);
}
};

int main() {
cin.tie(nullptr) -> sync_with_stdio(false);

int n, m;
cin >> n >> m;

int sv = 0, tv = n+1;
primal_dual<int, ll> g(tv+1);
rep(i, m) {
int u, v, w;
cin >> u >> v >> w;
}

ll ans = g.min_cost_flow(sv, tv, 2).second;
cout << ans << '\n';

return 0;
}


Ncik
2天前
// 原始对偶
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define INF 1e18

using namespace std;
using ll = long long;

template <typename Cap, typename Cost>
struct primal_dual {
struct edge{
int to, rev;
Cap cap;
Cost cost;
edge(int to, int rev, Cap cap, Cost cost): to(to), rev(rev), cap(cap), cost(cost) {}
};
int N;
vector<vector<edge>> G;
primal_dual(){}
primal_dual(int N): N(N), G(N){}
void add_edge(int from, int to, Cap cap, Cost cost){
int id1 = G[from].size();
int id2 = G[to].size();
G[from].push_back(edge(to, id2, cap, cost));
G[to].push_back(edge(from, id1, 0, -cost));
}
pair<Cap, Cost> min_cost_flow(int s, int t, Cap F){
Cap flow = 0;
Cost cost = 0;
vector<Cost> h(N, 0);
while (flow < F){
vector<Cap> m(N, INF);
vector<Cost> d(N, INF);
vector<int> pv(N, -1);
vector<int> pe(N, -1);
vector<bool> used(N, false);
priority_queue<pair<Cost, int>, vector<pair<Cost, int>>, greater<pair<Cost, int>>> pq;
pq.push(make_pair(0, s));
d[s] = 0;
while (!pq.empty()){
int v = pq.top().second;
pq.pop();
if (!used[v]){
used[v] = true;
if (v == t){
break;
}
int cnt = G[v].size();
for (int i = 0; i < cnt; i++){
int w = G[v][i].to;
if (!used[w] && G[v][i].cap > 0){
Cost tmp = G[v][i].cost - h[w] + h[v];
if (d[w] > d[v] + tmp){
d[w] = d[v] + tmp;
m[w] = min(m[v], G[v][i].cap);
pv[w] = v;
pe[w] = i;
pq.push(make_pair(d[w], w));
}
}
}
}
}
if (!used[t]){
break;
}
for (int i = 0; i < N; i++){
if (used[i]){
h[i] -= d[t] - d[i];
}
}
Cap c = min(m[t], F - flow);
for (int i = t; i != s; i = pv[i]){
G[pv[i]][pe[i]].cap -= c;
G[i][G[pv[i]][pe[i]].rev].cap += c;
}
flow += c;
cost += c * (- h[s]);
}
return make_pair(flow, cost);
}
};

int main() {
cin.tie(nullptr) -> sync_with_stdio(false);

int n, m, s, t;
cin >> n >> m >> s >> t;

primal_dual<int, ll> g(n+1);
rep(i, m) {
int u, v, c, w;
cin >> u >> v >> c >> w;
}

auto [flow, cost] = g.min_cost_flow(s, t, INF);
cout << flow << ' ' << cost << '\n';

return 0;
}


Ncik
2天前
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::max;
using std::vector;

const int MX = 300005;

int n, m;
vector<int> to[MX];
int dist[MX];
int dep[MX];
vector<int> co[MX];

int par[MX][20];
void dfs(int v, int p=0) {
for (int i = 1; i < 20; ++i) {
par[v][i] = par[par[v][i-1]][i-1];
}
rep(i, to[v].size()) {
int u = to[v][i];
if (u == p) continue;
dist[u] = dist[v] + co[v][i];
dep[u] = dep[v]+1;
par[u][0] = v;
dfs(u, v);
}
}

int LCA(int a, int b) {
if (dep[a] > dep[b]) std::swap(a, b);
int gap = dep[b]-dep[a];
for (int i = 19; i >= 0; --i) {
int len = 1<<i;
if (gap >= len) {
gap -= len;
b = par[b][i];
}
}
if (a == b) return a;
for (int i = 19; i >= 0; --i) {
int na = par[a][i];
int nb = par[b][i];
if (na != nb) a = na, b = nb;
}
return par[a][0];
}

int d[MX];
void dfs2(int v, int p=0) {
for (int u : to[v]) {
if (u == p) continue;
dfs2(u, v);
d[v] += d[u];
}
}

int len[MX], s[MX], t[MX], lca[MX];
bool judge(int x) {
int cnt = 0, mx = 0;
memset(d, 0, sizeof d);
rep(i, m) {
if (len[i] > x) {
d[s[i]]++;
d[t[i]]++;
d[lca[i]] -= 2;
mx = max(mx, len[i]-x);
cnt++;
}
}
dfs2(1);
for (int v = 2; v <= n; ++v) { // d[i]==cnt意味着它是交集
if (d[v] == cnt and dist[v]-dist[par[v][0]] >= mx) return true;
}
return false;
}

int main() {
cin >> n >> m;

rep(i, n-1) {
int a, b, t;
cin >> a >> b >> t;
to[a].push_back(b); co[a].push_back(t);
to[b].push_back(a); co[b].push_back(t);
}

dfs(1);

rep(i, m) {
cin >> s[i] >> t[i];
lca[i] = LCA(s[i], t[i]);
len[i] = dist[s[i]] - dist[lca[i]] + dist[t[i]] - dist[lca[i]];
}

int wa = -1, ac = 1001001001;
while (abs(wa-ac) > 1) {
int wj = (wa+ac)/2;
if (judge(wj)) ac = wj; else wa = wj;
}

cout << ac << '\n';

return 0;
}


Ncik
3天前

### 算法

##### (二分答案、贪心、LCA、树上差分) $O(n\log n)$

$m=1$

#### C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::max;
using std::vector;

const int MX = 300005;

int n, m;
vector<int> to[MX];
int dist[MX];
int dep[MX];
vector<int> co[MX];

int par[MX][20];
void dfs(int v, int p=0) {
for (int i = 1; i < 20; ++i) {
par[v][i] = par[par[v][i-1]][i-1];
}
rep(i, to[v].size()) {
int u = to[v][i];
if (u == p) continue;
dist[u] = dist[v] + co[v][i];
dep[u] = dep[v]+1;
par[u][0] = v;
dfs(u, v);
}
}

int LCA(int a, int b) {
if (dep[a] > dep[b]) std::swap(a, b);
int gap = dep[b]-dep[a];
for (int i = 19; i >= 0; --i) {
int len = 1<<i;
if (gap >= len) {
gap -= len;
b = par[b][i];
}
}
if (a == b) return a;
for (int i = 19; i >= 0; --i) {
int na = par[a][i];
int nb = par[b][i];
if (na != nb) a = na, b = nb;
}
return par[a][0];
}

int d[MX];
void dfs2(int v, int p=0) {
for (int u : to[v]) {
if (u == p) continue;
dfs2(u, v);
d[v] += d[u];
}
}

int len[MX], s[MX], t[MX], lca[MX];
bool judge(int x) {
int cnt = 0, mx = 0;
memset(d, 0, sizeof d);
rep(i, m) {
if (len[i] > x) {
d[s[i]]++;
d[t[i]]++;
d[lca[i]] -= 2;
mx = max(mx, len[i]-x);
cnt++;
}
}
dfs2(1);
for (int v = 2; v <= n; ++v) { // d[i]==cnt意味着它是交集
if (d[v] == cnt and dist[v]-dist[par[v][0]] >= mx) return true;
}
return false;
}

int main() {
cin >> n >> m;

rep(i, n-1) {
int a, b, t;
cin >> a >> b >> t;
to[a].push_back(b); co[a].push_back(t);
to[b].push_back(a); co[b].push_back(t);
}

dfs(1);

rep(i, m) {
cin >> s[i] >> t[i];
lca[i] = LCA(s[i], t[i]);
len[i] = dist[s[i]] - dist[lca[i]] + dist[t[i]] - dist[lca[i]];
}

int wa = -1, ac = 1001001001;
while (abs(wa-ac) > 1) {
int wj = (wa+ac)/2;
if (judge(wj)) ac = wj; else wa = wj;
}

cout << ac << '\n';

return 0;
}