7.12Test——Graph Theory 1
1 path
1.1 Description
众所周知，Bfk经常为找不到路而烦恼
Bfk终于迎来了它高中以来第一个完整的暑假，它决定从假期里抽出一段时间去日本旅游。可是，对于连教师宿舍都找不到的Bfk来说，在旅途中不迷路是一件很困难的事情。为了避免迷路的尴尬，Bfk早早的就规划起了它的行程。它将日本的地图抽象成了一张n个点m条边的有向图，并在上面选定了行程的起点和终点，但它在规划旅行路径时却犯了难。它希望路径上的点都满足该点的出边所指向的点都能直接或间接的到达终点，这样即使它走错了路，也能重新规划路线到达终点。另外，它还希望旅行的路程尽可能短，以便节约更多的时间预习大学课程。
现在，Bfk找到了你，希望你能帮帮它。它不想为难你，因此你不用输出具体的方案，只需要告诉它满足条件的路径的最短长度就可以了
1.2 Input
第一行两个整数n和m，含义如题
接下来m行，每行三个整数u,v,l，描述一条从u指向v的单向边，长度为l
接下来一行两个整数s,t，表示起点和终点
1.3 Output
输出一行一个数字，表示满足要求的路径的最短长度
特别的，如果不存在这样的路径，则输出“-1”（不含引号）
1.4 Sample Input
|
3 2 1 2 2 1 1 3 |
1.5 Sample Input
|
-1 |
解释：起点为1号点，终点为3号点，此两点不连通，故输出-1
1.6 Note
对于 15% 的数据，n ≤ 10, m ≤ 20
对于 30% 的数据，n ≤ 100, m ≤ 2000
对于 50% 的数据，n ≤ 10000, m ≤ 200000
对于全部数据，n ≤ 100000, m ≤ 500000 ，数据有梯度
1.7 Hint
本题附有大样例，见下发文件
解析
此题与NOIP2014[寻找道路]类似
其实只需要建反边，先把t点能到的点打上标记，再给与没打标记的点直接相连的点打上不能去的标记，然后在可以到的点内正向跑最短路即可，其实好像将就反向跑最短路也行。注意打标记时开两个bool型数组，不然会误判
然而我考试是天真地以为建反边，tarjan缩点，拓扑排序，先删与t相连的边，一次删去入度为0的点的边，能被删的点就是能到的点，实际上当图中有环时，环上的点有些能走而有些不能走，这个画画图就可以知道
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100005, maxm = 500005; inline int read_(){ int rt = 0 ; char ch = getchar() ; while( ch < '0' || ch > '9' ) ch = getchar() ; while( ch >='0' && ch <='9' ) rt = (rt<<1)+(rt<<3) + ch - '0' , ch = getchar() ; return rt ; } int n, m, s, t; ll ans; int head[2][maxn], tot[2]; struct edge{ int nxt, to; ll d; }e[2][maxm]; void Addedge(int opt, int x, int y, ll d) { e[opt][++tot[opt]] = (edge){head[opt][x], y, d}; head[opt][x] = tot[opt]; } int que[maxn], h, tail; bool vis[maxn], used[maxn], col[maxn]; void check() { h = 1; que[++tail] = t; while(h <= tail) { int sta = que[h++]; for(int i = head[1][sta]; i; i = e[1][i].nxt) { int id = e[1][i].to; if(!vis[id]) que[++tail] = id; vis[id] = 1; } } vis[t] = 1; for(int i = 1; i <= n ; ++i) if(!vis[i]) { col[i] = 1; for(int j = head[1][i]; j; j = e[1][j].nxt) col[e[1][j].to] = 1; } if(col[s]) { printf("-1"); exit(0); } } ll dis[maxn]; priority_queue<pair<ll, int> > p; void Dijksra() { memset(dis, 0x3f, sizeof(dis)); dis[s] = 0; col[t] = 0; p.push(make_pair(0,s)); while(!p.empty()) { int sta = p.top().second; p.pop(); if(used[sta]) continue; used[sta] = 1; if(sta == t) return; for(int i = head[0][sta]; i; i = e[0][i].nxt) { int id = e[0][i].to; if(!col[id] && !used[id] && dis[id] > dis[sta] + e[0][i].d) { dis[id] = dis[sta] + e[0][i].d; p.push(make_pair(-dis[id], id)); } } } } int main() { freopen("path.in", "r", stdin); freopen("path.out", "w", stdout); n = read_();m = read_(); for(int i = 1; i <= m ; ++i) { int u = read_(), v = read_(); ll d; scanf("%lld", &d); Addedge(1, v, u, d); Addedge(0, u, v, d); } s = read_();t = read_(); check(); Dijksra(); printf("%lld", dis[t]); return 0; }
2 rabbit
2.1 Description
众所周知，Bfk家的后院有一片胡萝卜田
这片田地很受兔子们的喜爱，兔子们为了方便偷吃胡萝卜，在地下打出了一片洞穴网络。Bfk早就发现了它家的萝卜田里兔子泛滥的情形，因此，它决定先外出旅游几天，让兔子们放松警惕，回家时再将兔子们一网打尽。
具体的，我们可以将洞穴网络抽象成一个n条边的图。bfk的策略是，随机堵住某个节点，如果这个点是地下网络的必经之路，那么它就可以守洞待兔了。兔子们并不想坐以待毙，因此它们决定在某些节点挖出通向地面的出口，使得无论bfk堵住哪个节点，兔子们都可以直接从某个出口溜走。
但是兔子们只会计算1+1=2，对于如此复杂的问题，它们毫无头绪。请你帮忙计算一下，兔子们至少需要挖多少个出口才能满足上述条件，以及在出口数最少的情况下，出口的分布方式有多少种
2.2 Input
第一行两个正整数n，表示地下网络的边数
接下来n行，每行两个整数u,v，表示有一条双向边连通了u,v两点
2.3 Output
输出一行两个整数cnt,tot。其中，cnt表示最少出口数，tot表示在出口数最少的情况下，设置出口的方案数在模998244353意义下的值
2.4 Sample Input
由于样例较长，请在下发文件中查看输入样例
2.5 Sample Input
由于样例较长，请在下发文件中查看输出样例
2.6 Note
对于 20% 的数据，n ≤ 15
对于 40% 的数据，n ≤ 10000
对于 68% 的数据, n ≤ 100000
对于全部数据，n ≤ 2000000，数据有梯度
保证有 16% 的数据满足，该图任意两点间至少有两条点不重复的路径
保证无自环，但不保证无重边
2.7 Hint
本题读入数据量大，请使用读入优化
读入优化代码在下发文件readin.cpp中，其中read_()函数的作用是，读入一个数字，并将该数字通过返回值传递
解析
很容易想到要tarjan找割点，但我考场上就不会了接着操作了
实际上对于每个连通块，tarjan一次后，找到了每个割点，把点双看成一个点，那就是一颗树，貌似叫圆方树，显然，只有在每个叶子结点修洞才能满足一定可以逃出且修的洞最少，这里叶子结点一定是点双。对于没有割点的连通块，那就随便选两个点修洞就可以了
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 500005; const ll mod = 998244353; template<class T> void read(T &re) { re=0; T sign=1; char tmp; while((tmp=getchar())&&(tmp<'0'||tmp>'9')) if(tmp=='-') sign=-1; re=tmp-'0'; while((tmp=getchar())&&(tmp>='0'&&tmp<='9')) re=(re<<3)+(re<<1)+(tmp-'0'); re*=sign; } int cur, n, m, tot, num, cnt, cut, timer; ll ans; int dfn[maxn], low[maxn], vis[maxn]; bool may[maxn]; vector<int> G[maxn]; void tarjan(int x,int fa) { int cnt = 0; low[x] = dfn[x] = ++cur; for(unsigned i = 0; i < G[x].size(); i++) { if(!dfn[G[x][i]]) { tarjan(G[x][i], x); low[x] = min(low[x], low[G[x][i]]); if((++cnt > 1 && !fa) || (dfn[x] <= low[G[x][i]] && fa)) may[x] = 1; } else low[x] = min(low[x],dfn[G[x][i]]); } } void dfs(int x) { num ++; vis[x] = timer; for(unsigned int i = 0; i < G[x].size(); ++i) { int id = G[x][i]; if(may[id] && vis[id] != timer) { cut ++; vis[id] = timer; } if(!may[id] && !vis[id]) dfs(id); } } int main() { freopen("rabbit.in", "r", stdin); freopen("rabbit.out", "w", stdout); read(m); for(int i = 1; i <= m ; ++i) { int u, v; read(u);read(v); G[u].push_back(v); G[v].push_back(u); n = max(n,max(v, u)); } ans = 1; for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i, 0); for(int i = 1; i <= n ; ++i) { if(!may[i] && !vis[i]) { num = cut = 0; timer ++; dfs(i); if(cut == 0) { tot += 2; ans = ans * (ll)(1LL * num * (num - 1) / 2) % mod; } else if(cut == 1) { tot ++; ans = ans * 1LL * num % mod; } } } printf("%d %lld", tot, ans); return 0; }
3 construct
3.1 Description
Me懒得编题面了
给出一个n个点m条边的图，每条边有边长。现在我们钦定了一条边，要使该边一定出现在最小生成树中
你可以进行如下操作：将某条边的长度+1，并付出1的代价
最少需要付出多少代价可以满足要求呢？
3.2 Input
第一行三个整数n,m,id，分别表示点数，边数，被钦定的边的编号
接下来 行，每行三个整数u,v,d，表示一条连接u,v的路径，其长度为d
3.3 Output
输出一行一个数字，表示最少操作次数