近几日总结

CF1152D Neko and Aki’s Prank
假设根节点为1 ，那么所有的叶子结点深度必为偶数，我们对每个深度为偶数的点向上与它的父节点连边，选择该边，若冲突则不选，这样选择出来的边集就是最大的

接下来进行转换，对于深度为偶数的点，保证不冲突选边时会覆盖所有深度为奇数的点，所以选边的数量=深度为奇数点的数量

然后递推dpi,jdp_{i,j}dpi,j​表示 前$i+j$层，选了$i$个（，选了$j$个 ），转移时注意$i<=j$，那么对于$i+j$为奇数时对答案产生贡献

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;vector<vector<ll>> dp(n+1,vector<ll>(n+1));ll ans=0;for (int i=1;i<=n;i++){dp[i][0]=1;if (i&1) ans++;}for (int i=1;i<=n;i++){for (int j=1;j<=i;j++){dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;if ((i+j)&1) ans=(ans+dp[i][j])%mod;}}cout<<ans<<"\\n";return 0;
}

P3243 [HNOI2015]菜肴制作
显然要跑一个拓扑，但是题目要求并不是让字典序最小，而是尽量让序号小的数放在前面。
例二：先选1，后面可以选择5->2或4->3，如果让字典序最小，那么应该先选4->3，但是题目要求应该先让2尽快拓扑出来

反向建边跑字典序最小的拓扑，可以让小的尽可能放到后面

#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){int n,m;cin>>n>>m;vector<vector<int>> e(n+1);vector<int> ru(n+1);for (int i=1;i<=m;i++){int a,b;cin>>a>>b;e[b].push_back(a);ru[a]++;}priority_queue<int,vector<int>,less<int>> q;for (int i=n;i>=1;i--){if (!ru[i]){q.push(i);}}vector<int> ans;while (!q.empty()){int u=q.top();q.pop();ans.push_back(u);for (auto v:e[u]){ru[v]--;if (!ru[v]){q.push(v);}}}if (ans.size()!=n){cout<<"Impossible!\\n";return;}reverse(ans.begin(),ans.end());for (auto i:ans){cout<<i<<" ";}cout<<"\\n";}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T;cin>>T;while (T--){solve();}return 0;
}

P1038 [NOIP2003 提高组] 神经网络
跑拓扑然后按照题目公式算即可
注意当cu>0c_u>0cu​>0时，才会将兴奋值传递给%c_v%

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=105;
const int M=10005;struct edge{int v,w,next;
}e[M];
int head[N],cnt;void add(int u,int v,int w){++cnt;e[cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;vector<int> c(n+1),u(n+1);for (int i=1;i<=n;i++){cin>>c[i]>>u[i];}vector<int> ru(n+1),sym(n+1);for (int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;sym[x]=1;ru[y]++;add(x,y,z);}queue<int> q;for (int i=1;i<=n;i++){if (!ru[i]){q.push(i);}}vector<int> ans;while (!q.empty()){int uu=q.front();q.pop();for (int i=head[uu];i;i=e[i].next){int v=e[i].v;ru[v]--;if (c[uu]>0){c[v]+=e[i].w*c[uu];}if (!ru[v]){c[v]-=u[v];if (c[v]>0&&!sym[v]){ans.push_back(v);}q.push(v);}}}if (n==1&&m==0){cout<<"1 2";return 0;}if (ans.size()==0){cout<<"NULL";}else{sort(ans.begin(),ans.end());for (auto i:ans){cout<<i<<" "<<c[i]<<"\\n";}}return 0;
}

P5030 长脖子鹿放置
P3355 骑士共存问题
类似的二分图最大匹配问题
核心就是如何转换为二分图，对于二分图来说，首先考虑如何分出两个阵营，某个阵营内部是不会连边的，那么我们只需要找到题目中不可能连边的两个点即可

对于长脖子鹿问题，按行的奇偶分即可
对于骑士共存问题，按（行+列）的奇偶分即可

建图后跑最大匹配即可

P2573 [SCOI2012]滑雪
首先考虑第一个问题，最多能滑到多少个点，我们只要先跑一个dfs，找到所有能够到达的点，即最多能滑到的点

对于最短路程，由于我们能无限次使用时空胶囊，那么也就是相当于为我们的搜索提供了回溯操作，那么同一条边不会走两次，于是我们最短的路程就是删去一些边后，仍能到达删边前所有点 当前图留下的边之和，这与最小生成树很像，我们可以通过类似prim对点分析的操作，来贪心，但是由于是有向边，高度越高的点应该最先与1点连通，为此prim中的堆只需先按边终点的高度排序，再按边的长度排序即可。
用kruskal的话只需要预处理排序，正常跑最小生成树即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int M=2e6+5;
const int N=1e5+5;struct edge{int u,v,w;
}e[M];
int cnt,f[N];
bool vis[N];
vector<vector<int>> ee(N);void dfs(int u){for (auto v:ee[u]){if (vis[v]) continue;vis[v]=1;dfs(v);}
}int find(int x){if (f[x]!=x){f[x]=find(f[x]);}return f[x];
}
bool merge(int x,int y){if (find(x)!=find(y)){f[find(x)]=find(y);return 1;}return 0;
}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;vector<int> h(n+1);for (int i=1;i<=n;i++){cin>>h[i];}for (int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;if (h[a]>=h[b]){e[++cnt]=edge{a,b,c};ee[a].push_back(b);if (h[a]==h[b]){e[++cnt]=edge{b,a,c};ee[b].push_back(a);}}else{e[++cnt]=edge{b,a,c};ee[b].push_back(a);}}sort(e+1,e+cnt+1,[&](edge x,edge y){if (h[x.v]==h[y.v]){return x.w<y.w;}return h[x.v]>h[y.v];});vis[1]=1;dfs(1);for (int i=1;i<=n;i++){f[i]=i;}int tol=0;ll ans=0;for (int i=1;i<=cnt;i++){if ((!vis[e[i].v])||(!vis[e[i].u])) continue;if (merge(e[i].v,e[i].u)){tol++;ans+=e[i].w;}}cout<<tol+1<<" "<<ans;return 0;
}

P2505 [HAOI2012]道路
首先考虑最短路，必须有起点或终点，考虑最暴力的方法是，找出所有的最短路并记录路径然后依次计算贡献，显然时间复杂度不允许且实现比较复杂

如果我们按照题目，考虑图上某一条边，我们只需要找到该边有多少条最短路即可，假设我们现在固定图上起点$s$，找到从$s$出发的最短路，然后跑一遍dijkstra，实际上有很多条边的在从$s$出发去其它点的最短路上不会经过，假设我们删去这些边，那么最终构成的图一定是个无环图。

证明：假设有环，这个环在$s$到某个点的最短路上一定经过，那么这段环会对该条路产生贡献，一定有不走这个环的更短路线

然后我们再考虑固定起点$s$，固定一条边后如何计算该边的答案，设该边的起点为$u$，终点为$v$,从$s$到点$u$的路径条数记为cnt1ucnt1_ucnt1u​，从某个终点$t$到点$v$的路径条数为cnt2vcnt2_vcnt2v​，ansi=cnt1u∗cnt2vans_i=cnt1_u*cnt2_vansi​=cnt1u​∗cnt2v​ ，对于$cnt1$我们只需跑一遍拓扑dp求，对于$cnt2$我们通过跑反向的拓扑求。
要注意的是对于$cnt1$的求解，初始化只有起点$s$的cnt1s=1cnt1_s=1cnt1s​=1（起点已经固定，只需找有多少条分叉的路径即可）；而$cnt2$的求解，初始化需要每个点都赋为1（终点任意点都可以）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
const int M=5005;
const int N=1505;struct dij{int num,len;bool operator < (const dij &x)const{return len>x.len;}
};struct edge{int u,v,w,next;
}e[M],ee[M];
int head[N],headd[N],cntt,cnt,n,m;
ll ans[M];void ins(int u,int v,int w){e[++cnt]=edge{u,v,w,head[u]};head[u]=cnt;
}
void inss(int u,int v,int w){ee[++cntt]=edge{u,v,w,headd[u]};headd[u]=cntt;
}
void solve(int s){vector<bool> vis(n+1);vector<int> dis(n+1,1e9);priority_queue<dij> q;dis[s]=0;q.push({s,0});while (!q.empty()){dij x=q.top();q.pop();int u=x.num;if (vis[u]) continue;vis[u]=1;for (int i=head[u];i;i=e[i].next){int v=e[i].v,w=e[i].w;if (dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push({v,dis[v]});}}}// for (int i=1;i<=n;i++){//     cout<<dis[i]<<" ";// }// cout<<"\\n";vector<bool> good(m+1),goodd(m+1);vector<int> ru(n+1),ruu(n+1);for (int i=1;i<=m;i++){if (dis[e[i].u]+e[i].w==dis[e[i].v]){good[i]=1;ru[e[i].v]++;}if (dis[ee[i].v]+ee[i].w==dis[ee[i].u]){goodd[i]=1;ruu[ee[i].v]++;}}queue<int> q1,q2;vector<ll> cnt1(n+1),cnt2(n+1,1);for (int i=1;i<=n;i++){if (!ru[i]) q1.push(i),cnt1[i]=1;if (!ruu[i]) q2.push(i),cnt2[i]=1;}while (!q1.empty()){int u=q1.front();q1.pop();for (int i=head[u];i;i=e[i].next){if (!good[i]) continue;int v=e[i].v;cnt1[v]=(cnt1[v]+cnt1[u])%mod;ru[v]--;if (!ru[v]) q1.push(v);}}while (!q2.empty()){int u=q2.front();q2.pop();// cout<<u<<" ";for (int i=headd[u];i;i=ee[i].next){int v=ee[i].v;if (!goodd[i]) continue;ruu[v]--;cnt2[v]=(cnt2[v]+cnt2[u])%mod;if (!ruu[v]) q2.push(v);}}// for (int i=1;i<=n;i++){//     cout<<cnt1[i]<<" ";// }// for (int i=1;i<=n;i++){//     cout<<cnt2[i]<<" ";// }// cout<<"\\n";for (int i=1;i<=m;i++){if (!good[i]) continue;ans[i]=(ans[i]+(cnt1[e[i].u])*(cnt2[e[i].v]))%mod;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;for (int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;ins(a,b,c);inss(b,a,c);}for (int i=1;i<=n;i++){solve(i);}for (int i=1;i<=m;i++){cout<<(ans[i])%mod<<"\\n";}return 0;
}