bupt summer training for 16 #6 —

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 ;

 }

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 ;

 }

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 ;

 }

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 ;

 }

巴特西

bupt summer training for 16 #6 ——图论

最新文章

热门文章