图论相关算法模板

 1 int head[maxn];
 2 struct edge
 3 {
 4     int to,nxt,from;
 5 }e[50005];
 6 int cnt;
 7 inline void addedge(int u,int v)
 8 {
 9     e[++cnt].to=v;
10     e[cnt].from=u;
11     e[cnt].nxt=head[u];
12     head[u]=cnt;
13 }
14 int dfn[maxn],low[maxn],f[maxn],ttime,tot,num[maxn];
15 bool vis[maxn];
16 stack<int>st;
17 void dfs(int u,int fa)
18 {
19     st.push(u);
20     low[u]=dfn[u]=++ttime;
21     f[u]=fa;
22     vis[u]=1;
23     for(int i=head[u];i;i=edge[i].nxt)
24     {
25         int v=edge[i].to;
26         //if(v==fa) continue;对于无向图需要特殊处理
27         if(!dfn[v])
28         {
29             dfs(v,u);
30             low[u]=min(low[u],low[v]);
31         }
32         else if(vis[v])
33             low[u]=min(dfn[v],low[u]);
34     }
35     if(low[u]==dfn[u])
36     {
37         ++tot;
38         while(1)
39         {
40             int tmp=st.top();
41             num[tmp]=tot;
42             vis[tmp]=0;
43             st.pop();
44             if(tmp==u)
45                 break;
46         }
47     }
48 }

 1 int cnt;
 2 int head[maxn];
 3 struct Edge
 4 {
 5     int nxt,to,val;
 6 }edge[maxn*10];
 7 inline void addedge(int x,int y){edge[++cnt].to=y;edge[cnt].nxt=head[x];head[x]=cnt;}
 8 int dfn[maxn],low[maxn],f[maxn],ttime,tot,num[maxn];
 9 int iscut[maxn];
10 typedef pair<int,int> P;
11 stack<P>st;
12 void dfs(int u,int fa)
13 {
14     low[u]=dfn[u]=++ttime;
15     f[u]=fa;
16     int son=0;
17     for(int i=head[u];i;i=edge[i].nxt)
18     {
19         int v=edge[i].to;
20         if(v==fa)
21             continue;
22         if(!dfn[v])
23         {
24             son++;
25             st.push(P(u,v));
26             dfs(v,u);
27             low[u]=min(low[u],low[v]);
28             if(dfn[u]<=low[v])
29             {
30                 iscut[u]=1;
31                 ++tot;
32                 while(1)
33                 {
34                     P tmp=st.top();
35                     st.pop();
36                     num[tmp.first]=num[tmp.second]=tot;//属于点双连通分量
37                     if(tmp.first==u&&tmp.second==v)
38                         break;
39                 }
40             }
41         }
42         else if(dfn[v]<dfn[u])//后向边
43         {
44             low[u]=min(dfn[v],low[u]);
45             st.push(P(u,v));
46         }
47     }
48     if(fa==0&&son==1)
49         iscut[u]=0;
50 }

 1 const int MAXN = 2010;//点数的最大值
 2 const int MAXM = 1200010;//边数的最大值
 3 const int INF = 0x3f3f3f3f;
 4 struct Edge
 5 {
 6     int to,next,cap,flow;
 7 } edge[MAXM]; //注意是 MAXM
 8 int tol;
 9 int head[MAXN];
10 void init()
11 {
12     tol = 2;
13     memset(head,-1,sizeof(head));
14 }
15 void addedge(int u,int v,int w,int rw = 0)
16 {
17     edge[tol].to = v;
18     edge[tol].cap = w;
19     edge[tol].flow = 0;
20     edge[tol].next = head[u];
21     head[u] = tol++;
22     edge[tol].to = u;
23     edge[tol].cap = rw;
24     edge[tol].flow = 0;
25     edge[tol].next = head[v];
26     head[v] = tol++;
27 }
28 int Q[MAXN];
29 int dep[MAXN],cur[MAXN],sta[MAXN];
30 bool bfs(int s,int t,int n)
31 {
32     int front = 0,tail = 0;
33     memset(dep,-1,sizeof(dep[0])*(n+1));
34     dep[s] = 0;
35     Q[tail++] = s;
36     while(front < tail)
37     {
38         int u = Q[front++];
39         for(int i = head[u]; i != -1; i = edge[i].next)
40         {
41             int v = edge[i].to;
42             if(edge[i].cap > edge[i].flow && dep[v] == -1)
43             {
44                 dep[v] = dep[u] + 1;
45                 if(v == t)return true;
46                 Q[tail++] = v;
47             }
48         }
49     }
50     return false;
51 }
52 int dinic(int s,int t,int n)
53 {
54     int maxflow = 0;
55     while(bfs(s,t,n))
56     {
57         for(int i = 0; i < n; i++)cur[i] = head[i];
58         int u = s, tail = 0;
59         while(cur[s] != -1)
60         {
61             if(u == t)
62             {
63                 int tp = INF;
64                 for(int i = tail-1; i >= 0; i--)
65                     tp = min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
66                 maxflow += tp;
67                 for(int i = tail-1; i >= 0; i--)
68                 {
69                     edge[sta[i]].flow += tp;
70                     edge[sta[i]^1].flow -= tp;
71                     if(edge[sta[i]].cap-edge[sta[i]].flow == 0)
72                         tail = i;
73                 }
74                 u = edge[sta[tail]^1].to;
75             }
76             else if(cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to])
77             {
78                 sta[tail++] = cur[u];
79                 u = edge[cur[u]].to;
80             }
81             else
82             {
83                 while(u != s && cur[u] == -1)
84                     u = edge[sta[--tail]^1].to;
85                 cur[u] = edge[cur[u]].next;
86             }
87         }
88     }
89     return maxflow;
90 }

 1 #include<bits/stdc++.h>
 2 const int MAXN = 10000;
 3 const int MAXM = 100000;
 4 const int INF = 0x3f3f3f3f;
 5 struct Edge
 6 {
 7     int to,next,cap,flow,cost;
 8 } edge[MAXM];
 9 int head[MAXN],tol;
10 int pre[MAXN],dis[MAXN];
11 bool vis[MAXN];
12 int N;//节点总个数，节点编号从 0∼N-1
13 void init(int n)
14 {
15     N = n;
16     tol = 0;
17     memset(head,-1,sizeof(head));
18 }
19 void addedge(int u,int v,int cap,int cost)
20 {
21     edge[tol].to = v;
22     edge[tol].cap = cap;
23     edge[tol].cost = cost;
24     edge[tol].flow = 0;
25     edge[tol].next = head[u];
26     head[u] = tol++;
27     edge[tol].to = u;
28     edge[tol].cap = 0;
29     edge[tol].cost = -cost;
30     edge[tol].flow = 0;
31     edge[tol].next = head[v];
32     head[v] = tol++;
33 }
34 bool spfa(int s,int t)
35 {
36     std::queue<int>q;
37     for(int i = 0; i < N; i++)
38     {
39         dis[i] = INF;
40         vis[i] = false;
41         pre[i] = -1;
42     }
43     dis[s] = 0;
44     vis[s] = true;
45     q.push(s);
46     while(!q.empty())
47     {
48         int u = q.front();
49         q.pop();
50         vis[u] = false;
51         for(int i = head[u]; i != -1; i = edge[i].next)
52         {
53             int v = edge[i].to;
54             if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost )
55             {
56                 dis[v] = dis[u] + edge[i].cost;
57                 pre[v] = i;
58                 if(!vis[v])
59                 {
60                     vis[v] = true;
61                     q.push(v);
62                 }
63             }
64         }
65     }
66     if(pre[t] == -1)
67         return false;
68     else
69         return true;
70 }
71 //返回的是最大流，cost 存的是最小费用
72 int minCostMaxflow(int s,int t,int &cost)
73 {
74     int flow = 0;
75     cost = 0;
76     while(spfa(s,t))
77     {
78         int Min = INF;
79         for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
80         {
81             if(Min > edge[i].cap - edge[i].flow)
82                 Min = edge[i].cap - edge[i].flow;
83         }
84         for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
85         {
86             edge[i].flow += Min;
87             edge[i^1].flow -= Min;
88             cost += edge[i].cost * Min;
89         }
90         flow += Min;
91     }
92     return flow;
93 }