https://vjudge.net/contest/174020
A.100条双向边，每个点最少连2个边
所以最多100个点，点的标号需要离散化
然后要求恰好经过n条路径
快速幂，乘法过程就是floyed就行了
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std; const int maxn = ; int n, m, s, t, b, c[]; struct matrix {
int c[][];
matrix() {
memset(c, 0x3f, sizeof c);
}
void add(int u, int v, int w) {
c[u][v] = c[v][u] = w;
}
matrix operator * (const matrix &a) const {
matrix b;
for(int k = ;k <= n;k ++)
for(int i = ;i <= n;i ++)
for(int j = ;j <= n;j ++)
b.c[i][j] = min(b.c[i][j], c[i][k] + a.c[k][j]);
return b;
}
matrix operator ^ (int &k) {
matrix b = *this;
for(k --;k > ;k >>= , *this = (*this) * (*this))
if(k & ) b = b * (*this);
return b;
}
}; int main() {
matrix g;
int u, v, w;
scanf("%d %d %d %d", &n, &m, &s, &t);
while(m --) {
scanf("%d %d %d", &w, &u, &v);
if(!c[u]) c[u] = ++ b;
if(!c[v]) c[v] = ++ b;
g.add(c[u], c[v], w);
}
swap(b, n);
printf("%d", (g ^ b).c[c[s]][c[t]]);
return ;
}
B.
C.非常裸的生成树计数问题
其实谁是最高管理层并没什么卵用
想当然理解了读入，垃圾题目有重边
注意有重边，整数行列式计算可以拿来当板子了
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std; const int maxn = ; int n, m, s, t, b, c[]; struct matrix {
int c[][];
matrix() {
memset(c, 0x3f, sizeof c);
}
matrix(int x) {
memset(c, , sizeof c);
for(int i = ;i <= n;i ++)
c[i][i] = ;
}
void add(int u, int v, int w) {
c[u][v] = c[v][u] = w;
}
matrix operator * (const matrix &a) const {
matrix b;
for(int k = ;k <= n;k ++)
for(int i = ;i <= n;i ++)
for(int j = ;j <= n;j ++)
b.c[i][j] = min(b.c[i][j], c[i][k] + a.c[k][j]);
return b;
}
matrix operator ^ (int &k) {
matrix b = *this;
for(k --;k > ;k >>= , *this = (*this) * (*this))
if(k & ) b = b * (*this);
return b;
}
}; int main() {
matrix g;
int u, v, w;
scanf("%d %d %d %d", &n, &m, &s, &t);
while(m --) {
scanf("%d %d %d", &w, &u, &v);
if(!c[u]) c[u] = ++ b;
if(!c[v]) c[v] = ++ b;
g.add(c[u], c[v], w);
}
swap(b, n);
printf("%d", (g ^ b).c[c[s]][c[t]]);
return ;
}
D.
E.高中做过的网络流模型
每行被隔开的算一块，st向这些块连边流量为1
因为这样一个块里最多放一个棋子
每列被隔开的算一块，这些块向en连边流量为1，道理同上
行块和列快相遇出可以放旗子，那么它们连一条边流量为1
因为只有一个位置
求个最大流...这样一说直接二分图上匈牙利就可以了...
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int maxn = , maxm = , inf = 0x3f3f3f3f; int s, t, len = , g[maxn]; struct edge {
int to, cap, next;
}e[maxm]; int p[maxn], q[maxn], d[maxn]; void add(int u, int v, int w) {
e[++ len] = (edge){v, w, g[u]}, g[u] = len;
e[++ len] = (edge){u, , g[v]}, g[v] = len;
} bool bfs() {
int l = , r = , x, i;
memset(d, , sizeof d);
d[s] = , q[] = s;
while(l <= r) {
x = q[l ++];
for(i = g[x];i;i = e[i].next)
if(e[i].cap && !d[e[i].to])
d[e[i].to] = d[x] + , q[++ r] = e[i].to;
}
return d[t];
} int dfs(int x, int y) {
if(x == t || y == ) return y;
int flow = ;
for(int &i = p[x];i;i = e[i].next) {
if(!e[i].cap || d[e[i].to] != d[x] + ) continue;
int f = dfs(e[i].to, min(y, e[i].cap));
flow += f, y -= f;
e[i].cap -= f, e[i ^ ].cap += f;
if(!y) break;
}
return flow;
} int dinic() {
int maxflow = ;
while(bfs()) {
memcpy(p, g, sizeof g);
maxflow += dfs(s, inf);
}
return maxflow;
} int n, m, cnt; char str[][]; int mmp[][]; int main() {
t = ;
while(~scanf("%d", &n)) {
m = ;
memset(g, , sizeof g);
for(int i = ;i <= n;i ++)
scanf("%s", str[i] + );
for(int i = ;i <= n;i ++) {
for(int j = ;j <= n;j ++) {
if(str[i][j] == 'X') mmp[i][j] = -;
else {
if(j == || str[i][j - ] == 'X') m ++, add(s, m, );
mmp[i][j] = m;
}
}
}
for(int j = ;j <= n;j ++)
for(int i = ;i <= n;i ++) {
if(str[i][j] != 'X') {
if(i == || str[i - ][j] == 'X') m ++, add(m, t, );
add(mmp[i][j], m, inf);
}
}
printf("%d\n", dinic());
}
}
F.裸的最短路，当然你要看到这是
单向边！！！
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm> using namespace std; const int maxn = ; queue <int> q; int n, m, k, t, d[maxn], vis[maxn]; vector <pair<int, int> > e[maxn]; int main(){
while(~scanf("%d %d %d", &n, &m, &k)) {
for(int i = ;i <= n;i ++) d[i] = 0x3f3f3f3f, e[i].clear();
for(int u, v, w, i = ;i <= m;i ++) {
scanf("%d %d %d", &u, &v, &w);
e[u].push_back(make_pair(v, w));
//e[v].push_back(make_pair(u, w));
}
scanf("%d", &t);
for(int j, i = ;i <= t;i ++)
scanf("%d", &j), d[j] = , q.push(j);
while(!q.empty()) {
int u = q.front();
q.pop(), vis[u] = ;
for(int i = ;i < e[u].size();i ++) {
if(d[e[u][i].first] > d[u] + e[u][i].second) {
d[e[u][i].first] = d[u] + e[u][i].second;
if(!vis[e[u][i].first]) vis[e[u][i].first] = , q.push(e[u][i].first);
}
}
}
printf("%d\n", d[k] == 0x3f3f3f3f ? - : d[k]);
}
return ;
}
G.裸MST，稠密图没有卡 Kruskal，良心！
#include <cstdio>
#include <algorithm> using namespace std; struct edge {
int u, v, w;
bool operator < (const edge &a) const {
return w < a.w;
}
}e[]; int n, f[]; int find_(int x) {
if(f[x] != x) return f[x] = find_(f[x]);
return x;
} int main() {
while(~scanf("%d", &n)) {
int m = , ans = ;
for(int k, i = ;i <= n;i ++) {
f[i] = i;
for(int j = ;j <= i;j ++) scanf("%d", &k);
for(int j = i + ;j <= n;j ++) scanf("%d", &k), e[++ m] = (edge){i, j, k};
}
sort(e + , e + m + );
for(int u, v, i = , j = ;j < n;i ++) {
u = find_(e[i].u), v = find_(e[i].v);
if(u == v) continue;
f[v] = u, j ++, ans += e[i].w;
}
printf("%d\n", ans);
}
return ;
}
H.
I.经典网络流模型
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int maxn = , maxm = , inf = 0x3f3f3f3f; int s, t, len = , g[maxn]; struct edge {
int to, cap, next;
}e[maxm]; int p[maxn], q[maxn], d[maxn]; void add(int u, int v, int w) {
e[++ len] = (edge){v, w, g[u]}, g[u] = len;
e[++ len] = (edge){u, , g[v]}, g[v] = len;
} bool bfs() {
int l = , r = , x, i;
memset(d, , sizeof d);
d[s] = , q[] = s;
while(l <= r) {
x = q[l ++];
for(i = g[x];i;i = e[i].next)
if(e[i].cap && !d[e[i].to])
d[e[i].to] = d[x] + , q[++ r] = e[i].to;
}
return d[t];
} int dfs(int x, int y) {
if(x == t || y == ) return y;
int flow = ;
for(int &i = p[x];i;i = e[i].next) {
if(!e[i].cap || d[e[i].to] != d[x] + ) continue;
int f = dfs(e[i].to, min(y, e[i].cap));
flow += f, y -= f;
e[i].cap -= f, e[i ^ ].cap += f;
if(!y) break;
}
return flow;
} int dinic() {
int maxflow = ;
while(bfs()) {
memcpy(p, g, sizeof g);
maxflow += dfs(s, inf);
}
return maxflow;
} int Case, n, m, sum; int main() {
scanf("%d", &Case);
for(int tt = ;tt <= Case;tt ++) {
sum = , len = ;
memset(g, , sizeof g);
printf("Case #%d: ", tt);
scanf("%d %d", &n, &m), t = n + m + ;
for(int j, i = ;i <= n;i ++)
scanf("%d", &j), add(s, i, j), sum += j;
for(int j, i = ;i <= m;i ++)
scanf("%d", &j), add(n + i, t, j);
for(int k, j, i = ;i <= n;i ++) {
scanf("%d", &k);
while(k --) {
scanf("%d", &j);
add(i, n + j + , inf);
}
}
for(int k, i = ;i <= m;i ++)
for(int j = ;j <= m;j ++) {
scanf("%d", &k);
if(k) add(n + i, n + j, inf);
}
printf("%d\n", sum - dinic());
}
return ;
}
J.随便做的傻逼题，我写的算麻烦的
#include <cstdio>
#include <algorithm> using namespace std; int n, a[]; int main() {
scanf("%d", &n);
for(int i = ;i <= n;i ++)
scanf("%d", &a[i]);
int l = , r = n;
while(!a[l] && l <= n) l ++;
while(!a[r] && r >= ) r --;
if(l > r) puts("");
else {
int ans = , last = ;
for(int i = l + ;i <= r;i ++) {
if(a[i]) {
ans ++;
if(last != ) last = ;
}
else {
if(last != ) {
if(i < r && !a[i + ]) last = ;
else ans ++;
}
}
}
printf("%d\n", ans);
}
return ;
}