void mirror(VS& s)
{
for (int i = 0; i < n; i ++ )
for (int j = 0, k = n - 1; j < k; j ++ , k -- )
swap(s[i][j], s[i][k]);
}
void rotate(VS& s)
{
for (int i = 0; i < n; i ++ )
for (int j = 0; j < i; j ++ )
swap(s[i][j], s[j][i]);
mirror(s);
}
矩阵
#include <iostream>
#include <cstring>
using namespace std;
template <int row, int col>
struct Matrix
{
int r, c;
long long ele[row][col];
Matrix() { throw "Please set row and column!"; }
Matrix(int a, int b) : r(a), c(b) { memset(ele, 0, sizeof(ele)); }
long long &operator()(int a, int b) { return ele[a][b]; }
Matrix &operator+=(Matrix oth) { return *this = *this + oth; }
Matrix &operator-=(Matrix oth) { return *this = *this - oth; }
Matrix &operator*=(Matrix oth) { return *this = *this * oth; }
};
template <int m, int n>
Matrix<m, n> operator+(Matrix<m, n> m1, Matrix<m, n> m2)
{
Matrix<m, n> ret;
for (int i = 0; i < m1.r; i++)
for (int j = 0; j < m1.c; j++)
ret(i, j) = m1(i, j) + m2(i, j);
return ret;
}
template <int m, int n>
Matrix<m, n> operator-(Matrix<m, n> m1, Matrix<m, n> m2)
{
Matrix<m, n> ret;
for (int i = 0; i < m1.r; i++)
for (int j = 0; j < m1.c; j++)
ret(i, j) = m1(i, j) + m2(i, j);
return ret;
}
template <int m, int n, int p>
Matrix<m, p> operator*(Matrix<m, n> m1, Matrix<n, p> m2)
{
Matrix<m, p> ret(m1.r, m2.c);
for (int i = 0; i < m1.r; i++)
for (int k = 0; k < m1.c; k++)
for (int j = 0; j < m2.c; j++)
ret(i, j) += m1(i, k) * m2(k, j);
return ret;
}
template <int m, int n>
Matrix<m, n> operator^(Matrix<m, n> mat, long long k)
{
Matrix<m, n> ans = mat;
for (k--; k; mat *= mat, k >>= 1)
if (k & 1)
ans *= mat;
return ans;
}
template <int m, int n, int p>
Matrix<m, p> mulmod(Matrix<m, n> m1, Matrix<n, p> m2, int mod)
{
Matrix<m, p> ret(m1.r, m2.c);
for (int i = 0; i < m1.r; i++)
for (int k = 0; k < m1.c; k++)
for (int j = 0; j < m2.c; j++)
ret(i, j) = (ret(i, j) + m1(i, k) * m2(k, j) % mod) % mod;
return ret;
}
template <int m, int n>
Matrix<m, n> qpowmod(Matrix<m, n> mat, long long k, int mod)
{
Matrix<m, n> ans = mat;
for (k--; k; mat = mulmod(mat, mat, mod), k >>= 1)
if (k & 1)
ans = mulmod(ans, mat, mod);
return ans;
}
template <int m, int n>
ostream &operator<<(ostream &os, Matrix<m, n> &mat)
{
for (int i = 0; i < mat.r; i++)
{
for (int j = 0; j < mat.c; j++)
os << mat(i, j) << ' ';
os << endl;
}
return os;
}
template <int m, int n>
istream &operator>>(istream &is, Matrix<m, n> &mat)
{
for (int i = 0; i < mat.r; i++)
for (int j = 0; j < mat.c; j++)
is >> mat(i, j);
return is;
}
const int maxn = 105;
int main()
{
int n;
long long k;
const int p = 1e9 + 7;
cin >> n >> k;
Matrix<maxn, maxn> mat(n, n);
cin >> mat;
auto tmp = qpowmod(mat, k, p);
cout << tmp;
return 0;
}
最大牛(流)
EKKKK
bool bfs()
{
int hh = 0, tt = 0;
memset(st, false, sizeof st);
q[0] = S, st[S] = true, d[S] = INF;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (!st[ver] && f[i])
{
st[ver] = true;
d[ver] = min(d[t], f[i]);
pre[ver] = i;
if (ver == T) return true;
q[ ++ tt] = ver;
}
}
}
return false;
}
int EK()
{
int r = 0;
while (bfs())
{
r += d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
}
return r;
}
bool bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (d[ver] == -1 && f[i])
{
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T) return true;
q[ ++ tt] = ver;
}
}
}
return false;
}
int find(int u, int limit)
{
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i; // 当前弧优化
int ver = e[i];
if (d[ver] == d[u] + 1 && f[i])
{
int t = find(ver, min(f[i], limit - flow));
if (!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
2175. 飞行员配对方案问题 求方案
for (int i = 0; i < idx; i += 2)
if (e[i] > m && e[i] <= n && !f[i])
printf("%d %d\n", e[i ^ 1], e[i]);
作者:北海没有WA
链接:https:
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。