acmclub专题
ACMclub - 2131 产生冠军（拓扑排序，map）
题目连接 1、成环矛盾 2、不全在同一集合则无法产生冠军。 #define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <string>using namespace std;int N, M;const int M
ACMclub 2117 确定比赛名次（拓扑排序）
题目连接 直接排序 #define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <cstdio>#include <cstring>using namespace std;int N, M;const int MAXN = 501, MAXM = MAXN*MAXN/2;int g[MAXN][MAXN], i
ACMclub - 1123 确定排序序列（拓扑排序）
题目连接 三种情况 1、成环矛盾 2、不能确定排序 3、确定 #define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <cstdio>#include <cstring>using namespace std;int N, M;const int MAXN = 27, MAXM = 1000;int
ACMclub - 1122 关系推断 （拓扑排序， 并查集）
题目连接 题目描述 给你一些已经确定的元素之间的关系，请你判断是否能从这些元素关系中推断出其他的元素关系。 将小于关系的两个点建立一个边。 拓扑排序： (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止. 用并查集判断是否
ACMclub - 1124 成语接龙 （最短路，SPFA）
题目连接 给出N个字符串，要将字符串处理分离出前4个字符和后4个字符，然后建图。 由于N最大是1000，O（N^2）是可以接受的，所以直接查找前面的点，判断是否符合条件了。不过还可以用HASH吧，这样时间复杂度会小很多，主要是SPFA的时间了，由于SPFA不太熟悉，不然用Bellman-Ford或者Dijkstra在这题的数据都可以的，不过Bellman-ford的O（NM）就有点危险了。