D. Sorting It All Out
Description
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A,B,C,D implies that A<B, B<C and C<D. in this problem, we will give you a set of relations of the form A<Band ask you to determine whether a sorted order has been specified or not.
Input
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n
and m. the first value indicated the number of objects to sort, where 2≤n≤26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A<B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character “<” and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n=m=0 indicate end of input.
Output
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after xxx relations: yyy…y. Sorted sequence cannot be determined. Inconsistency found after xxx relations. where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy…y is the sorted, ascending sequence.
Samples
Input 复制
4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0
Output
Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.
考虑拓扑排序，有非常明显的从局部的特征到整体的特征之间的特点，拓扑排序可以跳转博客
因为数据范围足够小，并且题目要求输出循环次数，说明跑拓扑排序是完全没问题的
当入度为0的点有多个的情况下，可以得到答案不唯一的结果，当vector中的点的数量小于n的情况下，说明此时有1环，即有冲突，当以上两种情况均在循环中没有发生，即得不到答案
const int maxn = 1e6+7; int n,m; vector<int> vet; int a[30][30]; int deg[30]; int teg[30]; string s[30000]; int topSort(){ queue<int> que; int cnt = 0; for(int i=1;i<=n;i++){ if(deg[i] == 0) que.push(i); teg[i] = deg[i]; } vet.clear(); int flag = 0; while(que.size()){ if(que.size() > 1) flag = 1; int top = que.front(); que.pop(); int tot = 0; vet.push_back(top); for(int i=1;i<=n;i++){ if(a[top][i]){ teg[i] --; if(teg[i] == 0){ que.push(i); } } } } if(vet.size() < n) return 0;///huan if(flag == 1) return 1;/// return 2; } int main() { ///freopen("1.in","r",stdin); while(cin >> n >> m){ if(n == 0 && m == 0) break; for(int i=1;i<=m;i++) cin >> s[i]; int flag = 0; int siz; memset(a,0,sizeof a); memset(deg,0,sizeof deg); for(int i=1;i<=m;i++){ int u = s[i][0]; int v = s[i][2]; u -= 'A'; u ++; v -= 'A'; v ++; deg[v] ++; a[u][v] = 1; siz = topSort(); if(siz == 2){ printf("Sorted sequence determined after %d relations: ",i); for(int i=0;i<n;i++) printf("%c",vet[i] + 'A' - 1); puts("."); flag = 1; break; } else if(siz == 0){ printf("Inconsistency found after %d relations.\n",i); flag = 1; break; } } if(flag == 0) puts("Sorted sequence cannot be determined."); } return 0; }
F. 走廊泼水节
Description
给定一棵N个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。求增加的边的权值总和最小是多少。我们一共有N个OIER打算参加这个泼水节，同时很凑巧的是正好有N个水龙头(至于为什么，我不解释)。N个水龙头之间正好有N−1条小道，并且每个水龙头都可以经过小道到达其他水龙头(这是一棵树，你应该懂的…)。但是OIER门为了迎接中中的挑战，决定修建一些个道路(至于怎么修，秘密～),使得每个水龙头到每个水龙头之间都有一条直接的道路连接(也就是构成一个完全图呗～)。但是OIER门很懒得，并且记性也不好，他们只会去走那N-1条小道，并且希望所有水龙头之间修建的道路，都要大于两个水龙头之前连接的所有小道(小道当然要是最短的了)。所以神COW们，帮那些OIER们计算一下吧，修建的那些道路总长度最短是多少，毕竟修建道路是要破费的～
Input
多组数据，第一行t，表示有t组测试数据，对于每组数据：第一行N，表示水龙头的个数（当然也是OIER的个数）；
2到N行，每行三个整数X,Y,Z；表示水龙头X和水龙头Y有一条长度为Z的小道
Output
对于每组数据，输出一个整数，表示修建的所有道路总长度的最短值。
Samples
Input
2 3 1 2 2 1 3 3 4 1 2 3 2 3 4 3 4 5
Output
4 17
Hint
第一组数据，在2和3之间修建一条长度为4的道路，是这棵树变成一个完全图，且原来的树依然是这个图的唯一最小生成树.
每个测试点最多10组测试数据
50%: n≤1500;
100%: n≤6000
100%: z≤100
克鲁斯卡尔思想，分享一片比较好的 博文
要用到并查集维护联通块，如果说再给两个本来不连通的连通块连上一条边之后，增加的边的数量是siz_a * siz_b - 1;
因为还不能破坏之前存在的最小生成树（假设边权为w）,那么来说新增加的边权至少是w + 1;
const int maxn = 5e5 + 7; const double eps = 1e-6; int n, m; int T; struct node { int u, v, w; } e[maxn]; bool cmp(node a, node b) { return a.w < b.w; } int fa[maxn]; int find(int x) { if(x == fa[x]) return x; else return fa[x] = find(fa[x]); } int siz[maxn]; void init() { for(int i = 1; i <= n; i++) { fa[i] = i; siz[i] = 1; } } int main() { cin >> T; while(T --) { n = read; init(); for(int i = 1; i < n; i++) { e[i].u = read, e[i].v = read, e[i].w = read; } ll ans = 0; sort(e + 1, e + n, cmp); for(int i = 1; i < n; i++) { int fau = find(e[i].u); int fav = find(e[i].v); if(fau == fav) continue; else { fa[fau] = fav; ans += (e[i].w + 1) * (siz[fau] * siz[fav] - 1); siz[fav] += siz[fau]; } } cout << ans << '\n'; } return 0; }
G. 黑暗城堡
Description
在顺利攻破Lord lsp的防线之后，lqr一行人来到了Lord lsp的城堡下方。Lord lsp黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。现在lqr已经搞清楚黑暗城堡有N
个房间 (1≤N≤1000)，M条可以制造的双向通道，以及每条通道的长度。
lqr深知Lord lsp的想法，为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp一定会把城堡修建成树形的；但是，为了尽量提高自己的移动效率，Lord lsp一定会使得城堡满足下面的条件：设 D[i] 为如果所有的通道都被修建，第 i 号房间与第1号房间的最短路径长度；而 S[i] 为实际修建的树形城堡中第 i 号房间与第1号房间的路径长度；要求对于所有整数 i(1≤i≤N)，有 S[i]=D[i] 成立。
为了打败Lord lsp，lqr想知道有多少种不同的城堡修建方案。于是lqr向applepi提出了这个问题。因为applepi还要忙着出模拟赛，所以这个任务就交给你了。当然，你只需要输出答案对 231–1取模之后的结果就行了。
Input
第一行有两个整数N和M。
之后M 行，每行三个整数X,Y 和L，表示可以修建X 和Y之间的一条长度为L 的通道。
Output
一个整数，表示答案对 231–1
取模之后的结果。
Samples
Input 复制
3 3 1 2 2 1 3 1 2 3 1
Output
2
Hint
对于30% 的数据，2≤N≤5，M≤10。
对于50% 的数据，满足条件的方案数不超过10000。
对于100% 的数据，2≤N≤1000，N–1≤M≤N(N–1)/2，1≤L≤100
n的数据范围比较小，n 2 也是可以的，dijstra(),求出来最短路之后，可以直接使用乘法原理加取膜进行操作就好
const int maxn = 1e6+7; struct node{ int v; int w; int nex; }e[maxn]; bool vis[maxn]; ll dis[maxn]; int head[maxn]; int cnt = 0; int n,m; typedef pair<int,int> PII; void init(){ for(int i=1;i<=n;i++){ dis[i] = 0x3f3f3f3f; head[i] = -1; vis[i] = 0; } } void add(int u,int v,int w){ e[cnt].v = v; e[cnt].nex = head[u]; e[cnt].w = w; head[u] = cnt++; } void Dijkstra(int x){ dis[x] = 0; priority_queue<PII,vector<PII>,greater<PII> > que; que.push({dis[x],x}); while(que.size()){ PII cur = que.top(); que.pop(); int u = cur.second; if(vis[u]) continue; vis[u] = 1; for(int i=head[u];~i;i = e[i].nex){ int v = e[i].v; int w = e[i].w; if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w; que.push({dis[v],v}); } } } } ll ans = 1; const ll mod = (1L << 31) - 1L; int main() { cin >>n >> m; init(); for(int i = 1;i<=m;i++){ int u,v,w; cin >> u >> v >> w; add(u,v,w); add(v,u,w); } Dijkstra(1); for(int i=2;i<=n;i++){ int cnt = 0; for(int j = head[i];~j;j = e[j].nex){ int v = e[j].v; int w = e[j].w; if(dis[i] == dis[v] + w){ cnt ++; } } ans = (ans * cnt) % mod; ans %= mod; } cout<<ans<<'\n'; return 0; }
