【以上均出自WOJ】
最短路 设一个ans数组记录当前点的最短路有几条。 满足条件更新。 松弛的时候重新更新。
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return x*f; } struct edge{ int v,w,nxt; }e[4000010]; int first[2010],cnt=0; inline void add(int u,int v,int w){ e[++cnt].v=v;e[cnt].w=w; e[cnt].nxt=first[u];first[u]=cnt; } int n,m,g[2005][2005],dis[2005],vis[2005],ans[2005]; void dijkstra(){ priority_queue< pair<int,int> >q; memset(dis,0x3f,sizeof(dis)); dis[1]=0;ans[1]=1; q.push(make_pair(0,1)); while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u])continue; vis[u]=1; for(int i=first[u];i;i=e[i].nxt){ int v=e[i].v; if(dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; q.push(make_pair(-dis[v],v)); ans[v]=ans[u]; } else if(dis[v]==dis[u]+e[i].w)ans[v]+=ans[u]; } } } int main(){ n=read();m=read(); for(int i=1;i<=m;i++){ int u,v,w; u=read();v=read();w=read(); if(!g[u][v]||w<g[u][v])g[u][v]=w; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(g[i][j])add(i,j,g[i][j]); dijkstra(); if(dis[n]==0x3f3f3f3f)printf("No answer"); else printf("%d %d",dis[n],ans[n]); return 0; }最短路 判断一条边是否在最短路上。 双向dijkstra即可：dis_1[u]+e[i].w+dis_2[v]==dis_1[n]; 不过此题只用判零环，用一个flag数组就好。
#include<bits/stdc++.h> using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return x*f; } struct edge{ int v,w,nxt; }e[200010]; int first[5010],cnt=0; inline void add(int u,int v,int w){ e[++cnt].v=v;e[cnt].w=w; e[cnt].nxt=first[u];first[u]=cnt; } const int mod=1000000009; int n,m,dis[5005],vis[5005],ans[5005],flag[5005]; void dijkstra(){ priority_queue< pair<int,int> >q; memset(dis,0x3f,sizeof(dis)); dis[1]=0;ans[1]=1; q.push(make_pair(0,1)); while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u])continue; vis[u]=1; for(int i=first[u];i;i=e[i].nxt){ int v=e[i].v; if(dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; if(flag[u]||!e[i].w)flag[v]=1; else flag[v]=0; q.push(make_pair(-dis[v],v)); ans[v]=ans[u]; } else if(dis[v]==dis[u]+e[i].w)ans[v]=(ans[v]+ans[u])%mod; } } } int main(){ n=read();m=read(); for(int i=1;i<=m;i++){ int u,v,w; u=read();v=read();w=read(); add(u,v,w);add(v,u,w); } dijkstra(); if(flag[n])printf("-1"); else printf("%d",ans[n]); return 0; }次短路 次短路径和最短路径至少有一条边不同，且那条边一定不在最短路径上， 那我就双向dijkstra,枚举所有的边，再求这条边的起点到1，终点到n的最短路径，加上这条边权值，判断一下是否为最短路，再取maxans。
#include<bits/stdc++.h> using namespace std; struct edge{ int u,v,w,nxt; }e[200010]; int first[5005],cnt=0; inline void add(int u,int v,int w){ e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w; e[cnt].nxt=first[u];first[u]=cnt; } int n,m,ans; int vis[5005],dis1[5005],dis2[5005]; void dijkstra_1(){ priority_queue< pair<int,int> >q; q.push(make_pair(0,1)); memset(dis1,0x3f,sizeof(dis1)); memset(vis,0,sizeof(vis)); dis1[1]=0; while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u])continue; vis[u]=0; for(int i=first[u];i;i=e[i].nxt){ int v=e[i].v; if(dis1[v]>dis1[u]+e[i].w){ dis1[v]=dis1[u]+e[i].w; q.push(make_pair(-dis1[v],v)); } } } } void dijkstra_2(){ priority_queue< pair<int,int> >q; q.push(make_pair(0,n)); memset(dis2,0x3f,sizeof(dis2)); memset(vis,0,sizeof(vis)); dis2[n]=0; while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u])continue; vis[u]=0; for(int i=first[u];i;i=e[i].nxt){ int v=e[i].v; if(dis2[v]>dis2[u]+e[i].w){ dis2[v]=dis2[u]+e[i].w; q.push(make_pair(-dis2[v],v)); } } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w);add(v,u,w); } dijkstra_1(); dijkstra_2(); ans=0x7fffffff; for(int i=1;i<m*2;i++){ int r=dis1[e[i].u]+dis2[e[i].v]+e[i].w; if(r!=dis1[n]&&r<ans)ans=r; } printf("%d",ans); return 0; }二分图 二分图完全匹配问题 对每一个黑点，我们都建一条横坐标连向纵坐标的边， 然后跑二分图匹配。
推导 最终状态是（1,1）（2，2）…(n,n)都有一个点 我们把点看成匹配边的话，就是每行和每列都做到了匹配 换言之就是N个行和N个列都有匹配时，一定能转换成最终状态
#include<bits/stdc++.h> using namespace std; struct edge{ int u,v,nxt; }e[1000010]; int first[4010],cnt=0; inline void add(int u,int v){ e[++cnt].u=u;e[cnt].v=v; e[cnt].nxt=first[u];first[u]=cnt; } int n,t,vis[4010],match[4010],ans=0; bool dfs(int x){ for(int i=first[x];i;i=e[i].nxt){ int v=e[i].v; if(vis[v])continue; vis[v]=1; if(!match[v]||dfs(match[v])){ match[v]=x; return 1; } } return 0; } int main(){ scanf("%d",&t); while(t--){ memset(match,0,sizeof(match)); memset(first,0,sizeof(first)); ans=0; scanf("%d",&n); int c; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&c); if(c)add(i,j+n); } for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } if(ans==n)printf("Yes\n"); else printf("No\n"); } return 0; }二分图 裸二分图最大匹配
#include<bits/stdc++.h> using namespace std; int n,m,a[205][205],vis[405],mat[405],ans=0; bool dfs(int x){ for(int i=1;i<=m;i++){ if(!a[x][i]||vis[i])continue; vis[i]=1; if(!mat[i]||dfs(mat[i])){ mat[i]=x; return 1; } } return 0; } int main(){ scanf("%d%d",&n,&m); int c,d; for(int i=1;i<=n;i++){ scanf("%d",&c); while(c--){ scanf("%d",&d); a[i][d]=1; } } for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); ans+=dfs(i); } printf("%d",ans); return 0; }矩阵DP qwq ^ __ ^ qwq的算法一
#include<bits/stdc++.h> using namespace std; struct node{ int x,y; }a[5010]; inline int Sort_5(node e,node f){ return e.y<f.y; } inline int Sort_3(node e,node f){ return e.y>f.y; } inline int Sort_1(node e,node f){ return e.x<f.x; } int n,m,t,ans; void work(){ for(int i=1;i<=t;i++){//枚举左端点（右端点） int l=0,r=n; for(int j=i+1;j<=t;j++){//枚举产奶点，卡上下界 if(a[j].x>=r||a[j].x<=l)continue; ans=max(ans,abs(a[j].y-a[i].y)*(r-l));//不减一 if(a[j].x<a[i].x)l=a[j].x; else r=a[j].x; if(l>=r-1)break; } } } int main(){ scanf("%d%d%d",&n,&m,&t); if(t==0){ printf("%d",n*m); return 0; } for(int i=1;i<=t;i++){ scanf("%d%d",&a[i].x,&a[i].y); } a[++t].x=0;a[t].y=0;a[++t].x=n;a[t].y=m; a[++t].x=0;a[t].y=m;a[++t].x=n;a[t].y=0;//需要添加的点不仅仅是左下右上，4个顶角都要 sort(a+1,a+t+1,Sort_1); for(int i=2;i<=t;i++)ans=max(ans,m*(a[i].x-a[i-1].x)); sort(a+1,a+t+1,Sort_5); work(); sort(a+1,a+t+1,Sort_3); work(); printf("%d",ans); return 0; }