1. 图论的反向建边
一般问题：有向图的多个起点到一个终点的最短距离 是最短路的变式。
我们只需要把图的箭头反向(正向变逆向,逆向变正向)
矩阵: mp[u,v] = cost ---->mp[v,u] = cost
邻接表也是类似的方法
[P2853 USACO06DEC] Cow Picnic S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这里为什么要反向建边，因为我们要牧场去找牛，相反的，我们可以让含有牛的牧场去找牧场。
2. DAG图的求点1到点n两点之间的最长路
关键问题是可能不止有点1是入度为0的点。如果不删除这些点，我们无法做到通过删点边的方式来求到1到n的路径。所以应该先遍历一次从点2到点n的入度为0的点找到那些点，再把延伸出来的点的入度 −1，如果这些点入读 −1后又变成了入度为 0 的点，那么再做同样的处理。至于一个点的最长路的转移方程就是：
max{入度1+相应的边,入度2+相应的边……入度n加相应的边} 类似于dijkstra的更新距离操作。
vector<int>g[1505];
vector<int>d[1505];
queue<int>q;
int v[1505];//存最长路
int n,m;
int ru[1505];
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,val;
cin>>u>>v>>val;
g[u].eb(v);
d[u].eb(val);
ru[v]++;
}
for(int i=2;i<=n;i++){
v[i] = -inf;
if(!ru[i]) q.push(i);
}
while(!q.empty()){
int x = q.front();
q.pop();
for(int i=0;i<g[x].size();i++){
if(!(--ru[g[x][i]])) q.push(g[x][i]);
}
}
q.push(1);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i=0;i<g[x].size();i++){
if(v[g[x][i]]<v[x]+d[x][i]) v[g[x][i]] = v[x]+d[x][i];
if(!(--ru[g[x][i]])) q.push(g[x][i]);
}
}
if(v[n] == -inf) cout<<"-1"<<endl;
else cout<<v[n]<<endl;
}
3. m条直线交点（三点不重合）的情况数计算
n=4 的情况：
1)4 条直线全部平行，则 0 交点 { =4*(4-4)}。
2)其中 3 条直线平行，则 3 交点 { =3*(4-3) }。
3)其中 2 条直线平行，则这2条直线与另2条直线的交点数为4,而另2条直线之间可能有0个或1个交点（见 n=2 的情况,共 4 个交点或 5 个交点。{=2*(4-2)+0 或 1 }
4)4 条直线均不平行（可看成 1 条直线平行），这 1 条直线与其它 3 条直线的交点数为 3，而其 它 3 条直线之间的交点数为 3，共 6 个交点。{ =1*(4-1)+3 }
结论：m 条直线的交点方案=r 条平行线与（m-r）条直线交叉的交点数+（m-r）条直线本身的交点方案
=r*(m-r)+(m-r)条直线本身的交点方案 （1<=r<=m）
- 写成递归程序
void g(int n,int k){ //交点数k n是平行线数量
if(n==0) {f[k]=1;maxn = max(maxn,k);}
else {
for(int r=n;r>=1;r--){
g(n-r,(n-r)*r+k);
}
}
}
4. 最大公约数，最小公倍数的一些结论
- 求gcd() , 方法一是直接调用c++的库中的gcd函数。方法二：
ull gcd(ull a, ull b)
{
return b == 0 ? a : gcd(b, a % b);
}
- 求lcm()，方法是a*b/gcd(a,b)
ull lcm(ull a, ull b)
{
return a / gcd(a, b) * b; //这样写是防止a*b溢出。
}
-
一些固有知识：gcd(x,a0) = a1 ---> gcd(x/a1 , a0/a1) = 1 暂且叫它为结论p
lcm(x,b0) = b1 = x*b0/gcd(x,b0)
使用结论p我们可以得到：gcd(x , b0) = x*b0/b1 ----> gcd(b1/b0 , b1/x) = 1 结论q
用心体会这两个式子，你会发现x是a1的整数倍而且是b1的因子
如果我们知道a0,a1,b0,b1想要求x的个数，我们可以遍历1~sqrt(b1) 找到能整除的数，且满足结论p和结论q，就能找到x的情况了。
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int a0,a1,b0,b1; void solve(){ int t; cin>>t; while(t--){ cin>>a0>>a1>>b0>>b1; int p = a0/a1; int q = b1/b0; int cnt = 0; for(int i=1;i*i<=b1;i++){ if(b1%i==0){ if(i%a1==0&&gcd(i/a1,p)==1 && gcd(q,b1/i)==1) cnt++; int j = b1/i; if(i==j) continue; if(j%a1==0&&gcd(j/a1,p)==1&& gcd(q,b1/j)==1) cnt++; } } cout<<cnt<<endl; } }