spfa
邻接矩阵
int dist[maxn],mp[maxn][maxn]; int visit[maxn]; void spfa() //SPFA算法 { int i, now; memset(visit, false, sizeof(visit)); for(i = 1; i <= n; i++) dist[i] = inf; dist[1] = 0; queue<int> Q; Q.push(1); visit[1] = true; while(!Q.empty()) { now = Q.front(); Q.pop(); visit[now] = false; for(i = 1; i <= n; i++) { if(dist[i] > dist[now] + mp[now][i]) { dist[i] = dist[now] + mp[now][i]; if(visit[i] == 0) { Q.push(i); visit[i] = true; } } } } }
邻接表
int n,m,ans; int head[MAXN]; int begin1,end1; int dis[MAXN],vis[MAXN]; struct node { int u,v,w; int next; }edge[MAXN]; void init() { ans=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int w) { edge[ans].u=u; edge[ans].v=v; edge[ans].w=w; edge[ans].next=head[u]; // next标记以u为起点的下一条边 head[u]=ans++; // head标记这个点是哪条边的起点，更新head } void SPFA(int begin1) { int i,j; queue<int>q; for(int i=0;i<n;i++) dis[i]=INF; memset(vis,0,sizeof(vis)); dis[begin1]=0,vis[begin1]=1; q.push(begin1); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(i=head[u];i!=-1;i=edge[i].next){ int top=edge[i].v; if(dis[top]>dis[u]+edge[i].w){ dis[top]=dis[u]+edge[i].w; if(!vis[top]){ vis[top]=1; q.push(top); } } } } if(dis[end1]==INF) printf("-1 "); else printf("%d ",dis[end1]); }
Dijkstra
const int INF = 0x3f3f3f3f; int dis[maxn],n; struct node{ int x,d; node(){} node(int a,int b){x=a;d=b;} bool operator < (const node & a) const { if(d==a.d) return x<a.x; else return d > a.d; } }; vector<node> eg[maxn]; void init() { for(int i=0;i<=n;i++) eg[i].clear(); } void Dijkstra(int s) { memset(dis,INF,sizeof(dis)); dis[s]=0; priority_queue<node> q; q.push(node(s,dis[s])); while(!q.empty()){ node x=q.top(); q.pop(); for(int i=0;i<eg[x.x].size();i++){ node y=eg[x.x][i]; if(dis[y.x]>x.d+y.d){ dis[y.x]=x.d+y.d; q.push(node(y.x,dis[y.x])); } } } }
邻接表
const int maxm=200500; const int maxn=100500; inline int read() { int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x; } struct edge{ int u,v,a,b,next; }e[maxm]; int edgenum,head[maxn]; void addedge(int u,int v,int a,int b){ e[edgenum].u=u; e[edgenum].v=v; e[edgenum].a=a; e[edgenum].b=b; e[edgenum].next=head[u]; head[u]=edgenum++; } struct Node{ int id; LL d; Node(int id, LL d):id(id),d(d){} bool operator < (const Node &A)const{ return d > A.d; } }; LL d[maxn]; bool vis[maxn]; int dijkstra(int S,int T){ memset(d,0x3f,sizeof(d)); memset(vis,0,sizeof(vis)); priority_queue<Node> que; que.push(Node(S,1)); d[S]=1; while(!que.empty()){ Node tp1=que.top(); que.pop(); int tp=tp1.id; if(tp==T){ for(int i=1;;i++){ if((1LL<<i)>tp1.d)return i-1; } } if(vis[tp])continue; vis[tp]=1; for(int i=head[tp];i!=-1;i=e[i].next){ if(vis[e[i].v])continue; if(((e[i].a+tp1.d)/(tp1.d))>=(1LL<<e[i].b)&&e[i].a+tp1.d<d[e[i].v]){ d[e[i].v]=e[i].a+tp1.d; que.push(Node(e[i].v,d[e[i].v])); } } } return -1; }
前向星
int cnt; struct node { int from,to,val,next; }edge[maxm<<1]; int head[maxm]; LL dis[maxn]; int vis[maxn]; struct Node { int val,id; bool operator <(const Node &b)const { if(val==b.val)return id<b.id; return val>b.val; } }; void init() { memset(head,-1,sizeof(head)); cnt=1; } void addedge(int from,int to,int val) { edge[cnt].from=from; edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } void dijkstra(int s,int e) { memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); Node now; priority_queue<Node>q; while(q.size())q.pop(); now.val=0,now.id=s; dis[s]=0; q.push(now); while(!q.empty()){ Node u=q.top(); q.pop(); if(vis[u.id])continue; vis[u.id]=1; for(int i=head[u.id];i!=-1;i=edge[i].next){ int to=edge[i].to; if(dis[u.id]+edge[i].val<dis[to]){ dis[to]=dis[u.id]+edge[i].val; Node pus; pus.id=to,pus.val=dis[to]; q.push(pus); } } } return ; }
二维dijkstra
struct node { int next,to,val; }edge[100005]; int head[10005],cnt; struct Node { int to,val,sum; friend bool operator<(Node a,Node b){return a.val>b.val;} }; void addedge(int u,int v,int w) { edge[++cnt].next=head[u]; edge[cnt].to=v; edge[cnt].val=w; head[u]=cnt; } void add(int u,int v,int w) { addedge(u,v,w); addedge(v,u,w); } void init() { cnt=0; memset(head,-1,sizeof(head)); } int dis[10005][25],vis[10005][25]; int k; void dijsktra(int s) { priority_queue<Node>que; memset(dis,127/3,sizeof(dis)); dis[s][0]=0; que.push((Node){s,0,0}); while(!que.empty()){ Node x=que.top();que.pop(); if(vis[x.to][x.sum])continue; vis[x.to][x.sum]=1; for(int i=head[x.to];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[y][x.sum+1]>dis[x.to][x.sum]&&x.sum+1<=k){ dis[y][x.sum+1]=dis[x.to][x.sum]; que.push((Node){y,dis[y][x.sum+1],x.sum+1}); } if(dis[y][x.sum]>dis[x.to][x.sum]+edge[i].val){ dis[y][x.sum]=dis[x.to][x.sum]+edge[i].val; que.push((Node){y,dis[y][x.sum],x.sum}); } } } return ; }
K短路
int s,t; int tot; int retot; struct Edge{ int to,w; int next1; }edge[maxe],redge[maxe]; //f = g + h ///先跑spfa，在跑Astar，s,t为起点终点 struct Node{ int v; int f,h,g; bool operator <(const Node &a)const { if(f==a.f)return g>a.g; return f>a.f; } }; int dis[maxn],head[maxe],rehead[maxe],vis[maxn]; void init() { tot=0 ; retot=0; memset(head,-1,sizeof(head)); memset(rehead,-1,sizeof(rehead)); } void addedge(int u,int v,int c){ edge[tot].to=v; edge[tot].w=c; edge[tot].next1=head[u]; head[u]=tot++; redge[retot].to=u; redge[retot].w=c; redge[retot].next1=rehead[v]; rehead[v]=retot++; } void spfa(){ for(int i=1;i<=n;i++)dis[i]=INF; dis[t]=0; queue<int>Q; Q.push(t); while(!Q.empty()){ int u=Q.front(); Q.pop(); for(int i=rehead[u];~i;i=redge[i].next1){ int v=redge[i].to; int w=redge[i].w; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; Q.push(v); } } } } int Astar(int st){ Node a; a.v=st; a.g=0; a.h=dis[st]; a.f=a.g+a.h; memset(vis,0,sizeof(vis)); if(dis[s]==INF) return -1; if(s==t)k++; priority_queue<Node>que; que.push(a); while(!que.empty()){ Node tmp=que.top(); que.pop(); int v=tmp.v; vis[v]++; if(vis[t]==k) return tmp.g; for(int i=head[v];~i;i=edge[i].next1 ){ Node p; p.v=edge[i].to; p.h=dis[edge[i].to]; p.g=tmp.g + edge[i].w; p.f=p.g + p.h; que.push(p); } } return -1; }
最小生成树
邻接表（kruskal）
int fa[maxn],sum,len; struct edge { int u,v,w; bool operator <(const edge &b)const{ return w<b.w; } }g[maxn]; void init() { sum=0;len=0; for(int i=0;i<=n;i++)fa[i]=i; } int Find(int x) { return fa[x]==x?x:fa[x]=Find(fa[x]); } void addedge(int u,int v,int w) { g[len].u=u; g[len].v=v; g[len++].w=w; } void kruskal() { int cot=0; sort(g,g+len); for(int i=0;i<len;i++){ int t1=Find(g[i].u); int t2=Find(g[i].v); if(t1!=t2){ fa[t2]=t1; cot++; sum=sum+g[i].w;///return sum } if(cot==n-1) break; } }
最小树形图
朱刘算法（无左偏树优化）
const int INF=0x7f7f7f7f; const int maxn=1005; struct Node { int u,v; LL w; }edge[maxn*maxn]; int pre[maxn],id[maxn],vis[maxn],n,m,pos; long long in[maxn]; long long Directed_MST(int root,int V,int E) {///点和边都是从0开始的 long long ret=0; while(true){ for(int i=0;i<V;i++)in[i]=INF; for(int i=0;i<E;i++){ int u=edge[i].u; int v=edge[i].v; if(edge[i].w<in[v]&&u!=v){ pre[v]=u; in[v]=edge[i].w; if(u==root)pos = i; } } for(int i=0;i<V;i++){ if(i==root)continue; if(in[i]==INF)return -1; } int cnt=0; memset(id,-1,sizeof(id)); memset(vis,-1,sizeof(vis)); in[root]=0; for(int i=0;i<V;i++){ ret+=in[i]; int v=i; while(vis[v]!=i&&id[v]==-1&&v!=root){ vis[v]=i; v=pre[v]; } if(v!=root&&id[v]==-1){ for(int u=pre[v];u!=v;u=pre[u])id[u]=cnt; id[v]=cnt++; } } if(cnt==0)break; for(int i=0;i<V;i++) if(id[i]==-1)id[i] = cnt++; for(int i=0;i<E;i++){ int u=edge[i].u; int v=edge[i].v; edge[i].u=id[u]; edge[i].v=id[v]; if(id[u]!=id[v])edge[i].w-=in[v]; } V=cnt;root=id[root]; } return ret; }
割点tarjan
const int maxn=110; int num[maxn],low[maxn],head[maxn],vis[maxn];///head为头，初始化为-1，Tarjan（root,-1） bool cut[maxn];///cut代表是不是割点 int res,n,cnt,root; struct Edge{ int to,next; }edge[maxn<<1]; void init() { memset(head,-1,sizeof(head)); memset(num,0,sizeof(num)); memset(low,0,sizeof(low)); memset(vis,0,sizeof(vis)); memset(cut,0,sizeof(cut)); cnt=0;res=0; } void addedge(int u,int v){ edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } void Tarjan(int u,int fa){ int son=0; vis[u]=1; num[u]=low[u]=++res; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(vis[v]==1 && v!=fa){ low[u]=min(low[u],num[v]); } if(vis[v]==0){ Tarjan(v,u); son++; low[u]=min(low[u],low[v]); if((u==root && son>1) || (u!=root && num[u]<=low[v])) cut[u]=1; } } vis[u]=2; }
int sum, dfn[maxe], low[maxe], vis[maxe], stk[maxe], top, col[maxe]; void tarjan(int x) { dfn[x] = low[x] = ++ sum; vis[x] = 1; stk[++top] =x; for(int i = head1[x]; i; i = nxt[i]) { if(!vis[to[i]]) { tarjan(to[i]); low[x] = min(low[x], low[to[i]]); } else if(vis[to[i]] == 1) { low[x] = min(low[x], dfn[to[i]]); } } if(dfn[x] == low[x]) { do { vis[stk[top]] = 2; col[stk[top]] = x; } while(stk[top--] != x); } }
最大流
struct Edge{ int next,to,f; }; struct Dinic { int s,t; Edge e[1000010]; int cnt=2,head[1000010]={0}; int dis[1000010]={0}; Dinic (){} void init(int _s,int _t) { cnt=2; s=_s,t=_t; memset(head,0,sizeof(head)); } void addedge(int u,int v,int f) { e[cnt]={head[u],v,f}; head[u]=cnt++; e[cnt]={head[v],u,0}; head[v]=cnt++; } bool bfs() { memset(dis,0,sizeof(dis)); dis[s]=1; queue<int> q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(!dis[v]&&e[i].f>0) { dis[v]=dis[u]+1; q.push(v); } } } return dis[t]!=0; } int dfs(int u,int flow) { if(u==t||flow==0) return flow; int flow_sum=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].to,f=e[i].f; if(dis[v]!=dis[u]+1||f==0) continue; int temp=dfs(v,min(flow-flow_sum,f)); e[i].f-=temp; e[i^1].f+=temp; flow_sum+=temp; if(flow_sum>=flow) break; } if(!flow_sum) dis[u]=-1; return flow_sum; } int maxflow() { int ans=0; while(bfs()) { while(int temp=dfs(s,0x7fffffff)) ans+=temp; } return ans; } }DC;
最小费用最大流
struct Min_cost_flow { int S,T,ans=0; int vis[100010],vis2[100010]; int d[100010],head[100010],to[100010],nextt[100010],w[100010],cost[100010]; int tot = 2; int inf=0x7fffffff; void init(int _s,int _t) { S=_s;T=_t; memset(head,0,sizeof(head)); ans=0;tot=2; } void add(int u,int v,int cap,int co) { cost[tot]=co; w[tot]=cap; to[tot]=v; nextt[tot]=head[u]; head[u]=tot++; cost[tot] = -co; w[tot]=0; to[tot]=u; nextt[tot]=head[v]; head[v]=tot++; } bool spfa() { memset(vis,0,sizeof(vis)); memset(vis2,0,sizeof(vis2)); for(int i = 1;i<=T;i++)d[i]=inf; queue<int> q; q.push(S); d[S]=0; vis[S]=1; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i = head[u];i;i=nextt[i]) { int v = to[i]; if(w[i] && d[v]>d[u]+cost[i]) { d[v]=d[u]+cost[i]; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return d[T]<inf; } int dfs(int u,int f) { if(u==T) { ans+=d[u] * f; return f; } int res=0; vis2[u]=1; for(int i=head[u];i;i=nextt[i]) { int v = to[i]; if (w[i] && !vis2[v] && d[v]==d[u]+cost[i]) { int temp=dfs(v,min(f-res,w[i])); w[i] -= temp; w[i^1] += temp; res += temp; if(res == f)return res; } } return res; } int MCMF() { while(spfa())dfs(S,inf); return ans; } }mcmf;
浮点数最小费用最大流，只是加了eps，不然会T
const double eps=1e-8; struct Min_cost_flow { int S,T; double ans=0; int vis[100010],vis2[100010]; int head[100010],to[100010],nextt[100010],w[100010]; double d[100010],cost[100010]; int tot = 2; double inf=0x7fffffff; void init(int _s,int _t) { S=_s;T=_t; memset(head,0,sizeof(head)); ans=0;tot=2; } void add(int u,int v,int cap,double co) { cost[tot]=co; w[tot]=cap; to[tot]=v; nextt[tot]=head[u]; head[u]=tot++; cost[tot] = -co; w[tot]=0; to[tot]=u; nextt[tot]=head[v]; head[v]=tot++; } bool spfa() { memset(vis,0,sizeof(vis)); memset(vis2,0,sizeof(vis2)); for(int i = 1;i<=T;i++)d[i]=inf; queue<int> q; q.push(S); d[S]=0; vis[S]=1; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i = head[u];i;i=nextt[i]) { int v = to[i]; if(w[i] && d[v]>d[u]+cost[i]+eps) { d[v]=d[u]+cost[i]; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return d[T]<inf; } int dfs(int u,int f) { if(u==T) { ans+=d[u] * f; return f; } int res=0; vis2[u]=1; for(int i=head[u];i;i=nextt[i]) { int v = to[i]; if (w[i] && !vis2[v] && d[v]==d[u]+cost[i]) { int temp=dfs(v,min(f-res,w[i])); w[i] -= temp; w[i^1] += temp; res += temp; if(res == f)return res; } } return res; } double MCMF() { while(spfa())dfs(S,inf); return ans; } }mcmf;
带返回流量的（好像有问题）
struct Edge { int to,next,cap,flow,cost; }edge[maxm]; int head[maxn],tol; int pre[maxn],dis[maxn]; bool vis[maxn]; int N;//节点总个数，节点编号从0~N-1 void init(int n) {//0==S N-1==T N = n; tol = 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int cap,int cost) { edge[tol].to = v; edge[tol].cap = cap; edge[tol].cost = cost; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = 0; edge[tol].cost = -cost; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++; } bool spfa(int s,int t) { queue<int>q; for(int i = 0;i < N;i++) { dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u]; i != -1;i = edge[i].next) { int v = edge[i].to; if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ) { dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]) { vis[v] = true; q.push(v); } } } } if(pre[t] == -1)return false; else return true; } //返回的是最大流，cost存的是最小费用 int minCostMaxflow(int s,int t,int &cost) { int flow = 0; cost = 0; while(spfa(s,t)){ int Min = INF; for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){ if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; } for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){ edge[i].flow += Min; edge[i^1].flow -= Min; cost += edge[i].cost * Min; } flow += Min; } return flow; }
无向图最小割
struct Stoer_Wagner { int n,g[maxn][maxn],b[maxn],dis[maxn]; void init(int nn,int w[maxn][maxn]){ int i,j; n=nn; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ g[i][j]=w[i][j]; } } } int Min_Cut_Phase(int ph,int &x,int &y){ int i,j,t; b[t=1]=ph; for(i=1;i<=n;++i) if(b[i]!=ph)dis[i]=g[1][i]; for(i=1;i<n;++i){ x=t; for(t=0,j=1;j<=n;++j) if(b[j]!=ph && (!t||dis[j]>dis[t]))t=j; b[t]=ph; for(j=1;j<=n;++j) if(b[j]!=ph)dis[j]+=g[t][j]; } return y=t,dis[t]; } void Merge(int x,int y){ int i; if(x>y)swap(x,y); for(i=1;i<=n;++i) if(i!=x&&i!=y) g[i][x]+=g[i][y],g[x][i]+=g[i][y]; if(y==n)return ; for(i=1;i<n;++i)if(i!=y){ swap(g[i][y],g[i][n]); swap(g[y][i],g[n][i]); } } int Min_Cut(){ int i,ret=0x3fffffff,x,y; memset(b,0,sizeof(b)); for(i=1;n>1;++i,--n){ ret=min(ret,Min_Cut_Phase(i,x,y)); Merge(x,y); } return ret; } }SW;
二分图
有关系为1没关系为0
int mp[maxn][maxn]; int book[maxn],vis[maxn],sum; bool dfs(int x) { for(int i=1;i<=m;i++) { if(mp[x][i]&&!vis[i]){ vis[i]=1; if(book[i]==0||dfs(book[i])){ book[i]=x; return 1; } } } return 0; } int solve() { int sum=0; memset(book,0,sizeof(book)); for(int i=1; i<=n; i++){ memset(vis,0,sizeof(vis)); if(dfs(i)) sum++; } return sum; }
倍增LCA（附带扩栈指令）
int n,m,s,num; int f[maxn][30],head[maxn],dep[maxn]; bool vis[maxn]; LL val[maxn][60]; struct node { int next,to; }e[maxn<<1]; inline void add(int from,int to) { e[++num].next=head[from]; e[num].to=to; head[from]=num; } inline void dfs(int x,int d,int pre) { vis[x]=1;dep[x]=d; for(int i=head[x];i;i=e[i].next) { int to=e[i].to; if(!vis[to]) { f[to][0]=x; dfs(to,d+1,x); } } } inline int lca(int a,int b) { if(dep[a]<dep[b]){int t=a;a=b;b=t;} int d=dep[a]-dep[b]; for(int i=20;i>=0;i--) if(d&(1<<i)) a=f[a][i]; if(a==b) return a; for(int i=20;i>=0;i--) if(f[a][i]!=f[b][i]) { a=f[a][i]; b=f[b][i]; } return f[a][0]; } int main() { n=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); add(u,v); add(v,u); } dfs(s,1,0);//s是rt for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; return 0; }
最小生成树计数
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=107; const int M=1007; const int MOD=31011; LL n,m,ans; vector<int>gra[N]; struct edge{ int u,v,w; }e[M]; int cmp(edge a,edge b){ return a.w<b.w; } LL mat[N][N],g[N][N]; LL fa[N],ka[N],vis[N]; LL det(LL c[][N],LL n){ LL i,j,k,t,ret=1; for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]%=MOD; for(i=0; i<n; i++){ for(j=i+1; j<n; j++){ while(c[j][i]){ t=c[i][i]/c[j][i]; for(k=i; k<n; k++) c[i][k]=(c[i][k]-c[j][k]*t)%MOD; swap(c[i],c[j]); ret=-ret; } } if(c[i][i]==0)return 0L; ret=ret*c[i][i]%MOD; } return (ret+MOD)%MOD; } LL Find(LL a,LL f[]){ return f[a]==a?a:Find(f[a],f); } void matrix_tree(){///对当前长度的边连接的每个联通块计算生成树个数 for(int i=0;i<n;i++)if(vis[i]){///当前长度的边连接了i节点 gra[Find(i,ka)].push_back(i);///将i节点压入所属的联通块 vis[i]=0;///一边清空vis数组 } for(int i=0;i<n;i++){ if(gra[i].size()>1){///联通块的点数为1时生成树数量是1 memset(mat,0,sizeof mat);///清空矩阵 int len=gra[i].size(); for(int j=0;j<len;j++){ for(int k=j+1;k<len;k++){///构造这个联通块的矩阵（有重边） int u=gra[i][j],v=gra[i][k]; if(g[u][v]){ mat[k][j]=(mat[j][k]-=g[u][v]); mat[k][k]+=g[u][v];mat[j][j]+=g[u][v]; } } } ans=ans*det(mat,gra[i].size()-1)%MOD; for(int j=0;j<len;j++)fa[gra[i][j]]=i;///缩点 } } for(int i=0;i<n;i++){ gra[i].clear(); ka[i]=fa[i]=Find(i,fa); } } int main() { scanf("%lld%lld",&n,&m); for(int i=0;i<m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); u--;v--; e[i]=(edge){u,v,w}; } sort(e,e+m,cmp); memset(g,0,sizeof(g)); ans=1; for(LL i=0;i<n;i++)ka[i]=fa[i]=i; for(LL i=0;i<=m;i++){///边从小到大加入 if(i&&e[i].w!=e[i-1].w||i==m)///处理完长度为e[i-1].w的所有边 matrix_tree();///计算生成树 LL u=Find(e[i].u,fa),v=Find(e[i].v,fa);///连的两个缩点后的点 if(u!=v){///如果不是一个 vis[v]=vis[u]=1; ka[Find(u,ka)]=Find(v,ka);///两个分量在一个联通块里。 g[u][v]++,g[v][u]++;///邻接矩阵 } } int flag=1; for(int i=1;i<n;i++)if(fa[i]!=fa[i-1])flag=0; printf("%lld ",flag?ans%MOD:0);///注意p可能为1，这样m=0时如果ans不%p就会输出1 return 0; }