贴板子系列_1 网络流

网络流

 1 //Dinic  
 2 struct MAX_FLOW
 3 {
 4     struct edge
 5     {
 6         int v,next,w;
 7     } vs[14000];
 8     int st[N],ee,h[N],cur[N];
 9     inline void addedge(int u,int v,int w)
10     {
11         vs[++ee].v=v;
12         vs[ee].next=st[u];
13         st[u]=ee;
14         vs[ee].w=w;
15     }
16     inline void insert(int u,int v,int w)
17     {
18         addedge(u,v,w);
19         addedge(v,u,0);
20     }
21     bool bfs()
22     {
23         memset(h,-1,sizeof(h));
24         queue <int> q;
25         q.push(S),h[S]=0;
26         while(!q.empty())
27         {
28             int lx=q.front();
29             q.pop();
30             for(int i=st[lx]; i; i=vs[i].next)
31                 if(vs[i].w&&h[vs[i].v]==-1)
32                 {
33                     h[vs[i].v]=h[lx]+1;
34                     q.push(vs[i].v);
35                 }
36         }
37         return h[T]!=-1;
38     }
39     int dfs(int x,int f)
40     {
41         if(x==T) return f;
42         int used=0,w;
43         for(int i=cur[x]; i; i=vs[i].next)
44             if(vs[i].w&&h[vs[i].v]==h[x]+1)
45             {
46                 w=dfs(vs[i].v,min(f-used,vs[i].w));
47                 vs[i].w-=w;
48                 vs[i^1].w+=w;
49                 used+=w;
50                 if(vs[i].w) cur[x]=i;
51                 if(used==f) return used;
52             }
53         if(!used) h[x]=-1;
54         return used;
55     }
56     void dinic()
57     {
58         while(bfs())
59         {
60             for(int i=S; i<=T; i++)
61                 cur[i]=st[i];
62             ans+=dfs(S,inf);
63         }
64     }
65 }G;

费用流

 1 struct edge
 2 {
 3     int u,v,w;
 4     int next,c;
 5 }vs[M];
 6 int n,ee=1,st[N],from[N],S,T,m,tot;
 7 int ans=0,vis[N],dis[N],p[N];
 8 queue <int> q;
 9 inline void addedge(int u,int v,int w,int c)
10 {
11     vs[++ee].u=u;vs[ee].v=v;vs[ee].w=w;
12     vs[ee].next=st[u];st[u]=ee;vs[ee].c=c;
13 }
14 inline void insert(int u,int v,int w,int c)
15 {
16     addedge(u,v,w,c);addedge(v,u,0,-c);
17 }
18 bool spfa()
19 {
20     for(int i=S;i<=T;i++) dis[i]=inf;
21     while(!q.empty())q.pop();
22     q.push(S);dis[S]=0;vis[S]=1;
23     while(!q.empty())
24     {
25         int lx=q.front();q.pop();
26         for(int i=st[lx];i;i=vs[i].next)
27             if(vs[i].w&&dis[lx]+vs[i].c<dis[vs[i].v])
28             {
29                 dis[vs[i].v]=dis[lx]+vs[i].c;
30                 from[vs[i].v]=lx;p[vs[i].v]=i;
31                 if(!vis[vs[i].v]) q.push(vs[i].v),vis[vs[i].v]=1;
32             }
33         vis[lx]=0;
34     }
35     return dis[T]!=inf;
36 }
37 inline void mcf()
38 {
39     int ss=inf;
40     for(int i=T;i!=S;i=from[i])
41         ss=min(ss,vs[p[i]].w);
42     for(int i=T;i!=S;i=from[i])
43     {
44         vs[p[i]].w-=ss;vs[p[i]^1].w+=ss;
45         ans+=ss*vs[p[i]].c;
46     }tot-=ss;
47 }