图论板子整理

SPFA

 1 void spfa(){
 2     queue<int> q;
 3     for(int i=1; i<=n; i++) dis[i]=INF; 
 4     q.push(s); dis[s]=0; vist[s]=1;
 5     while(!q.empty()){
 6     int u=q.front();
 7     q.pop();vist[u]=0;
 8     for(int i=head[u];i;i=edge[i].next)
 9         if(dis[edge[i].to]>dis[u]+edge[i].dis){
10             dis[edge[i].to]=dis[u]+edge[i].dis;
11             if(vist[edge[i].to]==0){vist[edge[i].to]=1;q.push(edge[i].to);}
12         }   
13     }
14 }
15 void spfa(int u){//DFS
16     vist[u]=1;
17     for(int i=head[u];i;i=edge[i].nxt){
18         int g=edge[i].to;
19         if(dis[g]<dis[u]+edge[i].dis){
20             dis[g]=dis[u]+edge[i].dis;
21             spfa(g);
22         }
23     }
24     vist[u]=0;
25 }

迪杰

 1 void dij(){
 2 for(int i=1;i<=n;i++)dis[i]=INF;
 3 priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > >q;
 4 dis[s]=0;
 5 q.push(make_pair(0,s));
 6 while(!q.empty())
 7 {
 8 int tt=q.top().second;
 9 q.pop();
10 if(vist[tt])continue;
11 vist[tt]=1;
12 for(int i=head[tt];i;i=edge[i].next)
13 if(dis[edge[i].to]>dis[tt]+edge[i].dis){dis[edge[i].to]=dis[tt]+edge[i].dis;
14 q.push(make_pair(dis[edge[i].to],edge[i].to));    }
15 }
16 }

DAG=拓扑配DP

 1 int n,c,id,ne,ans,a,b,m;
 2 struct Edge{int to,next;}edge[MAXN];
 3 int head[MAXN],rd[MAXN],sj[MAXN],f[MAXN];
 4 void adde(int from,int to){
 5     edge[++ne].next=head[from];
 6     edge[ne].to=to;
 7     head[from]=ne;
 8     rd[to]++;
 9 }
10 void topo()
11 {
12     queue<int> q;
13     f(1,n){if(!rd[i])q.push(i);f[i]=1;}
14     while(!q.empty()){
15         int x=q.front();q.pop();
16         for(int i=head[x];i;i=edge[i].next){
17         int v=edge[i].to;
18             f[v]=max(f[v],f[x]+1);
19             if(!--rd[v])q.push(v);
20         }
21     }
22 }
23 int main(){
24 cin>>n>>m;
25 w(m){cin>>a>>b;adde(a,b);}
26     topo();    
27     f(1,n)cout<<f[i]<<endl;
28 }

krusal

 1 int main(){
 2     cin>>n>>m;
 3     f(1,m){cin>>a>>b>>c;adde(a,b,c);adde(b,a,c);}
 4     f(1,ne)f[i]=i;
 5     sort(edge+1,edge+ne+1,cmp);
 6     f(1,ne){int x=find(edge[i].from),y=find(edge[i].to);
 7         if(x!=y){cnt++;ans+=edge[i].dis;f[x]=y;}
 8         if(cnt==n-1)break;
 9     }
10     if(cnt==n-1)cout<<ans;
11     else cout<<"orz";
12 }

PRIM

 1 void prim(){
 2 for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f;
 3 priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > > q;
 4 dis[1]=0;
 5 q.push(make_pair(0,1));
 6 while(!q.empty()){
 7 int u=q.top().second;q.pop();
 8 if(vist[u])continue;
 9 vist[u]=1;
10 ++cnt;
11 ans+=dis[u];
12 for(int i=head[u];i;i=edge[i].next){
13 int g=edge[i].to;
14 if(edge[i].dis<dis[g]){
15 dis[g]=edge[i].dis;
16 q.push(make_pair(dis[g],g));
17 }
18 }
19 if(cnt==n)break;
20 }
21 }

二分图最大匹配

 1 int dfs(int u) {
 2 for(int i=head[u];i;i=edge[i].nxt) {
 3 int g=edge[i].to;
 4 if(!mk[g]){mk[g]=1;if(!vis[g]||dfs(vis[g])) {vis[g]=u;return 1;}}
 5 }
 6 return 0;
 7 }
 8 int main() {
 9 cin>>n>>m>>k;
10 while(k--){cin>>a>>b;if(a>n||b>m)continue;adde(a,b);}
11 for(int i=1;i<=n;i++){
12 memset(mk,0,sizeof(mk));if(dfs(i))++_ans;
13 } 
14 cout<<_ans;
15 }