**解题报告：**这还是个定理吧，就是说我们可以删掉最小生成树的一条树边，然后加上该点的树边，就能形成一个生成树，（如上图p2，绿色的边是两个点之间的最长树边，我们可以把他删掉，加上蓝色的边，这样并不影响它的连通性，所以他还是生成树）那么就一定有他的值是sum-l+w，为了让这个值最小并且比sum大，sum指的是最小生成树所有和，那么一定要找到a,b之间的最大树边（a,b指的是w边的两个顶点），这个可以dfs做，然而这样并不一样对，看上图p3,墨染空大佬就指出了一个错误，当两点之间的距离如果等于这条边，在原做法里面就不会更新了，然而我们可以更新次大值，不得不说是真的强啊。当然在dfs的时候，我...

其实我个人的看法，觉得差分约束最难的还是要把问题的限制想全，如果遗漏了一个点肯定错，然后求最大值就是<=k1,k2,k3,因为都要满足所以肯定要求k里面的最小值，最短路，求最小值>=k1,k2,k3，就是求最大值，最长路。最短路对应负环，最长路对应正环，如果传统队列的spfa太慢那就考虑把队列换成栈，不过一般情况下不要乱用，在更新值的方面，队列比栈要快不少。 模板题，看清楚题目问的最值是最小还是最大，该题是最小那么我们求最长路，最长路对应的是>=，即a>=b+w，a,b分别为端点，w为边权，如果存在正环就输出无解。 #include<iostream> ...

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue> #include<set> #define IL inline #define x first #define y second typedef long long ll; using namespace std; c...

当一头牛的出度为0他一定是受欢迎的牛。 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=10010,M=50010; int h[N],ne[M],e[M],idx; int s[N],dfn[N],low[N],timestamp,cnt; int Size[N],id[N]; bool is[N]; int n,m; int top; int dout[N]; void add(int a,int b) { ...

题目大致意思：给定一个图，问最少激活多少个点可以遍历整个图，至少加几条边可以让每个点都能到达任何点（成为一个大连通分量）。 第一个问题很简单，只要让入度为0的起点都激活，肯定能遍历所有点，第二个答案是max（起点个数，终点个数），类似于这样，记录规律就行了。。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #inc...

解题思路：只要找一个最长的链，因为不需要两个点互相到达，只需要一个点能到另一个点就行了，但是这条链不能分叉，先tarjan，缩点，建新图，然后用递推思想，从ssc_cnt开始递减，按照拓扑序做，g[]数组代表以i点为终点的方案数，f[]数组代表以i为终点集合中点的数量。如果f[k]<f[i]+size[k] g[k]=g[i],更新f[k]，如果相等g方案数相加就行了。 #include<iostream> #include<cstring> #include<cstdio> #include<set> using namespace s...

解题报告：这题其实可以差分约束做。但是spfa跑太慢了，我们今天来讲一个线性的做法，tarjan，因为图中没有负点，如果图中存在正环就说明存在和为正数的强联通分量，然后最后问的所有亮度和，可以求出每个连通分量的个数再乘以亮度，亮度可以跑在长路，按照拓扑序的做法。 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=100010,M=600010; typedef long long ll; int h[N],hs[N],e[M...

解题报告：二分出来答案，让小于等于答案的罪犯放在同一个监狱，让大于答案的放在另一个监狱，看是否染色成功。 #include<iostream> #include<cstring> using namespace std; const int N=20010,M=200010; int h[N],e[M],ne[M],w[M],idx; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } int n,m; int color[N]; bool dfs(i...

1123 铲雪车 解题报告：这题其实不知道欧拉路径也能做出来，由于铲雪车在路径上，那么只要算出来所有路径长*2，因为两边都要铲，除以速度就是答案了。 #include<iostream> #include<cmath> using namespace std; double get_dis(int x1,int y1,int x2,int y2) { return sqrt(1.0*(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } int main() { int x,y; cin>>x&g...

解题报告：拓扑排序的板子题，不想说了。 #include<iostream> #include<cstring> using namespace std; const int N=110,M=10010; int q[N]; bool st[N]; int n; int h[N],e[M],ne[M],idx; int tt=-1,hh=0; int din[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int cnt; int ans[N]; int main() ...

实在太菜了，之前做过的模板还是给忘记了，wa10000次才刻骨铭心。 #include<iostream> #include<cstring> using namespace std; const int N=200010; typedef long long ll; int h[N],ne[N],w[N],idx,e[N]; int n; ll ans=-1e18; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } ll dfs(int u,int fa) { ll d1...

这题讲讲思路吧，告诉你两个数，算出他们俩能组成哪些数，其实就是裴蜀定理的应用，他们gcd的倍数都可以组成，只要判断奇偶性就行了。 dfs题，我卡了太久了，按照不同辆小车dfs就行啦。 #include<iostream> #include<cstring> #include<queue> #include<map> using namespace std; typedef pair<int,int> pii; int n,m,k; int dx[4]={ 1,-1,0,0},dy[4]={ 0,0,1,-1}; c...

解题报告：看似像博弈论的问题，其实就是在询问当两个点在一个集合了就结束游戏了，并查集处理就行了。 #include<iostream> using namespace std; const int N=210,M=N*N; int p[M]; int n,m; int get(int x,int y) { return x*n+y; } int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { cin>>n&g...

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue> #include<set> #define IL inline #define x first #define y second typedef long long ll; using namespace std; i...